1 Tree
1.1 Recursion
1.1 Recursion
PreOrderTraversal
https://leetcode.cn/problems/binary-tree-preorder-traversal/
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
self.res = []
def dfs(node):
if node is None:
return
self.res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return self.res
InOrderTraversal
PostOrderTraversal
二叉树的最大深度
二叉树的直径
1.2 LevelOrderTraversal
https://leetcode.cn/problems/binary-tree-level-order-traversal/
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
ans = []
from collections import deque
q = deque([root])
while q:
tmp = []
for _ in range(len(q)): # for loop [], until it's full
node = q.popleft()
tmp.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
ans.append(tmp)
return ans
https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
ans = []
from collections import deque
q = deque([root])
while q:
tmp = []
for _ in range(len(q)): # for loop [], until it's full
node = q.popleft()
tmp.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
ans.append(tmp[::-1] if len(ans)%2 else tmp)
return ans
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
if root is None:
return
from collections import deque
q = deque([root])
tmp = []
while q:
node = q.popleft()
tmp.append(node.val)
if node.right: q.append(node.right)
if node.left: q.append(node.left)
return tmp[-1]
1.3 BST
BST(Binary Search Tree)，二叉搜索树具有左子树 < Root < 右子树的性质。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def dfs(nums, lo, hi):
if lo > hi: return
# 以升序数组的中间元素作为根节点 root
mid = lo + (hi - lo) // 2
root = TreeNode(nums[mid])
root.left = dfs(nums, lo, mid - 1)
root.right = dfs(nums, mid + 1, hi)
return root
return dfs(nums, 0, len(nums)-1)
1.4 Common Ancestor
https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
2 Sliding Window
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
cnt = Counter()
left = 0
for right, c in enumerate(s): # add the new character to the s, from right
cnt[c] += 1
while cnt[c] > 1: # abcb -> bcb -> cb
cnt[s[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m, res = len(s), len(p),[]
if n < m: return res
p_cnt = [0] * 26
s_cnt = [0] * 26
for i in range(m): # initialize p_cnt
p_cnt[ord(p[i]) - ord("a")] += 1
s_cnt[ord(s[i]) - ord("a")] += 1
if s_cnt == p_cnt:
res.append(0)
for i in range(m,n): # sliding window
s_cnt[ord(s[i-m])-ord("a")] -= 1
s_cnt[ord(s[i])-ord("a")] += 1
if s_cnt == p_cnt:
res.append(i-m+1) # start index
return res
3 Prefix Sum
- 计算前缀和s，注意要初始化一个0，
- 因为s[j] - s[i] = k，所以s[j] - k = s[i]
- 每次寻找 s[j] 前面有多少个前缀和等于 s[j]−k， 用哈希表记录前缀和的个数，就能 O(1) 算出前面有多少个 s[j]−k
- 遍历前缀和s, ans += cnt[s[j] - k], cnt[s[i]] += 1，顺序不能颠倒，因为如果k=0，会多记一次
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
s = [0] * (len(nums) + 1)
for i, num in enumerate(nums):
s[i+1] = s[i] + num
ans = 0
cnt = Counter()
for sj in s:
ans += cnt[sj - k]
cnt[sj] += 1
return ans
4 Stack
class Solution:
def isValid(self, s: str) -> bool:
if len(s)%2 != 0:
return False
mp = {"}":"{", ")":"(", "]":"["}
st = []
for c in s:
if c not in mp: # c是左括号
st.append(c)
elif not st or st.pop() != mp[c]: # c是右括号
return False # 没有左括号，或右括号不匹配
return not st # 所有左括号必须匹配完毕，检查左括号比右括号多的情况，如{{}
5 Linked List
5.1 反转链表
- 初始化：pre指向null，cur指向head
- 先暂存head.next，再改变head.next，最后更新head：
- tmp = cur.next
- cur.next = pre
- pre = cur
- cur = tmp
- 必记性质：反转结束后，pre指向这一段的末尾，cur指向这一段末尾的下一个节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, cur = None, head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
5.2 快慢指针
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
- 关注fast和slow的相对运动，相当于fast相对运动一格，如果有环，最终fast肯定会与slow相遇
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast is slow:
return True
return False
- 哈希表记录遍历过的节点， 记录大于2表示有环，且为入口
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
visited = Counter()
while head:
if visited[head]:
return head
visited[head] += 1
head = head.next
return None
Follow up: Can you solve it using O(1) (i.e. constant) memory?
- 最差情况: 当慢指针进入环时，快指针刚好在慢指针前面，根据相对距离分析，快指针需要走(环长-1)步的相对距离才能追上慢指针，其余任何情况快指针走的步数都小于(环长-1)，所以慢指针移动的距离是小于环长的。
- slwo和fast相遇之后：head从出发点出发，slow从相遇点出发，head和slow相遇的位置必定是入口，这是因为设相遇点到入口的距离为c, a - c = (k - 1)(b + c)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast is slow: # 有环
while slow is not head:
slow = slow.next
head = head.next
return slow
return None
- 找到链表中点，反转链表
- 先暂存head.next，再改变head.next，最后更新head：
- tmp = head.next
- tmp2 = head2.next
- head.next = head2
- head2.next = tmp
- head = tmp
- head2 = tmp2
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head):
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
def reorderList(self, head: Optional[ListNode]) -> None:
mid = self.middleNode(head)
head2 = self.reverseList(mid)
while head2.next:
tmp = head.next
tmp2 = head2.next
head.next = head2
head2.next = tmp
head = tmp
head2 = tmp2
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head):
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if head is None:
return True
mid = self.middleNode(head)
head2 = self.reverseList(mid)
while head2:
if head.val != head2.val:
return False
head = head.next
head2 = head2.next
return True
5.3 前后指针
https://leetcode.cn/problems/intersection-of-two-linked-lists/
- 初始化：A指向headA，B指向headB，同时开始向前遍历
- 遍历: a + (b - c) = b + (a - c)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
A = headA
B = headB
while A!=B:
A = A.next if A else headB
B = B.next if B else headA
return A