大多是 max_heap 和 min_heap 的配合使用。在用索引获取堆顶元素时，注意保证 heap 非空。

In many problems, where we are given a set of elements such that we can divide them into two parts. To solve the problem, we are interested in knowing the largest element in one part and the smallest element in the other part. This pattern is an efficient approach to solve such problems.

This pattern uses Two Heaps to solve these problems; A max heap to find the largest element and a min heap to find the smallest element.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class MedianFinder:
    def __init__(self):
        self.max_heap = []
        self.min_heap = []

    def add_num(self, num: int) -> None:
        if not self.max_heap or num <= -self.max_heap[0]:
            heappush(self.max_heap, -num)
        else:
            heappush(self.min_heap, num)
        
        # rebalance
        if len(self.max_heap) > len(self.min_heap) + 1:
            heappush(self.min_heap, -heappop(self.max_heap))
        if len(self.min_heap) > len(self.max_heap):
            heappush(self.max_heap, -heappop(self.min_heap))

    def find_median(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        
        return -self.max_heap[0]

LeetCode

295. Find Median from Data Stream
480. Sliding Window Median
502. IPO
436. Find Right Interval

重点掌握左右子树相关和不相关时，两种递归代码的写法。

This pattern is based on the Depth-First Search (DFS) technique to traverse a tree.

We will be using recursion (or we can also use a stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing. This also means that the space complexity of the algorithm will be O(H), where “H” is the maximum height of the tree.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

"""L&R Unrelated"""
def dfs(root, path):
    if not root:
        return
    
    path = path + [root.val]
    if not root.left and not root.right and sum(path) == targetSum:
        ans.append(path)
    
    dfs(root.left, path)
    dfs(root.right, path)

ans = []
dfs(root, [])

return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

"""L&R Related"""
def dfs(root):
    if not root:
        return 0
    
    l = max(0, dfs(root.left))
    r = max(0, dfs(root.right))

    nonlocal ans
    ans = max(ans, l + r + root.val)

    return max(l, r) + root.val

ans = root.val
dfs(root)

return ans

LeetCode

112. Path Sum
113. Path Sum II
129. Sum Root to Leaf Numbers
1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
437. Path Sum III
543. Diameter of Binary Tree
124. Binary Tree Maximum Path Sum

基本就是 deque 一把梭，不过需要单纯处理 root 为 None 的情况。借助同层节点的 index 可实现更细微的操作。

This pattern is based on the Breadth-First Search (BFS) technique to traverse a tree.

Any problem involving the traversal of a tree in a level-by-level order can be efficiently solved using this approach. We will use a queue to keep track of all the nodes of a level before we jump onto the next level. This also means that the space complexity of the algorithm will be O(W), where “W” is the maximum number of nodes on any level.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

if not root:
    return

queue = deque([root])
while queue:
    curr_len = len(queue)
    for idx in range(curr_len):
        node = queue.popleft()
        if idx != curr_len - 1:
            node.next = queue[0]

        # bfs
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

return root

LeetCode

102. Binary Tree Level Order Traversal
107. Binary Tree Level Order Traversal II
103. Binary Tree Zigzag Level Order Traversal
637. Average of Levels in Binary Tree
111. Minimum Depth of Binary Tree
429. N-ary Tree Level Order Traversal
117. Populating Next Right Pointers in Each Node II
116. Populating Next Right Pointers in Each Node
199. Binary Tree Right Side View

除了掌握反转链表的写法外，设置哨兵节点（前一个节点）、由远及近地处理 next pointer 也很重要。

In a lot of problems, we are asked to reverse the links between a set of nodes of a linked list. Often, the constraint is that we need to do this in-place, i.e., using the existing node objects and without using extra memory.

In-Place Reversal of a Linked List pattern describes an efficient way to solve the above problem.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

dummy, dummy.next = ListNode(), head  # set sentinel
ptr = dummy

for _ in range(left - 1):
    ptr = ptr.next

prev, curr = None, ptr.next
for _ in range(right - left + 1):
    curr.next, prev, curr = prev, curr, curr.next

# link
ptr.next.next = curr
ptr.next = prev

return dummy.next

LeetCode

206. Reverse Linked List
92. Reverse Linked List II
25. Reverse Nodes in k-Group
2074. Reverse Nodes in Even Length Groups
61. Rotate List

常用但鲜为人知的循环排序。核心理念是：将元素交换到正确的位置，继而获取某个 range 内缺失的数字。其中，缺失数字为索引值，已有数字为元素值。警惕 desired index 可能造成的数组越界。

This pattern describes an interesting approach to deal with problems involving arrays containing numbers in a given range. For example, take the following problem:

You are given an unsorted array containing numbers taken from the range “1” to “n”. The array can have duplicates, which means that some numbers will be missing. Find all the missing numbers.

To efficiently solve this problem, we can use the fact that the input array contains numbers in the range of “1” to “n”. For example, to efficiently sort the array, we can try placing each number in its correct place, i.e., placing “1” at index “0”, placing “2” at index “1”, and so on. Once we are done with the sorting, we can iterate the array to find all indices that are missing the correct numbers. These will be our required numbers.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

n = len(nums)

i = 0
while i < n:
    j = nums[i] - 1
    if 0 <= j < n and nums[i] != nums[j]:  # avoid index out of bounds
        nums[i], nums[j] = nums[j], nums[i]
        continue

    i += 1

for i in range(n):
    if nums[i] != i + 1:
        return i + 1

return n + 1

LeetCode

765. Couples Holding Hands
268. Missing Number
448. Find All Numbers Disappeared in an Array
287. Find the Duplicate Number
442. Find All Duplicates in an Array
645. Set Mismatch
41. First Missing Positive
1539. Kth Missing Positive Number