基本就是 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

两个区间之间存在 6 种可能情况。取交集时，start = max(a.start, b.start); end = min(a.end, b.end)。

This pattern describes an efficient technique to deal with overlapping intervals. In a lot of problems involving intervals, we either need to find overlapping intervals or merge intervals if they overlap.

Given two intervals (“a” and “b”), there will be six different ways the two intervals can relate to each other:

Understanding the above six cases will help us in solving all intervals related problems.

Snippets

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

n = len(intervals)
ans = []

i = 0
# case 1
while i < n and intervals[i][1] < newInterval[0]:
    ans.append(intervals[i])
    i += 1
# case 2-5
while i < n and intervals[i][0] <= newInterval[1]:
    newInterval[0] = min(newInterval[0], intervals[i][0])
    newInterval[1] = max(newInterval[1], intervals[i][1])
    i += 1
ans.append(newInterval)
# case 6
while i < n:
    ans.append(intervals[i])
    i += 1

return ans

LeetCode

56. Merge Intervals
57. Insert Interval
986. Interval List Intersections
435. Non-overlapping Intervals
253. Meeting Rooms II
1094. Car Pooling
759. Employee Free Time

掌握判环以及判环的变形。while 循环的条件往往是 r and r.next 存在，过程中可以顺便获取 middle pointer。

The Fast & Slow Pointers approach is a pointer algorithm that uses two pointers which move through the array (or linked list) at different speeds. This approach is quite useful when dealing with cyclic linked lists or arrays.

By moving at different speeds (say, in a cyclic linked list), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

Snippets

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

l = r = head
while r and r.next:
    l = l.next
    r = r.next.next
    if l == r:
        break
else:
    return

l = head
while l != r:
    l = l.next
    r = r.next

return l

LeetCode

141. Linked List Cycle
142. Linked List Cycle II
202. Happy Number
876. Middle of the Linked List
234. Palindrome Linked List
143. Reorder List
457. Circular Array Loop