검 지 offer (제2판) python 실현
19877 단어 알고리즘 지식
2.2 프로 그래 밍 언어
면접 문제 2: 단일 디자인 모델 구현
제목: 하나의 클래스 를 설계 합 니 다. 우 리 는 이 클래스 의 인 스 턴 스 만 생 성 할 수 있 습 니 다.
LeetCode: 이 문 제 는 LeetCode 에 없습니다.
문제 풀이 방향:
개인 플래그 를 정의 하고 None 로 초기 화 합 니 다. 인 스 턴 스 를 만 들 면 이 플래그 를 인 스 턴 스 로 설정 합 니 다.
구현 코드:
class Earth(object):
__instance = None
def __new__(cls):
if cls.__instance is not None:
# __instance
# __new__(cls)
cls.__instance = object.__new__(cls)
return cls.__instance
else:
#
return cls.__instance
2.3 데이터 구조
면접 문제 3: 배열 에서 중복 되 는 숫자
제목: 하나의 정수 배열 a 를 지정 하 였 으 며, 그 중 1 ≤ a [i] ≤ n (n 은 배열 길이), 그 중 일부 요 소 는 두 번 나타 나 고, 기타 요 소 는 한 번 나타 납 니 다.두 번 나타 나 는 모든 원 소 를 찾 습 니 다.
제목 요구: 당신 은 어떠한 추가 공간 도 가지 않 고 O (n) 시간 복잡 도 에서 이 문 제 를 해결 할 수 있 습 니까?
LeetCode: LeetCode 442: 배열 에서 중복 되 는 데이터
문제 풀이 방향:
구현 코드:
def findDuplicates(nums):
m_list = []
for i in nums:
# ,
# , , ,
if nums[abs(i)-1] > 0:
nums[abs(i)-1] *= -1
else:
m_list.append(abs(i))
print(m_list)
if __name__ == '__main__':
list = [4, 3, 2, 7, 8, 2, 3, 1]
findDuplicates(list)
면접 문제 4: 2 차원 배열 에서 의 찾기
제목: m x n 매트릭스 matrix 의 목표 값 target 을 검색 하기 위해 효율 적 인 알고리즘 을 만 듭 니 다.이 행렬 은 다음 과 같은 특성 을 가지 고 있다. 각 줄 의 요 소 는 왼쪽 에서 오른쪽으로 오름차 순 으로 배열 된다.각 열의 요 소 는 위 에서 아래로 오름차 순 으로 배열 된다.
제목: 없 음
LeetCode: LeetCode 240: 2 차원 매트릭스 검색 II
문제 풀이 방향:
구현 코드:
def searchMatrix(matrix, target):
found = False
#
rows = len(matrix)
#
columns = len(matrix[0])
if matrix is not None and rows > 0 and columns > 0:
#
row = 0
#
column = columns - 1
# ,
# 0
while row < rows and column >= 0:
if matrix[row][column] == target:
found = True
return found
elif matrix[row][column] > target:
column -= 1
else:
row += 1
return found
if __name__ == '__main__':
mli = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
found = searchMatrix(mli, 20)
print(found)
면접 문제 5: 스페이스 바 꾸 기
제목: 한 문자열 의 빈 칸 을 '% 20' 으로 바 꾸 는 함 수 를 구현 하 십시오.예 를 들 어: We Are Happy 가 바 뀐 문자열 은: We% 20are% 20Happy 입 니 다.
제목: 없 음
LeetCode: 우 객 망
문제 풀이 방향:
python 에 내 장 된 문자열 로 함수 replace 를 바 꾸 고 빈 칸 을% 20 으로 바 꿉 니 다.
구현 코드:
def replaceSpace(s):
return s.replace(' ', '%20')
if __name__ == '__main__':
s = 'We are happy'
print(replaceSpace(s))
면접 문제 6: 끝 에서 끝까지 링크 인쇄
제목: 단일 체인 시트 반전.예제: 입력: 1 - > 2 - > 3 - > 4 - > 5 - > NULL 출력: 5 - > 4 - > 3 - > 2 - > 1 - > NULL
제목: 없 음
LeetCode: LeetCode 206: 반전 링크
문제 풀이 방향:
각 노드 를 이 노드 의 앞 자 리 를 가리 키 며 역 순 서 를 완성 합 니 다.
구현 코드:
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# ,pre cur,pre None
pre = None
cur = head
# ,while
# ,
while cur:
#
tmp = cur.next
# pre
cur.next = pre
# pre cur
pre = cur
cur = tmp
return pre
:user7439t
:https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
: (LeetCode)
。 , 。
면접 문제 7: 이 진 트 리 재건
제목: 이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어 앞 순 서 를 입력 하 십시오. {1, 2, 4, 7, 3, 5, 6, 8} 과 중간 순 서 를 입력 하 십시오. {4, 7, 2, 1, 5, 3, 8, 6} 은 이 진 트 리 를 재 구축 하고 돌아 갑 니 다.
제목: 없 음
LeetCode: LeetCode 206: 반전 링크
문제 풀이 방향:
각 노드 를 이 노드 의 앞 자 리 를 가리 키 며 역 순 서 를 완성 합 니 다.
구현 코드:
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# ,pre cur,pre None
pre = None
cur = head
# ,while
# ,
while cur:
#
tmp = cur.next
# pre
cur.next = pre
# pre cur
pre = cur
cur = tmp
return pre
:user7439t
:https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
: (LeetCode)
。 , 。