Leetcode 는 문 제 를 풀 고 조금씩 깨 달 았 습 니 다.
자주 쓰 는 가방 몇 개.
1、from collections import deque
python 의 collections 모듈 에는 비교적 고 급 스 러 운 데이터 구조 가 많이 포함 되 어 있 습 니 다. 예 를 들 어 대기 열 해시 표 등 은 문 제 를 풀 때 사용 할 수 있 습 니 다.
대기 열 사용 방법 초기 화 a = deuqe () or deque (list), pop () 은 팝 업 의 맨 오른쪽 끝 (팀 끝), populeft 는 팝 업 팀 의 첫 번 째 요소 (상용), len (), append ()
2、import heapq
최대 / 최소 더미 의 기초 사용 방법
초기 화 / 추가: q = [xxxx] heap. heapify (q) or q = [] for... heapq. heappush (q, number)
최소 요소: q [0] 삭제: heapq. heappop (q)
Python 표준 라 이브 러 리 모듈 의 hepq, leetcode 의 hepq 사용 - key 가 있 는 정렬
3、import sys
소 객 / ACM 제출 형식 가 져 오기 입력 은 두 가지 형식 이 있 습 니 다. input () and string = sys. stdin. readline (). strip () 은 한 줄 의 입력 만 얻 을 수 있 습 니 다.
흔히 볼 수 있 는 문제 유형:
트 리 관련:
기본적으로 나무의 몇 가지 반복 적 인 변화 이다. 나무의 순환 과 교체 법의 앞 뒤 층 차 를 기억 하고 잘 알 아야 한다. 기본 적 으로 는 이 몇 가지 문제 이 고 비 순환 적 인 사상 을 이해 하 는 데 중심 을 두 어야 한다.
이 진 트 리 의 최대 경로 와 이 문 제 는 비교적 전형 적 이 며 코드 의 반환 과 처리 결과 가 어떻게 진행 되 는 지 볼 수 있 습 니 다.
배열 관련:
일반적으로 지침 을 사용 하여 풀 고 중복 항목 을 삭제 하 는 몇 가지 문제 가 있 는데 관건 은 바로 두 지침 의 사상 이다. 원시 배열 에서 직접 수정 하고 처리 할 수 있 고 중복 되 는 느 린 움직임 을 만 날 수 있다. 그렇지 않 으 면 함께 하 나 를 더 해서 운동 을 하 는 것 도 네덜란드 국기 와 마찬가지 이다.
링크 관련:
1. 두 개의 반전 링크 는 논 리 를 미리 파악 하고 종이 에 먼저 그 려 놓 은 다음 에 코드 를 쓰 면 많이 좋아 집 니 다 (25 문제 K 개 반전 링크 의 간단 한 모델)
2. 링크 작업 에서 주의해 야 할 점, 예 를 들 어 두 개의 할당, a = b, b 또는 a 의 next 를 바 꾸 면 나머지 next 도 이에 따라 달라 집 니 다. 두 개의 지침 이 하나의 주 소 를 가리 키 는 것 과 같 지만 이 두 지침 은 가리 키 는 주 소 를 바 꿀 수 있 습 니 다. 이때 다른 하 나 는 더 이상 변화 하지 않 습 니 다.
3. 링크 에서 가장 많이 사용 하 는 것 은 Dummy 노드 이 고 장면 을 많이 사용 하 며 빠 르 고 느 린 지침 도 있 습 니 다. 잊 지 마 세 요. 양 대 신기.
4. while 순환 에 while 순환 을 추가 하면 안에 while 의 조건 은 외부 에 있 는 것 을 더 해 야 합 니 다. 그렇지 않 으 면 크로스 오 버 오류 가 발생 합 니 다.
5. 링크 에서 마지막 몇 번 째 노드 와 관련 된 문 제 를 처리 해 야 한다. 먼저 모든 length 를 옮 겨 다 니 거나 느 린 지침 을 사용 하 는 방식 으로 시간 복잡 도가 더욱 낮다.
영문 자모 관련:
26 개의 자모 와 관련 된 것 은 모두 해시 표 로 해결 하 는데, 모두 상수 급 의 해시 이기 때문이다.
단조 로 운 창고
비교적 사용 하 는 데이터 구조, 단조 로 운 스 택 의 소개 와 기본 적 인 특성 입 니 다. 그 중에서 저 는 비교적 유용 하 다 고 생각 합 니 다. 단조 로 운 스 택 을 사용 하면 요 소 를 찾 아 왼쪽 으로 옮 겨 다 니 는 첫 번 째 작은 요 소 를 찾 을 수 있 고 요소 가 왼쪽으로 옮 겨 다 니 는 첫 번 째 큰 요 소 를 찾 을 수 있 습 니 다.
단조 로 운 창고 의 일부 응용
재 귀 에 관 한 생각 들
DFS 는 깊이 우선, BFS 는 넓이 우선
- 그러면 이 두 가지의 차 이 는 무엇 일 까요?
- 깊이 를 우선 적 으로 옮 겨 다 니 면 보통 한 길 을 내 려 가 고 다시 거 슬러 올 라 가지 않 는 다. 흔히 볼 수 있 는 실현 방식 은 바로 재 귀 이다. 재 귀 는 먼저 한 길 을 내 려 가 고 조건 을 만족 시 키 지 못 하면 다시 거 슬러 올 라 가 는 것 이다.광범 위 한 우선 검색 은 계층 분석 을 우선 하 는 검색 이다. 일반적인 실현 방식 은 양단 대기 열 을 사용 하 는 것 이다. 한 노드 에 접근 할 때 그 부근의 노드 를 대기 열 에 넣 고 이 를 반복 하 는 것 은 층 차 를 밖으로 펼 치 는 것 과 같다. 여 기 는 leetcode 에서 기계 인의 운동 범위 한 문제 의 해법 을 참고 할 수 있다.
빠 른 배열 과 병합 의 사고.
빠 른 배열 과 병합 은 두 가지 상 반 된 과정 이다. 하 나 는 위 에서 아래로, 다른 하 나 는 아래 에서 위로 하기 때문에 대응 하 는 절차 도 반대 이다. 빠 른 배열 은 먼저 처리 한 다음 에 재 귀 하 는 것 이 고, 병합 은 먼저 재 귀 재 처리 하 는 것 이다.
여기 뚜렷 한 프로그램 이 있어 요. - 빠 른 배열 + 병합.
하프 만 나무
원래 가장 짧 은 문자 인 코딩 을 위해 디자인 된 것 으로 확률 에 따라 분할 되 었 고 모든 문자 (변수) 는 잎 노드 이기 때문에 서로 다른 문자 간 의 인 코딩 은 존재 할 수 없다. 예 를 들 어 한 명 을 추가 하면 i 는 다른 문자 이 고 모든 문 자 는 독립 적 인 것 이다. 하 프 만 트 리 원리 와 구조 방법 이다.
욕심 산법
욕심 산법 의 몇 가지 사례 는 모두 수학 표현 식 을 통 해 미 룰 수 있다.
특수 정렬 알고리즘
O (N) 복잡 도의 정렬 알고리즘 이 있 는데 그 중에서 계수 정렬, 기수 정렬, 통 정렬 이 있 습 니 다. 그 중에서 leetcode 164 최대 간격 에서 이 몇 가지 알고리즘 은 응용 되 었 습 니 다. 그 중에서 기수 정렬 은 계수 정렬 에 비해 사용 하 는 공간 이 상대 적 으로 적 고 보통 10 * 비트 크기 만 사용 하면 되 며 계수 정렬 은 큰 공간 (bitmap 의 사상 과 비슷 합 니 다) 이 필요 합 니 다.
동적 계획
주로 상태 전이 행렬 을 찾 는 것 이다. 할 때 의문 은 행렬 을 옮 기 는 매개 변수 가 무엇 인지, 1 차원 인지, 2 차원 인지 하 는 것 이다. 이런 것들 을 해결 하면 된다.근본적으로 말 하면 동태 계획 은 매 거 진 것 이 고 중복 되 지 않 는 매 거 진 것 에 불과 하 다.
구현 세부 사항:
1. python 이 목록 을 추가 할 때 값 이 비어 있 거나 append (list (A) 가 필요 합 니 다. 이것 은 append 가 인용 만 추가 하고 복사 하지 않 았 기 때 문 입 니 다. 인용 대상 이 바 뀌 었 을 때 해당 하 는 값 도 바 뀌 기 때 문 입 니 다.자료 링크
2. 예 를 들 어 한 함수 에서 다른 내부 함 수 를 정의 합 니 다. 내부 함수 에서 외부 함수 가 정의 하 는 변 수 를 사용 하려 면 두 가지 상황 이 있 습 니 다. 목록 등에 대해 외부 함수 에서 직접 정의 하면 내부 함수 에서 사용 할 수 있 습 니 다. 일반적인 변 수 는 외부 함수 에서 정의 하거나 init 함수 에서 정의 해 야 합 니 다. 그리고 self 를 추가 해 야 사용 할 수 있 습 니 다.
3. BFS 와 DFS 의 용법 은 매우 비슷 하 다. 흔히 볼 수 있 는 DFS 는 두 가지 실현 이 있 는데 그것 이 바로 재 귀 방식 과 교체 방식 (비 재 귀) 이다. 그 중에서 재 귀 방식 은 아무런 문제 가 없고 템 플 릿 을 직접 하면 된다. 그러나 교체 방식 도 목록 을 사용 하 는 방식 이다. BFS 와 의 주요 한 차이 점 은 DFS 의 stack 은 직접 꼬리 부분 에 추가 한 다음 에 꼬리 부분 pop 이다.그러나 BFS 가 머리 에서 진행 하 는 pop (0) (또는 사용 하 는 popleft) (이 두 가지 교체 방식 은 저 는 개인 적 으로 list 를 바탕 으로 이 루어 진 것 입 니 다). 곰 곰 이 생각해 보면 이런 효과 입 니 다. 교체 방식 을 바탕 으로 하 는 두 가지 방법 으로 전환 하 는 것 이 특히 편리 합 니 다.
4. list 에 서 는 reove 를 사용 하 는 시간 보다 pop 을 사용 하 는 것 이 더 짧 습 니 다. reove 를 사용 하면 시간 을 초과 할 수 있 습 니 다. list 에 서 는 색인 이 경 계 를 넘 으 면 빈 배열 입 니 다. 호출 하지 않 으 면 잘못 보고 하지 않 습 니 다.
5. 두 갈래 검색 트 리 의 좌우 하위 트 리 는 질서 가 있 습 니 다. 정렬 하려 면 중간 순서 로 옮 겨 다 니 기
문제 풀이 순서:
먼저 나 무 를 다 닦 고 나무의 사상 과 구 조 를 이해 하고 파악 한다.
그 다음 에 labuladong 의 각 시 리 즈 를 볼 수 있 습 니 다. 반드시 실제 코드 를 써 야 합 니 다. 많은 세부 사항 이 있 습 니 다. 예 를 들 어 2 분 검색, 2 분 검색 좌우 경계 등 입 니 다.
자료:
labuladong 의 github
음 설 명 초 블 로그, 1K + 문제, 그리고 문제 템 플 릿
위의 군주 들 이 세운 서 체 의 카드 놀이 와 교 류 를 감독 하 는 곳
오류 가 발생 하기 쉬 우 며 고주파 관련 코드:
#********************************************************
앞 순 서 를 편력 하 다.
#********************************************************
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
#
if not root: return
stack, res = [], []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return res
#********************************************************
중간 순서 로 옮 겨 다 닌 다.
#********************************************************
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
stack, res = [], []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
#********************************************************
뒤 순 서 를 옮 겨 다 닌 다.
#********************************************************
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
# ，
if not root: return
stack, res = [], []
stack = [(root, False)]
while stack:
node, visited = stack.pop()
if visited:
res.append(node.val)
else:
stack.append((node, True))
if node.right: stack.append((node.right, False))
if node.left: stack.append((node.left, False))
return res
#********************************************************
빠 른 정렬
#********************************************************
def partition(nums, start, end):
if len(nums)<=1 or start>=end: return
node = nums[end]
left = start
right = end - 1
while left <= right: # +
while left<=right and nums[left]<=node: left +=1
while left<=right and nums[right]>=node: right -=1
if left<=right: # ，
nums[left], nums[right] = nums[right], nums[left]
nums[left], nums[end] = nums[end], nums[left]
return left
def quick_soret(nums, start, end):
if len(nums)<=1 or start>=end: return
left = partition(nums, start, end)
quick_soret(nums, start, left-1)
quick_soret(nums, left+1, end)
#********************************************************
정렬
#********************************************************
실제 적 으로 쓸 때 는 빠 른 정렬 과 달리 색인 을 사용 하지 않 고 색인 을 사용 하 는 것 이 오히려 번거롭다.
def merge_core(left, right):
i, j = 0, 0
result = []
if not left: return right # ，
if not right: return left
while i<len(left) and j<len(right):
if left[i]<=right[j]:
result.append(left[i])
i+=1
else:
result.append(right[j])
j+=1
result += left[i:]
result += right[j:]
return result
def merge(nums):
if len(nums)<=1:
return nums
index = len(nums)//2
left = merge(nums[:index])
right = merge(nums[index:])
return merge_core(left, right)
#********************************************************
이분법 으로 좌우 경계 획득
#********************************************************
def get_left_index(nums, target):
left, right = 0, len(nums)-1
while left<=right:
mid = left+(right-left)//2
if target<=nums[mid]:
right = mid-1
else:
left = mid+1
print(left)
def get_right_index(nums, target):
left, right = 0, len(nums)-1
while left<=right:
mid = left+(right-left)//2
if target<nums[mid]:
right = mid-1
else:
left = mid+1
print(right)
```
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
error 함수()error Display message and abort function. error(MSGID, ERRMSG, V1, V2, …) displays a descriptive message ERRMSG when the...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
