lengthOfLongestSubstring (cache) O(n)

设两个指针 i 和 j：i 指向滑动窗口起点，j 指向终点。
先把 j 向右移动，遇到重复字符就停下，计算当前长度。
然后把 i 向右移动以越过那个重复字符。
用一个字典记录每个字符出现的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# O(kn)
def solution(a):
    i, j = 0, 0
    indice = {}
    ret = 0
    while j < len(a):
        if a[j] in indice:
            i = indice[a[j]]
            # reconstruct the indice map
            indice = {a[k]: k for k in range(i+1, j+1)}
        else:
            # only add the current element
            indice[a[j]] = j
        ret = max(ret, len(indice))
        j += 1
    return ret

# O(n)
def solution2(a):
    i, j = 0, 0
    indice = {}
    ret = 0
    while j < len(a):
        if a[j] in indice:
            # once we find a duplicate key
            # then valid path must be the length between these two key minus 1
            i = max(indice[a[j]], i)
        ret = max(ret, j-i+1)
        indice[a[j]] = j+1
        j += 1
    return ret


print(solution2("abcabcbb"))

findMedianSortedArrays (binary search) O(log(m+n))

      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

我们用 i 和 j 把数组 A、B 各切两半。当下面三个条件同时满足时即可拿到中位数：
- len(left_part)=len(right_part)
- max(left_part)≤min(right_part)
- median = (max(left_part) + min(right_part)) / 2

可以化简为：
- B[j−1]≤A[i] 且 A[i−1]≤B[j]
- j=(m+n+1)/2-i

对 i 做二分搜索：
- 若 B[j−1]≤A[i] 且 A[i−1]≤B[j]，找到中位数
- 若 B[j−1]>A[i]，需要把 i 向右移（二分）
- 若 A[i−1]>B[j]，需要把 i 向左移（二分）

注意：
- imin, imax, half_len = 0, m, (m+n+1)//2
- i = (imin+imax)//2, j = half_len – i
- if i < m and nums2[j-1] > nums1[i]: imin = i + 1 # binary search
- elif i > 0 and nums1[i-1] > nums2[j]: imax = i - 1 # binary search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def solution(nums1, nums2):
    m, n = len(nums1), len(nums2)
    if m > n:
        nums1, nums2, m, n = nums2, nums1, n, m
    imin, imax, half_len = 0, m, (m + n + 1) // 2
    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i
        if i > 0 and nums1[i - 1] > nums2[j]:
            imax = i - 1
        elif i < m and nums1[i] < nums2[j - 1]:
            imin = i + 1
        else:
            if i == 0:
                max_of_left = nums2[j - 1]
            elif j == 0:
                max_of_left = nums1[i - 1]
            else:
                max_of_left = max(nums1[i - 1], nums2[j - 1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m:
                min_of_right = nums2[j]
            elif j == n:
                min_of_right = nums1[i]
            else:
                min_of_right = min(nums1[i], nums2[j])

            return (max_of_left + min_of_right) / 2.

longestPalindrome (dp) O(N^2)

设两个下标，i 表示窗口长度，j 表示窗口起点，状态转移方程：

P(i, j) = P(i+1, j-1) + 2, if s[i] == s[j].

注意：

  • P(i, i) = 1
  • ‘aa’ 也是回文，所以 P(i, i+1) = 2 if s[i] = s[i+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# O(n^2)
def solution(s):
    n = len(s)
    dp = [[0] * n for i in range(n+1)]
    ret = ""
    max_len = 0
    # i is the length, j is the start position
    for i in range(1, len(s)+1):
        for j in range(len(s)-i+1):
            # case 1, single char
            if i == 1:
                dp[i][j] = 1
            # case 2, continuous smae char
            elif i == 2:
                if s[j] == s[j+1]:
                    dp[i][j] = 2
            else:
                if dp[i-2][j+1] > 0 and s[j] == s[j+i-1]:
                    dp[i][j] = dp[i-2][j+1] + 2
            if dp[i][j] > max_len:
                max_len = dp[i][j]
                ret = s[j:j+i]
    return ret

isMatch (recursive with memo) O(MN)

加备忘录避免重复检查。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(s, p):
    memo = {}
    m, n = len(s), len(p)

    def recursive(i, j):
        if (i, j) not in memo:
            if j == n:
                ans = i == m
            else:
                first_match = i < m and p[j] in (s[i], '.')
                if j + 1 < n and p[j + 1] == '*':
                    ans = recursive(
                        i, j + 2) or first_match and recursive(i + 1, j)
                else:
                    ans = first_match and recursive(i + 1, j + 1)
            memo[i, j] = ans
        return memo[i, j]

    return recursive(0, 0)

maxArea (trick) O(n)

令 i = 0，j = len(heights)-1。每次把较矮的那一根向中间移动，重新计算最大面积。因为如果下一根比当前还矮，宽度变小、高度也没增加，体积不可能更大。

注意：这题不能用 dp，因为没有最优子结构。

这个 trick 之所以成立：我们从两端往里收，宽度一直在减小，只有高度变大才有机会出现更大面积。而之所以移动较矮的那根：如果固定较矮的、移动较高的，min 高度仍然是较矮那根，面积只会随宽度减小而下降。

1
2
3
4
5
6
7
8
9
10
11
# O(n)
def solution(height):
    i, j = 0, len(height) - 1
    ret = min(height[j], height[i]) * (j-i)
    while i < j:
        ret = max(ret, min(height[i], height[j]) * (j-i))
        if height[i] < height[j]:
            i += 1
        else:
            j -= 1
    return ret

(mark) threeSum (trick) O(n^2)

先排序，然后三指针 i, j, k。固定 i 后，j = i+1，k = n-1，目标是让 nums[j] + nums[k] = -nums[i]：和偏小就 j++，和偏大就 k--（因为已排序）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# O(n^2) sort
def solution(nums):
    n = len(nums)
    nums.sort()
    ret = []
    for i in range(n-2):
        if i > 0 and nums[i] == nums[i-1]: # avoid repeat
            continue
        j, k = i+1, n-1
        while j < k:
            s = nums[i] + nums[j] + nums[k]
            if s < 0:
                j += 1
            elif s > 0:
                k -= 1
            else:
                ret.append([nums[i], nums[j], nums[k]])
                while j < k and nums[j] == nums[j+1]: # avoid repeat
                    j += 1
                while j < k and nums[k] == nums[k-1]: # avoid repeat
                    k -= 1
                j += 1
                k -= 1
    return ret

letterCombinations (full permutation), O(3^N * 4^M)

直接递归：每层枚举当前数字对应的所有字符，调用下一层递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
phone = {'2': ['a', 'b', 'c'],
         '3': ['d', 'e', 'f'],
         '4': ['g', 'h', 'i'],
         '5': ['j', 'k', 'l'],
         '6': ['m', 'n', 'o'],
         '7': ['p', 'q', 'r', 's'],
         '8': ['t', 'u', 'v'],
         '9': ['w', 'x', 'y', 'z']}


def solution(digits):
    ret = []
    if not digits:
        return ret

    def recursion(prefix, digits):
        if not digits:
            ret.append(prefix)
        else:
            for c in phone[digits[0]]:
                recursion(prefix+c, digits[1:])
    recursion("", digits)
    return ret

removeNthFromEnd (trick) O(n)

双指针 p, q：先让 p 向前走 n 步，再让两个指针一起走，当 p 走到末尾时，q 正好停在倒数第 n 个节点。

1
2
3
4
5
6
7
8
9
10
11
12
def solution(head, n):
    t = ListNode(None)
    t.next = head
    p = t
    q = t
    for _ in range(n):
        p = p.next
    while p.next:
        q = q.next
        p = p.next
    q.next = q.next.next
    return t.next

generateParenthesis (recursive) O(4^n/√2)

用计数器 n 记录还可用的左括号数量，k 记录已经放下、待匹配的左括号数量。
- n == 0 且 k == 0：输出
- n == 0 且 k > 0：recursive(n, k-1)，加 ‘)’
- n > 0 且 k == 0：recursive(n-1, k+1)，加 ‘(‘
- 否则两个分支都试：recursive(n-1, k+1) 加 ‘(‘ 和 recursive(n, k-1) 加 ‘)’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(n):
    ret = []
    if n == 0:
        return ret

    def recursion(prefix, i, j):
        # i means the assigned number of "(" and don't have ")"
        # j means the available number of "("
        if i==0 and j == 0:
            ret.append(prefix)
        elif i == 0:
            recursion(prefix+"(", i+1, j-1)
        elif j == 0:
            recursion(prefix+")", i-1, j)
        else:
            recursion(prefix+"(", i+1, j-1)
            recursion(prefix+")", i-1, j)

    recursion("", 0, n)
    return ret

nextPermutation (trick), O(n)

j = len(n)-1，i = len(n)-2。从后往前找 i，一旦发现 n[i] < n[j]，就交换 n[i] 与 n[j]，然后把 n[i:j+1] 反转。

要点：从末尾扫描，找到第一个”变小”的位置就把这两个值之间整段反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i + 1] <= nums[i]:
        i -= 1
    if i >= 0:
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = nums[:i:-1]
    else:
        nums[::] = nums[::-1]

longestValidParentheses

longestValidParentheses (stack trick) O(n)

核心想法：当遇到 ‘)’（栈非空）时，需要知道这一段合法子串从哪里开始 —— 把”开始位置”压栈即可。

每当遇到一个无效字符（仍需要 pop）或者一个 ‘(‘，就把当前位置入栈。这样以后再碰到 ‘)’，先 pop，栈顶 stack[-1] 就是当前合法子串的起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# dp O(n)
def solution(s):
    max_ret = 0
    stack = [-1]
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            stack.pop()
            if len(stack) == 0:
                stack.append(i) # last invalid point
            else:
                max_ret = max(max_ret, i - stack[-1]) # i-stack[-1] is current valid length
    return max_ret

# dp O(n)
def solution(s):
    ret = 0
    dp = [0] * len(s)
    for i in range(1, len(s)):
        if s[i] == ")":
            if s[i - 1] == "(":
                dp[i] = (dp[i - 2] if i > 1 else 0) + 2
            elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == "(":
                dp[i] = dp[i-1] + 2 + \
                    (dp[i-dp[i-1]-2] if i-dp[i-1]-2 > 0 else 0)
        ret = max(ret, dp[i])
    return ret

(mark) longestValidParentheses (dp) O(n)

dp[i] 表示以 i 结尾的最长合法子串长度。合法子串总以 ‘)’ 结尾，所以：
- s[i-1, i] = ‘()’：dp[i] = dp[i-2] + 2（dp[i-1]=0）
- s[i-1, i] = ‘))’：检查 s[i-dp[i-1]-1]（也就是上一个合法子串前面那个字符）是否为 ‘(‘。如果是，dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2 —— 即”上一个合法子串”+”再之前的合法子串”+”配对的两个括号”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# dp O(n)
def solution(s):
    ret = 0
    dp = [0] * len(s)
    for i in range(1, len(s)):
        if s[i] == ")":
            print(s[i], i, dp[i-1])
            if s[i-1] == "(":
                dp[i] = (dp[i-2] if i > 1 else 0) + 2
            elif i-dp[i-1] > 0 and s[i-dp[i-1]-1] == "(":
                dp[i] = dp[i-1] + 2 + \
                    (dp[i-dp[i-1]-2] if i-dp[i-1]-2 > 0 else 0)
        ret = max(ret, dp[i])
    return ret

(mark) search (binary search trick) O(log n)

举例：输入 [4, 5, 6, 7, 0, 1, 2]，s = 0，e = n-1，m = (s+e)//2。

考虑四种情况：
- 旋转点在右边、目标在左半段：nums[s] <= target < nums[m] → recursive(s, m-1)
- 旋转点在左边、目标在右半段：nums[m] < target <= nums[e] → recursive(s+1, m)
- 旋转点在右边、目标在右边：nums[m] > nums[e] → recursive(m+1, e)
- 旋转点在左边、目标在左边：nums[s] > nums[m] → recursive(s, m-1)

第三种情况隐含一个条件：若 nums[m] > nums[e]，则旋转点必在右边，因此 nums[s] 必小于 nums[m]。这种情况下只需检查目标是否落在右段；若落在左段，会被第一种情况捕获。第四种情况同理。

而且这种递归不会破坏旋转数组的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(nums, target):
    if not nums:
        return -1

    def recursion(i, j):
        if j < i:
            return -1
        m = (i+j)//2
        if nums[m] == target:
            return m
        # target locates at non-axis side (and is left side)
        elif nums[i] <= target < nums[m]:
            return recursion(i, m-1)
        # target locates at non-axis side (and is right side)
        elif nums[m] < target <= nums[j]:
            return recursion(m+1, j)
        # target locates at axis side (and is right side)
        elif nums[m] > nums[j]:
            return recursion(m+1, j)
        # target locates at axis side (and is left side)
        else:
            return recursion(i, m-1)
    return recursion(0, len(nums)-1)

searchRange (Binary Search trick) O(log n)

两次二分：一次找左边界，一次找右边界。

魔改普通二分：找到 target 时不停下，继续向另一侧搜索。当 right_index < left_index 时，左边界搜索返回 left_index，右边界搜索返回 right_index。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(nums, target):
    def recursiveLeft(s, e):
        if e < s:
            return s
        m = (s+e)//2
        if nums[m] < target:
            return recursiveLeft(m+1, e)
        else:
            return recursiveLeft(s, m-1)

    def recursiveRight(s, e):
        if e < s:
            return e
        m = (s+e)//2
        if nums[m] <= target:
            return recursiveRight(m+1, e)
        else:
            return recursiveRight(s, m-1)

    left, right = recursiveLeft(0, len(nums)-1), recursiveRight(0, len(nums)-1)
    # once we cannot found the value, the left will right-1
    return [left, right] if left <= right else [-1, -1]

combinationSum (dfs) O(exponential)

外面套个 for 循环依次调用递归即可。

1
2
3
4
5
6
7
8
9
10
11
12
def solution(candidates, target):
    ret = []

    def recursion(prefix, i, target):
        if target == 0:
            ret.append(prefix)
        for i in range(i, len(candidates)):
            num = candidates[i]
            if target - num >= 0:
                recursion(prefix+[num], i, target-num)
    recursion([], 0, target)
    return ret

firstMissingPositive (trick: hash with mod position) O(n)

最大挑战是只能用常数额外空间，不能开 O(n) 哈希表。因此用输入数组本身充当哈希表。

做法：先把所有 <0 或 >=n 的位置置 0，然后 nums[nums[i] % n] += n，用这种方式标记某个 bin 已经出现过。最后遍历，第一个值仍小于 n 的下标就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(nums):
    nums.append(0) # very important, for example, [1]
    n = len(nums)
    for i in range(n):  # delete those useless elements
        if nums[i] < 0 or nums[i] >= n:
            nums[i] = 0
    # use the index as the hash to record the frequency of each number
    for i in range(n):
        nums[nums[i] % n] += n # +n and %n to make the original value do not be overlaped
    for i in range(1, n):
        if nums[i] < n:
            return i
    return n

Trap (two dp, left and right) O(n)

两个 dp 数组：分别记录从左、从右两个方向看过来的最大高度。
- dp_l[i] = max(dp_l[i-1], height[i])
- dp_r[i] = max(dp_r[i+1], height[i])

每个坑的水量 = min(dp_l[i], dp_r[i]) - height[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(height):
    height = [0] + height + [0]
    n = len(height)
    ret = 0
    max_left = [0] * n  # record the max height from left
    max_right = [0] * n  # record the max height from right
    cur_max = height[0]
    for i in range(n):
        cur_max = max(cur_max, height[i])
        max_left[i] = cur_max
    cur_max = height[-1]
    for i in range(n-1, -1, -1):
        cur_max = max(cur_max, height[i])
        max_right[i] = cur_max
        ret += min(max_left[i], max_right[i]) - height[i]
    return ret

Permute (loop call recusive) O(2^n)

1
2
3
4
5
6
7
8
9
10
11
12
def solution(nums):
    ret = []
    n = len(nums)

    def recursion(prefix, remaining):
        if not remaining:
            ret.append(prefix)
        else:
            for k in range(len(remaining)):
                recursion(prefix+[remaining[k]], remaining[:k] + remaining[k+1:])
    recursion([], nums)
    return ret

Rotate (trick) O(n^2)

先反转再转置（reverse + transpose）。

1
2
3
4
5
6
7
8
9
10
11
12
def solution(matrix):
    n = len(matrix)
    i, j = 0, n - 1
    # swap
    while i < j:
        matrix[i], matrix[j] = matrix[j], matrix[i]
        i += 1
        j -= 1
    # transpose
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

(mark) groupAnagrams (hash) O(m)

用 collections.defaultdict(list)，把 tuple(sorted(s)) 作为哈希 key。

1
2
3
4
5
6
7
from collections import defaultdict

def solution(strs):
    ret = defaultdict(list)
    for s in strs:
        ret[tuple(sorted(s))].append(s)
    return list(ret.values())

** 必须用 sorted(s)；用 set(s) 不行（会丢失字符频次）。

(mark) maxSubArray (trick) O(n)

从左到右扫一遍，用一个累计 sum：只要左边累计是正的就保留，否则把累计的负值丢弃从头开始。

转移：nums[i] = max(0, nums[i-1]) + nums[i]

每段连续正子串里取最大：ret = max(ret, nums[i])。

1
2
3
4
5
6
7
def solution(nums):
    cur_sum = 0
    max_v = - sys.maxsize
    for num in nums:
        cur_sum = max(0, cur_sum) + num
        max_v = max(max_v, cur_sum)
    return max_v

canJump (greedy) O(n)

从左往右扫，维护”当前能到达的最远位置”。每遇到新位置就更新。能到末尾就返回 true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(nums):
    m = 0
    for i in range(0, len(nums)):
        if i > m:
            return False
        m = max(m, i+nums[i])
    return True

def solution(nums):
    i, max_i = 0, 0
    while i <= max_i and i < len(nums) and max_i < len(nums)-1:
        max_i = max(max_i, i+nums[i])
        i += 1
    return max_i >= len(nums) - 1

merge (greedy) O(n)

先按起点排序，然后维护一个结果数组：每次检查上一个区间的右端点是否 ≥ 当前区间的左端点，如果是就合并，否则直接 append。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

def solution(intervals):
    intervals.sort(key=lambda x: x[0])
    ret = []
    while intervals:
        interval_1 = intervals.pop(0)
        if intervals and interval_1[1] >= intervals[0][0]:
            intervals[0][0] = interval_1[0]
            intervals[0][1] = max(intervals[0][1], interval_1[1])
        else:
            ret.append(interval_1)
    return ret

uniquePaths (dp) O(m+n)

dp[i][j] = dp[i][j-1] + dp[i-1][j]

1
2
3
4
5
6
7
8
9
10
def solution(m, n):
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
    return dp[-1][-1]

minPathSum (dp) O(mn)

dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + m[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
def solution(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[-1][-1]

climbStairs (dp) O(n)

dp[i] = dp[i-1] + dp[i-2], dp[0]=1, dp[1] = 1

1
2
3
4
5
6
7
8
9
def solution(n):
    if n == 1:
        return 1
    dp = [0] * n
    dp[0], dp[1] = 1, 2
    for i in range(2, n):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[-1]

(mark) minDistance (dc) O(mn)

定义递归 recursive(word1, word2, i, j, memo) 返回 word1[i:] 转成 word2[j:] 所需的最少操作数，用 memo 缓存子问题。

若 word1[i] == word2[j]：memo[i][j] = recursive(word1, word2, i+1, j+1, memo)。否则有三种操作：
- insert = 1 + recursive(word1, word2, i, j+1, memo)：在 word1[i] 前插入 word2[j]，使两端字符相等，然后比较 word1[i] 与 word2[j+1]。
- delete = 1 + recursive(word1, word2, i+1, j, memo)：删掉 word2[j]，比较 word1[i+1] 与 word2[j]。
- replace = 1 + recursive(word1, word2, i+1, j+1, memo)：用 word2[j] 替换 word1[i]，再比较 word1[i+1] 与 word2[j+1]。

memo[i][j] = min(insert, delete, replace)。

终止条件：i == m && j == n 时已处理完两个字符串，返回 0；i == m 时返回 n - j；j == n 时返回 m - i（剩下的字符全靠插入）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(word1, word2):
    memo = {}
    n, m = len(word1), len(word2)
    if m < n:
        word1, word2, m, n = word2, word1, n, m

    def recursive(i, j):
        if (i, j) not in memo:
            if i == n:
                ans = m - j
            elif j == m:
                ans = n - i
            else:
                if word1[i] == word2[j]:
                    ans = recursive(i + 1, j + 1)
                else:
                    # insert, delete, replace
                    ans = min(recursive(i, j + 1), recursive(i + 1, j),
                              recursive(i + 1, j + 1)) + 1
            memo[i, j] = ans
        return memo[i, j]

    return recursive(0, 0)

sortColors (trick) O(n)

三指针 i, j, k：i 与 j 圈定待处理范围，k 指向当前处理的值。nums[k] 三种情况：
- nums[k] == 0：交换 nums[i] 与 nums[k]，i+=1，k+=1
- nums[k] == 1：什么都不做，k+=1
- nums[k] == 2：交换 nums[j] 与 nums[k]，j-=1

实际上 i 标识 0 区间的末尾，j 标识 2 区间的开头：每次遇到 0 就把它换到 0 区间末尾，遇到 2 就换到 2 区间开头，最后中间留下的全是 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(nums):
    n = len(nums)
    i, j, k = 0, 0, n-1
    while i <= k:
        if nums[i] == 0:
            if i != j:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1
            else:
                j += 1
                i += 1
        elif nums[i] == 2:
            nums[i], nums[k] = nums[k], nums[i]
            k -= 1
        else:
            i += 1
    return nums

minWindow (trick hash) O(n)

双指针 i, j 维护滑动窗口。哈希表 m 像一个”平衡钱包”：先把 T 中的字符加进去，遍历 S 时再扣除。m[c] > 0 表示这个字符还需要找；m[c] < 0 表示这个字符已经超额（出现次数比 T 中需要的还多）。再用 count = len(T) 记录还有多少字符要找。

向右移 j：m[s[j]] -= 1；只有当 m[s[j]] > 0（说明命中了一个真正需要的字符）时才 count -= 1。当 count == 0 表示窗口包含了 T 的所有字符，开始向右移 i 缩小窗口：每次 m[s[i]] += 1，若 m[s[i]] > 0（说明丢掉了一个真正需要的字符）才 count += 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
def minWindow(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: str
    """
    import sys
    import collections
    m = collections.defaultdict(int)
    # m just like a balance wallet
    # we first add chars of T into it
    # then once we encounter chars in S
    # we minus from m
    # so for m>0 menas there is still char we need to find
    # m<0 means we remove much more than we need in T
    for c in t:
        m[c] += 1
    j = 0

    # identify how many remaining chars in T we still need to find
    count = len(t)
    minLen = sys.maxsize
    minStart = 0
    for i in range(len(s)):
        # only when m[s[i]] > 0, means remaining chars in t
        if m[s[i]] > 0:
            count -= 1
        m[s[i]] -= 1
        # we have found all chars in T, we start to move j
        while count == 0:
            if (i - j + 1) < minLen:
                minLen = i-j+1
                minStart = j
            m[s[j]] += 1
            # when m[s[i]] > 0, means we remove too much target chars
            # we increase count to mark there are chars we need to find
            if m[s[j]] > 0:
                count += 1
            j += 1

    if minLen < sys.maxsize:
        return s[minStart:minStart+minLen]
    return ""

def solution(s, t):
    from collections import Counter
    import sys

    n = len(s)
    i, j = 0, 0
    c_t = Counter(t)
    count = len(t)
    b, l = 0, sys.maxsize
    while j < n:
        if c_t[s[j]] > 0:
            count -= 1
        c_t[s[j]] -= 1

        while not count:
            if (j-i+1) < l:
                l = j-i+1
                b = i
            c_t[s[i]] += 1
            if c_t[s[i]] > 0:
                count += 1
            i += 1
        j += 1
    if l < sys.maxsize:
        return s[b:b+l]
    return ""

Subsets (dfs) O(2^n)

跟全排列类似，但中间节点也要输出。

1
2
3
4
5
6
7
8
9
10
def solution(nums):
    n = len(nums)
    ret = []

    def recursion(prefix, i):
        ret.append(prefix)
        for j in range(i, n):
            recursion(prefix+[nums[j]], j+1)
    recursion([], 0)
    return ret

(mark) Exist (dfs) O(mn * len(words))

定义递归 dfs(row, col, idx)：从 nums[row][col] 开始匹配 word[idx:]。遍历每个 cell，仅当其等于 word[0] 时调用 dfs。

dfs 内：若 idx == len(word) 返回 True；否则向四个方向探索，若邻居等于 word[idx] 就递归下去；都失败则返回 False。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(board, word):
    m, n = len(board), len(board[0])

    def recursion(i, j, idx):
        if idx == len(word):
            return True
        board[i][j] = "#"
        if i+1 < m and board[i+1][j] == word[idx] and recursion(i+1, j, idx+1):
            return True
        if j+1 < n and board[i][j+1] == word[idx] and recursion(i, j+1, idx+1):
            return True
        if i-1 >= 0 and board[i-1][j] == word[idx] and recursion(i-1, j, idx+1):
            return True
        if j-1 >= 0 and board[i][j-1] == word[idx] and recursion(i, j-1, idx+1):
            return True
        board[i][j] = word[idx-1]
        return False

    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0] and recursion(i, j, 1):
                return True
    return False

largestRectangleArea (left and right dp) O(n)

两个数组 left_min、right_min 分别记录左右两侧第一个比当前更矮的位置。每个矩形面积 = height[i] * (right_min[i] - left_min[i] - 1)。

left_min[0] = -1。计算 left_min[i] 时从 j = i-1 开始，发现 height[j] >= height[i] 就跳到 j = left_min[j]，递归往前找更矮的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(heights):
    heights = [0] + heights + [0]
    n = len(heights)
    min_left = [0] * n
    min_right = [0] * n
    ret = 0
    for i in range(1, n - 1):
        tmp_i = i - 1
        while tmp_i > 0 and heights[tmp_i] >= heights[i]:
            tmp_i = min_left[tmp_i]
        min_left[i] = tmp_i
    for j in range(n - 2, 0, -1):
        tmp_j = j + 1
        while tmp_j < n - 1 and heights[tmp_j] >= heights[j]:
            tmp_j = min_right[tmp_j]
        min_right[j] = tmp_j
    for i in range(1, n - 1):
        ret = max(ret, heights[i] * (min_right[i] - min_left[i] - 1))
    return ret

maximalRectangle (greedy) O(mn)

三个数组分别记录最远高度、最远左边界、最远右边界。

height：
- matrix[i][j] == ‘1’ → height[j] += 1，否则 height[j] = 0

left：
- matrix[i][j] == ‘1’ → left[j] = max(left[j], cur_left)，否则 left[j] = 0，cur_left = j+1

right：
- matrix[i][j] == ‘1’ → right[j] = min(right[j], cur_right)，否则 right[j] = n，cur_right = j

流程：先确定矩形高度，再找它的最远左右边界。cur_left 记录当前行的最远左边界，left[j] 记录所有行的最远左边界，max(left[j], cur_left) 给出当前行内矩形的最远左边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def solution(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    left, right, height = [0] * n, [n] * n, [0] * n
    max_v = 0
    for i in range(m):
        cur_left, cur_right = 0, n
        for j in range(n):
            if matrix[i][j] == '1':
                height[j] += 1
                left[j] = max(left[j], cur_left)
            else:
                height[j] = 0
                left[j] = 0
                cur_left = j + 1
            j = n - j - 1
            if matrix[i][j] == '1':
                right[j] = min(right[j], cur_right)
            else:
                right[j] = n
                cur_right = j
        for j in range(n):
            max_v = max(max_v, (right[j] - left[j]) * height[j])
    return max_v

inorderTraversal (iterative) O(n)

用栈：每次 pop 一个节点，把它的子节点按 (node.left, node.val, node.right) 顺序入栈；pop 出整数就直接输出。

另一种写法：先一路把左节点压栈到最左叶子；每次 pop 一个节点输出，然后递归地把它右子节点的左链压栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def solution(root):
    ret = []

    def recursion(root):
        if not root:
            return
        recursion(root.left)
        ret.append(root.val)
        recursion(root.right)
    recursion(root)
    return ret


def solution(root):
    ret = []
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        elif isinstance(node, int):
            ret.append(node)
        else:
            stack.extend([node.right, node.val, node.left])
    return ret

numTrees (dp) O(n^2)

定义两个函数：
- G(n)：长度为 n 的序列能形成的 BST 数量
- F(i, n)，1 ≤ i ≤ n：以 i 为根、序列范围 1~n 的 BST 数量

那么 G(n) = F(1, n) + F(2, n) + … + F(n, n)，且 G(0) = G(1) = 1。

注意 F(i, n) = G(i-1) * G(n-i)。

合起来：

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)。

从 G(2) 开始：G(2) = G(0) * G(1)，G(3) = G(0) * G(2) + G(1) * G(1) + G(2) * G(0)，… 最终得 G(n)。

一开始想用 2D dp，但发现起点终点不重要、只看子问题长度，所以用 1D dp 就够了。

1
2
3
4
5
6
7
def solution(n):
    dp = [0] * (n+1)
    dp[0] = dp[1] = 1
    for i in range(2, n+1):
        for j in range(1, i+1):
            dp[i] += (dp[j-1]*dp[i-j])
    return dp[-1]

isValidBST (post-order, dfs) O(n)

解法 1（自底向上）：返回每个子树的 max 和 min。合法节点要求：节点值 > 左子树 max，且 < 右子树 min。

解法 2（自顶向下）：维护合法值域 (low, upper)。进入左子树时收紧上界，进入右子树时收紧下界。

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(root):
    if not root:
        return True

    def recursion(root, min_v, max_v):
        if not root:
            return True
        elif root.val <= min_v or root.val >= max_v:
            return False
        else:
            return recursion(root.left, min_v, root.val) and recursion(root.right, root.val, max_v)

    return recursion(root.left, -sys.maxsize, root.val) and recursion(root.right, root.val, sys.maxsize)

(mark) isSymmetric (dfs or bfs) O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def solution(root):
    if not root:
        return True

    def recursion(root1, root2):
        if not root1 and not root2:
            return True
        elif root1 and root2:
            if root1.val == root2.val:
                return recursion(root1.left, root2.right) and recursion(
                    root1.right, root2.left)
            else:
                return False
        else:
            return False

    return recursion(root.left, root.right)

def solution(root):
    if not root:
        return True
    queue1 = [root.left, root.right]
    queue2 = [root.right, root.left]

    while queue1 and queue2:
        node1 = queue1.pop(0)
        node2 = queue2.pop(0)
        if not node1 and not node2:
            continue
        elif node1 and node2 and node1.val == node2.val:
            queue1.extend([node1.left, node1.right])
            queue2.extend([node2.right, node2.left])
        else:
            return False
    if not queue1 and not queue2:
        return True
    else:
        return False

(mark) buildTree (recursive) O(n)

观察：preorder 按层序给出每个根，每个根又把 inorder 切成左右两段子树。

用 dict 记录 inorder 中每个值的位置以便快速查找。然后定义 helper(start, end)：每次给它一个 inorder 区间，递归构造左右子树：
- root.left = helper(start, idx-1)
- root.right = helper(idx+1, end)

（若 start > end 返回 None）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(preorder, inorder):

    inorder_dict = {v: k for k, v in enumerate(inorder)}

    def build(i, j):
        if not preorder or i > j:
            return None
        val = preorder.pop(0)
        key = inorder_dict[val]
        node = TreeNode(val)
        node.left = build(i, key - 1)
        node.right = build(key + 1, j)
        return node

    return build(0, len(inorder) - 1)

(mark) Flatten (iterative pre-order dfs) O(n)

每次找到最深的左节点，把它接到当前节点的右孩子之前；再走到原右孩子继续递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(root):
    if not root:
        return None

    def flatten(node):
        if not node.left and not node.right:
            return node
        if node.left:
            # get the deepest left node to append to its first right node
            tmp_node = flatten(node.left)
            tmp_node.right = node.right # append it right to the deepest node's right
            node.right = node.left # append the top left to its right
            node.left = None
        if node.right:
            # return deepest right node
            return flatten(node.right)

    flatten(root)
    return root

maxProfit (trick) O(n)

要找 [lowest, highest] 这种二元组，且 highest 必须出现在 lowest 之后。所以记录历史最低，每次更新：
- lowest = min(lowest, prices[i])
- profit = max(profit, prices[i] - lowest)

1
2
3
4
5
6
7
def solution(prices):
    cur_min = sys.maxsize
    max_profit = 0
    for p in prices:
        cur_min = min(cur_min, p)
        max_profit = max(max_profit, p - cur_min)
    return max_profit

maxPathSum (tree dp) O(n)

自底向上。每个节点拿到左、右子树各自能贡献的最大路径和，尝试更新全局答案 result = max(result, left_max + right_max + node.val)；返回值为 max(left_max + node.val, right_max + node.val)，表示从这个节点向上延伸的最大单链路径。注意要跟 0 比较：若小于 0 就当成不取（路径里不要这一段）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(root):
    max_v = -sys.maxsize

    def recursive(root):
        nonlocal max_v
        if not root:
            return 0
        else:
            left = recursive(root.left)
            right = recursive(root.right)
            max_v = max(max_v, left + right + root.val)
            return max(left + root.val, right + root.val, 0)

    recursive(root)
    return max_v

longestConsecutive (hash) O(n)

把数组转成 set。遍历时若 nums[i]-1 在 set 里就跳过；只有遇到序列起点（即没有 nums[i]-1）时才开始向后逐 +1 计数，求出连续长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(nums):
    if not nums:
        return 0
    set_nums = set(nums)
    max_v = 0
    for num in nums:
        if num - 1 not in set_nums:
            count = 1
            while num + 1 in set_nums:
                num += 1
                count += 1
            max_v = max(max_v, count)
    return max_v

copyRandomList (hash) O(n)

用 collections.defaultdict 记录已访问的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def solution(head):
    node_dict = defaultdict(Node)

    def build(node):
        if not node:
            return None
        _node = Node(node.val)
        node_dict[node] = _node
        if node.random:
            if node.random in node_dict:
                _node.random = node_dict[node.random]
            else:
                _node.random = build(node.random)
        if node.next:
            if node.next in node_dict:
                _node.next = node_dict[node.next]
            else:
                _node.next = build(node.next)
        return _node

    return build(head)


def solution(head):
    if not head:
        return None

    node_dict = defaultdict(Node)

    _head = Node(head.val)
    node_dict[head] = _head
    ret_head = _head
    while head:
        if head.random:
            if head.random not in node_dict:
                node_dict[head.random] = Node(head.random.val)
            _head.random = node_dict[head.random]
        if head.next:
            if head.next not in node_dict:
                node_dict[head.next] = Node(head.next.val)
            _head.next = node_dict[head.next]
        head = head.next
        _head = _head.next

    return ret_head

wordbreak (dp) O(mn)

dp[i] 表示 s[0:i] 是否可被切分。转移：dp[i] = True 当存在 w 使得 dp[i - len(w)] == True 且 s[i - len(w):i] == w。

1
2
3
4
5
6
7
8
9
def solution(s, wordDict):
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for w in wordDict:
            if i >= len(w) and dp[i - len(w)] and s[i - len(w):i] == w:
                dp[i] = True
    return dp[-1]

DetectCycle (trick) O(n)

设头节点到环入口距离为 A，慢指针走了 A+B 与快指针相遇。快指针走了 2(A+B)。设环长 N，相遇时快指针比慢指针多走的恰好是若干圈环长。
- A+B+N = 2A+2B
- N = A+B

所以两者相遇后，再让一个新指针从 head 出发，与 slow 同步前进，相遇点就是环的入口（因为 B + A = N）。

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(head):
    p = head
    q = head
    t = head
    while p and q and p.next and q.next and q.next.next:
        p = p.next.next
        q = q.next
        if q == p:
            while q != t:
                q = q.next
                t = t.next
            return t
    return None

LRUCache (double linked list) O(1)

用双向链表，封装两个基本操作：remove（按 id 移除节点）和 add（追加到尾部）。
- get：先 remove 再 add（提到尾部）
- put：add 到尾部；超容量时从头部 remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Node:
    
    def __init__(self, k, x, next=None, pre=None):
        self.key = k
        self.val = x
        self.next = next
        self.pre = pre

class LRUCache(object):
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.dict = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.pre = self.head

    def get(self, key):
        if key in self.dict:
            node = self.dict[key]
            self._remove(node)
            self._add(node) 
            return node.val
        else:
            return -1

    def put(self, key, value):
        if key in self.dict:
            self._remove(self.dict[key])
        node = Node(key, value)
        self._add(node)
        self.dict[key] = node
        while len(self.dict) > self.capacity:
            tmp_node = self.head.next
            self._remove(tmp_node)
            del self.dict[tmp_node.key]

    def _remove(self, node):
        p = node.pre
        n = node.next
        p.next = n
        n.pre = p
    
    def _add(self, node):
        p = self.tail.pre
        p.next = node
        node.pre = p
        node.next = self.tail
        self.tail.pre = node

SortList (merge sort or quick sort) O(nlogn)

用三个子链表存放节点：以 head 为 partition 节点；left_head 存比它小的节点，right_head 存比它大的节点，middle_head 存与它相等的节点。

然后对 left_head 和 right_head 递归排序，最后把三段串起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def solution(head):
    if head is None:
        return None

    def recursive(head):
        if head is None:
            return None, None

        partition_node = head
        middle_head = ListNode(None)
        middle_cur = middle_head
        left_head = ListNode(None)
        left_cur = left_head
        right_head = ListNode(None)
        right_cur = right_head

        while head:
            if head.val < partition_node.val:
                left_cur.next = ListNode(head.val)
                left_cur = left_cur.next
            elif head.val > partition_node.val:
                right_cur.next = ListNode(head.val)
                right_cur = right_cur.next
            else:
                middle_cur.next = ListNode(head.val)
                middle_cur = middle_cur.next
            head = head.next
        
        left_head, left_tail = recursive(left_head.next)
        right_head, right_tail = recursive(right_head.next)

        if left_head is not None:
            left_tail.next = middle_head.next
        else:
            left_head = middle_head
        if right_head is not None:
            middle_cur.next = right_head.next
        else:
            right_tail = middle_cur

        return left_head, right_tail

    head, _ = recursive(head)
    return head.next

(mark) maxProduct (greedy) O(n)

同时记录当前最大值和最小值（因为负数乘负数可能成为最大）。每步用三者 (num, b*num, s*num) 取 max/min 更新。

1
2
3
4
5
6
def solution(nums):
    maximum = b = s = nums[0]
    for num in nums[1:]:
        b, s = max(num, b * num, s * num), min(num, b * num, s * num)
        maximum = max(maximum, b)
    return maximum

MinStack (trick) O(n)

再开一个栈记录”当前最小”。每次 push 一个新值时，与原栈顶最小比较：新值大就复制旧最小，否则把新值压入。pop 时两个栈一起 pop。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.min = []
        self.stack = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        if not self.min:
            self.min.append(x)
        else:
            self.min.append(min(self.min[-1], x))

    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()
        self.min.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.min[-1]

GetIntersectionNode (trick) O(m+n)

两条链表 p、q，把 p 接到 q 尾部、q 接到 p 尾部之后再走，两个指针相遇时即为交点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def solution(headA, headB):
    if not headA or not headB:
        return None
    nodeA = headA
    nodeB = headB
    while nodeA is not nodeB:
        if not nodeA and nodeB:
            return None
        if nodeA.next is None:
            nodeA = headB
        else:
            nodeA = nodeA.next
        if nodeB.next is None:
            nodeB = headA
        else:
            nodeB = nodeB.next
    return nodeA


def solution(headA, headB):

    def len(head):
        ret = 0
        while head:
            ret += 1
            head = head.next
        return ret

    lenA, lenB = len(headA), len(headB)
    diff = abs(lenA - lenB)

    if lenA > lenB:
        for _ in range(diff):
            headA = headA.next
    else:
        for _ in range(diff):
            headB = headB.next

    while headA != headB:
        headA = headA.next
        headB = headB.next
    return headA

MajorityElement (trick) O(n)

Boyer-Moore 投票法。维护 value 和 count：count == 0 时把 value 置为 nums[i] 并 count += 1；nums[i] == value 则 count += 1，否则 count -= 1。

1
2
3
4
5
6
7
8
9
10
11
12
def solution(nums):
    cur_value = nums[0]
    cur_num = 1
    for num in nums[1:]:
        if num != cur_value:
            cur_num -= 1
            if cur_num == -1:
                cur_value = num
                cur_num = 1
        else:
            cur_num += 1
    return cur_value

Rob (dp) O(n)

解法 1：两个数组 max_rob、max_not_rob。max_rob[i] 表示打劫第 i 家时的最大金额，max_not_rob[i] 表示不打劫时的最大金额：
- max_rob[i] = max_not_rob[i-1] + nums[i]
- max_not_rob[i] = max(max_not_rob[i-1], max_rob[i-1])

解法 2：
- f(0) = nums[0]
- f(1) = max(num[0], num[1])
- f(k) = max(f(k-2) + nums[k], f(k-1))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(nums):
    if not nums:
        return 0
    dp = [[0, 0] for _ in range(len(nums))]  # (rob, not_rob) * n
    dp[0][0], dp[0][1] = nums[0], 0
    for i in range(1, len(nums)):
        dp[i][0] = dp[i - 1][1] + nums[i]
        dp[i][1] = max(dp[i - 1])
    return max(dp[-1])


def solution(nums):
    last, now = 0, 0
    for i in nums:
        last, now = now, max(last + i, now)
    return now

numIslands (BFS DFS) O(mn)

双重 for 循环遍历所有 cell；遇到 ‘1’ 就 BFS（用栈/队列），把同一连通块的 ‘1’ 都改成 ‘0’。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def solution(grid):
    if not len(grid) or not len(grid[0]):
        return 0
    ret = 0
    n = len(grid)
    m = len(grid[0])
    for i in range(n):
        for j in range(m):
            if grid[i][j] == "1":
                grid[i][j] = "0"
                ret += 1
                queue = [(i, j)]
                while queue:
                    _i, _j = queue.pop(0)
                    if _i > 0 and grid[_i - 1][_j] == "1":
                        grid[_i - 1][_j] = "0"
                        queue.append((_i - 1, _j))
                    if _j > 0 and grid[_i][_j - 1] == "1":
                        grid[_i][_j - 1] = "0"
                        queue.append((_i, _j - 1))
                    if _i < n - 1 and grid[_i + 1][_j] == "1":
                        grid[_i + 1][_j] = "0"
                        queue.append((_i + 1, _j))
                    if _j < m - 1 and grid[_i][_j + 1] == "1":
                        grid[_i][_j + 1] = "0"
                        queue.append((_i, _j + 1))
    return ret

(mark) canFinish (dfs) O(n^3)

visited 数组记录每个节点状态：初始为 0，开始递归时置 -1，递归结束置 1。递归中若发现 visited[i] == -1 直接返回 False（找到环）；若 visited[i] == 1 返回 True（已确认无环，避免重复搜索）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def solution(numCourses, prerequisites):
    grid = [[] for _ in range(numCourses)]
    visited = [0] * numCourses

    for i, j in prerequisites:
        grid[i].append(j)

    def recusive(i):
        if visited[i] == -1:
            return False
        if visited[i] == 1:
            return True

        visited[i] = -1
        for j in grid[i]:
            if not recusive(j):
                return False

        visited[i] = 1
        return True

    for i in range(numCourses):
        if not recusive(i):
            return False
    return True

Trie (tree) O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class TrieNode():

    def __init__(self, val):
        self.next = [None] * 26
        self.val = val


class Trie(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode(False)

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: None
        """
        node = self.root
        for w in word:
            idx = ord(w) - ord('a')
            if not node.next[idx]:
                node.next[idx] = TrieNode(False)
            node = node.next[idx]
        node.val = True

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self.root
        for w in word:
            idx = ord(w) - ord('a')
            if not node.next[idx]:
                return False
            node = node.next[idx]
        return node.val

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        node = self.root
        for w in prefix:
            idx = ord(w) - ord('a')
            if not node.next[idx]:
                return False
            node = node.next[idx]
        return True

(mark) findKthLargest (heap, quickselect) O(nlogn)

堆解法直接用 heap。quickselect 类似快排：每次选 pivot 把数组划成两部分；若 len(left_part) == k-1 就返回 pivot；否则在大的那一部分继续找第 k 大或第 k-len(left_part)-1 大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# O(klogk+2(n-k)logk)
def solution(nums, k):
    import heapq
    k_heap = nums[0:k]
    heapq.heapify(k_heap)
    for i in range(k, len(nums)):
        heapq.heappush(k_heap, nums[i])
        heapq.heappop(k_heap)
    return heapq.heappop(k_heap)


# O(n)
def solution(nums, k):

    def recursive(nums, k):
        pivot = nums.pop(len(nums) // 2)
        right = [num for num in nums if num > pivot]
        lr = len(right)
        if k == lr + 1:
            return pivot
        elif k < lr + 1:
            return recursive(right, k)
        else:
            left = [num for num in nums if num <= pivot]
            return recursive(left, k - lr - 1)

    return recursive(nums, k)

maximalSquare (dp) O(n^2)

  • dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1，若 matrix[i][j] == ‘1’
  • max_v = max(max_v, dp[i][j])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(matrix):
    if not matrix or not matrix[0]:
        return 0

    dp = [[int(x) for x in row] for row in matrix]
    max_v = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if i == 0 or j == 0:
                max_v = max(max_v, dp[i][j])
            elif matrix[i][j] == "1":
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                max_v = max(max_v, dp[i][j])
            else:
                dp[i][j] == 0
    return max_v**2

invertTree (recursive) O(n)

root.left, root.right = recursive(root.right), recursive(root.left)

1
2
3
4
5
6
7
8
def solution(root):

    def recursive(root):
        if root:
            root.left, root.right = recursive(root.right), recursive(root.left)
        return root

    return recursive(root)

isPalindrome (trick) O(n)

快慢指针：fast 每次走两步、slow 每次走一步。fast 走到尾时把链表后半段反转，再与前半段逐一比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(head):
    rev = ListNode(None)
    fast = slow = head
    while fast and fast.next:
        fast = fast.next.next
        _slow = slow
        slow = slow.next
        _slow.next = rev.next
        rev.next = _slow
    if fast:
        slow = slow.next
    rev = rev.next
    while rev and slow:
        if rev.val != slow.val:
            return False
        rev = rev.next
        slow = slow.next
    return True

lowestCommonAncestor (recursive) O(n)

后序递归。count = recursive(root.left, p, q) + recursive(root.right, p, q)；若 root.val == p or == q，则 cur_count = 1 否则 0。当 count + cur_count == 2 时，记录答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(root, p, q):
    low_desc = None

    def recursive(root):
        nonlocal low_desc
        if not root:
            return 0
        ret = recursive(root.left)
        if ret < 2:
            ret += recursive(root.right)
        if root.val in (q.val, p.val):
            ret += 1
        if ret == 2 and not low_desc:
            low_desc = root
        return ret

    recursive(root)
    return low_desc

productExceptSelf (two pointers, reverse list) O(n)

两个数组：第一个记录左侧累积乘积，第二个记录右侧累积乘积，最后 result[i] = left[i] * right[i]。

1
2
3
4
5
6
7
8
9
10
11
12
def solution(nums):
    res = [1] * len(nums)
    p = 1
    for i in range(len(nums)):
        res[i] = p
        p *= nums[i]

    right = 1
    for i in range(len(nums) - 1, -1, -1):
        res[i] *= right
        right *= nums[i]
    return res

maxSlidingWindow (trick) O(n)

不需要每次重算最大值。维护一个结果数组，每次：
- 新进入的值 ≥ 当前最大：直接 append 新值
- 即将出窗的值 < 当前最大：append 当前最大（不变）
- 否则才在窗口内重新求 max

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(nums, k):
    if not nums:
        return nums

    ret = [max(nums[:k])]
    for i in range(1, len(nums) - k + 1):
        if nums[i + k - 1] >= ret[-1]:
            ret.append(nums[i + k - 1])
        elif nums[i - 1] < ret[-1]:
            ret.append(ret[-1])
        else:
            ret.append(max(nums[i:i + k]))
    return ret

(mark) searchMatrix (trick) O(m+n)

第一行从右端开始，把比 target 大的列排除，记录下当前列下标；第二行从该列继续往左排除…… 找到 target 返回 True，否则 False。

1
2
3
4
5
6
7
8
9
10
def solution(matrix, target):
    if len(matrix) == 0 or len(matrix[0]) == 0:
        return False
    j = len(matrix[0]) - 1
    for i in range(len(matrix)):
        while j >= 0 and matrix[i][j] > target:
            j -= 1
        if matrix[i][j] == target:
            return True
    return False

numSquares (dp) O(n^1.5)

候选范围 [1, floor(n^0.5)]。dp[i] = min(dp[i - j^2] + 1)，j 取所有候选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import math, sys


def solution(n):
    dp = [0] * (n + 1)
    squares = [i**2 for i in range(1, int(math.sqrt(n)) + 1)]
    dp[1] = 1
    for i in range(2, n + 1):
        min_v = sys.maxsize
        for j in squares:
            if i - j < 0:
                break
            min_v = min(min_v, dp[i - j])
        dp[i] = min_v + 1
    return dp[-1]

moveZeroes (trick) O(n)

每遇到非零值，就把它和”第一个 0”的位置交换。维护 index 记录第一个 0 的位置：nums[i] != 0 时 swap 并 index += 1，否则不动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def solution(nums):
    n = len(nums)
    if n == 0 or n == 1:
        return nums
    i = 0
    while i < n and nums[i] != 0:
        i += 1
    j = i
    while True:
        while j < n and nums[j] == 0:
            j += 1
        if j >= n:
            break
        nums[i], nums[j] = nums[j], nums[i]
        i += 1


def solution(nums):
    n = len(nums)
    if n == 0 or n == 1:
        return nums
    i = 0
    while i < n and nums[i] != 0:
        i += 1
    for j in range(i + 1, n):
        if nums[j] != 0:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

findDuplicate (trick) O(n)

转化为”链表找环入口”：把下标 i 看成节点，i → nums[i]。因为有重复值，这条链一定有环；环的入口就是重复值。

1
2
3
4
5
6
7
8
9
10
11
12
def solution(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while fast != slow:
        fast = nums[nums[fast]]
        slow = nums[slow]
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

MedianFinder (trick) O(nlogn)

解法 1：维护一个有序列表，每次用二分找到插入位置。

解法 2：双堆 —— 大顶堆（存较小一半）+ 小顶堆（存较大一半）。每次插入时若两堆大小相等，先入大堆再 pop 一个最大值送进小堆；否则反之。求中位数：两堆等长时取两个堆顶平均，否则取大堆堆顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import heapq


class MedianFinder(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.left_heap = []
        self.right_heap = []
        heapq.heapify(self.left_heap)  # big heap
        heapq.heapify(self.right_heap)  # small heap

    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        if len(self.left_heap) == len(self.right_heap):
            heapq.heappush(self.left_heap,
                           -heapq.heappushpop(self.right_heap, num))
        else:
            heapq.heappush(self.right_heap,
                           -heapq.heappushpop(self.left_heap, -num))

    def findMedian(self):
        """
        :rtype: float
        """
        if len(self.left_heap) == len(self.right_heap):
            return float(-self.left_heap[0] + self.right_heap[0]) / 2.
        else:
            return float(-self.left_heap[0])

Serialize (bfs) O(n)

按完全二叉树编号：node[i] 的子节点是 node[2i] 和 node[2i+1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def serialize(self, root):
    """Encodes a tree to a single string.
    
    :type root: TreeNode
    :rtype: str
    """
    if not root:
        return ''
    out = []
    queue = collections.deque([root])
    while queue:
        node = queue.popleft()
        out.append(str(node.val) if node else '#')
        if node:
            queue.append(node.left)
            queue.append(node.right)
    return ' '.join(out)

def deserialize(self, data):
    """Decodes your encoded data to tree.
    
    :type data: str
    :rtype: TreeNode
    """
    if not data:
        return None
    out = data.split()
    bfs = [TreeNode(int(i)) if i != '#' else None for i in out]
    slow_idx = 0  # the id in array nodex
    fast_idx = 1  # the id in array bfs
    root = bfs[0]
    nodes = [root]
    while slow_idx < len(nodes):
        node = nodes[slow_idx]
        slow_idx += 1  # each time we handle one node in nodes
        node.left = bfs[fast_idx]
        node.right = bfs[fast_idx + 1]
        fast_idx += 2  # each time we only handle two nodes in bfs
        if node.left:
            nodes.append(node.left)
        if node.right:
            nodes.append(node.right)
    return root

lengthOfLIS(dp)

lengthOfLIS(dp) O(n^2)

dp[i] 表示以位置 i 结尾的最长上升子序列长度。每次把当前值与之前所有值比较，若当前更大就尝试更新：

1
2
3
4
5
6
7
8
9
10
11
12
def lengthOfLIS(nums):
    if len(nums) == 0:
        return 0
    dp = [0] * len(nums)
    dp[0] = 1
    for i in range(1, len(nums)):
        max_t = 0
        for j in range(0, i):
            if nums[i] > nums[j]:
                max_t = max(max_t, dp[j]) # # longest length till now plus current 
        dp[i] = max_t + 1
    return max(dp)

(mark) lengthOfLIS(dp) O(nlogn)

dp[i] 存放当前已遍历元素能构成的”潜在上升子序列”的第 i 个位置候选值。

例：输入 [0, 8, 4, 12, 2]：
逐元素扫描，每次在 dp 里二分找到第一个 ≥ 当前值的位置替换。

  • 0 → dp = [0]
  • 8 → dp = [0, 8]
  • 4 → dp = [0, 4]
  • 12 → dp = [0, 4, 12]
  • 2 → dp = [0, 2, 12]

注意：最终的 dp 不是真正的 LIS，但它的长度就是 LIS 长度。

为什么把 [0, 4, 12] 改成 [0, 2, 12] 仍然合法？(1) 不破坏长度本身；(2) 之后碰到比 2 大的值时，可以接在 2 后面延伸出更长的 LIS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# o(n^2)
def solution(nums):
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)


# O(n * logn)
def solution(nums):
    dp = [0] * len(nums)
    size = 0
    for n in nums:
        i, j = 0, size
        while i != j:
            m = (i + j) // 2
            if dp[m] < n:
                i = m + 1
            else:
                j = m
        dp[i] = n
        size = max(size, i + 1)
    return size

removeInvalidParentheses(recursive) O(n^2)

用计数器扫描：’(‘ 时 +1，’)’ 时 -1。一旦计数器为负，说明前缀里 ‘)’ 比 ‘(‘ 多。

要修复，需要删一个 ‘)’。删哪一个？理论上前缀里任意一个都行，但为避免重复结果（如 “())” 删 s[1] 或 s[2] 都得到 “()”），约定只删一连串 ‘)’ 中的第一个。

删完后前缀合法，再递归处理剩下部分。但还需要追加信息：上一次删除的位置。否则两次删除按不同顺序会产生重复。

所以维护两个游标：i 表示扫描到哪、j 表示从哪开始可以删 ‘)’。i 与 j 之间的每一个 ‘)’ 都尝试递归。

那 ‘(‘ 怎么办？比如 s = '(()(('。答案是从右往左做一遍。更聪明的做法：把字符串反转，复用同一段代码！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def removeInvalidParentheses(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    def removeHelper(s, output, iStart, jStart, openParen, closedParen):
        numOpenParen, numClosedParen = 0, 0
        for i in range(iStart, len(s)):
            if s[i] == openParen:
                numOpenParen += 1
            if s[i] == closedParen:
                numClosedParen += 1
            # We have only ONE extra closed paren we need to remove
            if numClosedParen > numOpenParen:
                print(s)
                if openParen == '(':
                    print("positive")
                elif openParen == ')':
                    print('negative')
                print("i=", i, numOpenParen, numClosedParen)
                # Try removing this ONE closed paren at each position, skipping duplicates
                print(jStart, i)
                # jStart: always to search the first closedParen which can be removed
                for j in range(jStart, i+1):  # <=
                    # can be the first char,
                    # or the char which previous char isn't closedParen, removing each one of the consequtive closedParen actually is the same
                    if s[j] == closedParen and (j == jStart or s[j-1] != closedParen): # since when j == jStart, there isn't j-1
                        # Recursion: iStart = i since we now have valid # closed parenthesis thru i. jStart = j prevents duplicates
                        # at the next recursion, we only need to search the iStart from the current i, and search the jStart from the current j
                        # since we found the first invalid closedParen at the i, and we have removed a closedParen at j
                        print("remove, j=", j, s[j])
                        removeHelper(s[:j]+s[j+1:], output,
                                     i, j, openParen, closedParen)
                return
        reversed = s[::-1]
        print(reversed, "now out of the loop")
        if openParen == '(':
            removeHelper(reversed, output, 0, 0, ')', '(')
        else:
            output.append(reversed)

    output = []
    removeHelper(s, output, 0, 0, '(', ')')
    return output

maxProfit(dp) O(3n)

stack[n][3]：stack[i][0] 记录冷冻期，stack[i][1] 记录买入，stack[i][2] 记录卖出。
- 冷冻：取前一天三种状态的最大值 stack[i][0] = max(stack[i-1])
- 买入：只能从前一天的冷冻期转过来 stack[i][1] = stack[i-1][0] - prices[i]。不会出现 [买, 冷, 买] 因为冷冻已取了 max。
- 卖出：stack[i][2] = bought + prices[i]。bought = max(bought, stack[i][1])，记录当下最便宜的买入成本。

  • 维护 bought 是为了避免 [卖, 休, 卖] 的退化路径，每步都保最大 bought（即最小成本）。
1
2
3
4
5
6
7
8
9
10
11
12
def solution(prices):
    if not prices:
        return 0
    n = len(prices)
    buy, sell, cooldown = [0] * n, [0] * n, [0] * n
    bought = buy[0] = -prices[0]
    for i in range(1, n):
        buy[i] = cooldown[i - 1] - prices[i]
        sell[i] = bought + prices[i]
        cooldown[i] = max(buy[i - 1], sell[i - 1], cooldown[i - 1])
        bought = max(bought, buy[i])
    return max(buy[-1], sell[-1], cooldown[-1])

maxCoins(dp) O(n^3)

dp[i][j] 表示已经把 i 与 j 之间的气球全部戳掉后所获得的最大金币数。转移：

1
2
for k in range(i+1, j):
    coins = max(coins, nums[i]*nums[k]*nums[j] + recursion(i, k) + recursion(k, j))

含义：要让 [i, j] 之间金币最大，枚举每个气球 k 作为最后一个被戳的。也就是先把 (i, k) 和 (k, j) 之间的气球戳完，最后只剩 i、k、j 三个。

注意：在数组首尾各 append 一个 1，每次只处理 i+1 到 j（跳过哨兵）。这个 trick 保证 nums[i] * nums[k] * nums[j] 公式成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    def recursive(i, j):
        if dp[i][j] or j == i + 1:
            return dp[i][j]
        coins = 0
        for k in range(i + 1, j):
            # we firstly burst (i,k) and (k,j), only leave (i,k,j) three ballons
            coins = max(
                coins,
                nums[i] * nums[k] * nums[j] + recursive(i, k) + recursive(k, j))
        dp[i][j] = coins
        return coins

    return recursive(0, n - 1)

coinChange(dp) O(nm)

dp[i] = min(dp[i - coin] + 1) for coin in coins。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(coins, amount):
    if len(coins) == 0:
        return -1
    if amount == 0:
        return 0

    coins = sorted(set(coins), reverse=True)
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i == c:
                dp[i] = 1
                break
            elif i > c and dp[i - c] > 0:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return -1 if dp[-1] > amount else dp[-1]

Rob(dp in a tree), O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(root):

    def recursive(root):
        if not root:
            return 0, 0

        l_rob, l_not_rob = recursive(root.left)
        r_rob, r_not_rob = recursive(root.right)
        rob = l_not_rob + r_not_rob + root.val
        not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob)
        return rob, not_rob

    return max(recursive(root))

countBits(dp) O(n)

f[i] = f[i // 2] + i % 2

直观上：右移一位等于减半，再加上是否末位为 1。

1
2
3
4
5
def solution(num):
    dp = [0] * (num + 1)
    for i in range(1, num + 1):
        dp[i] = dp[i // 2] + i % 2
    return dp

topKFrequent(heap) O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import defaultdict
import heapq


def solution(nums, k):
    hash_map = defaultdict(int)
    for num in nums:
        hash_map[num] += 1
    ret = []
    i = 0
    for key, val in hash_map.items():
        if i < k:
            heapq.heappush(ret, (val, key))
        else:
            heapq.heappushpop(ret, (val, key))
        i += 1
    return [v for k, v in ret]

decodeString(stack) O(n)

栈解法：遇到 ‘]’ 时 pop 出 ‘[‘ 之前的字符串，再继续 pop 数字字符拼成倍数，把字符串重复后压回栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(s):
    stack = [""]
    num = ""
    for c in s:
        if c.isdigit():
            num += c
        elif c == "[":
            stack.extend([num, ""])
            num = ""
        elif c == "]":
            chars = stack.pop()
            n_chars = stack.pop()
            stack[-1] += chars * int(n_chars)
        else:
            stack[-1] += c
    return stack.pop()

reconstructQueue(trick) O(nlog)

先按 (-x[0], x[1]) 排序：身高降序、k 升序。

然后按每个 tuple 的第二个元素（k）作为下标插入：result.insert(p[1], p)。

原理：一个 tuple 的位置只受比它高的 tuple 影响，所以先处理高的；同身高里 k 小的先插入，能保证后续插入不打乱已经成立的”前面有几个 ≥ 自己”的条件。

1
2
3
4
5
6
def solution(people):
    people = sorted(people, key=lambda x: (-x[0], x[1]))
    ret = []
    for p in people:
        ret.insert(p[1], p)
    return ret

canPartition

canPartition(dp) O(n*s), n<=200, s<=10000

矩阵 dp[n][s]，n 是元素数，s = sum(input)//2。dp[i][j] = True 表示从前 i 个数中能选出和为 j 的子集。
- 先令 dp[i][nums[i]-1] = 1，表示只选第 i 个值
- dp[i][j] 来自两种情况：不选第 i 个 dp[i-1][j]；选第 i 个 dp[i-1][j-nums[i]]

Partition(dp) O(2^n with cutting branch)

递归调用 helper(nums[i+1:], target - num) for i, num in enumerate(nums)，剪枝即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# O(N * S)
def solution(nums):
    sum_v = sum(nums)
    if sum_v % 2 == 1:
        return False
    if max(nums) > sum_v // 2:
        return False
    scale = sum_v // 2 + 1
    dp = [[False] * scale for _ in range(len(nums))]

    nums = sorted(nums, reverse=True)
    dp[0][nums[0]] = True
    for i in range(1, len(nums)):
        dp[i][nums[i]] = True
        for j in range(scale - 1, 0, -1):
            if dp[i - 1][j]:
                dp[i][j] = True
            if j > nums[i] and dp[i - 1][j - nums[i]]:
                dp[i][j] = True
            if dp[i][-1]:
                return True
    return dp[-1][-1]

def solution(nums):

    def recursive(nums, target):
        for i, num in enumerate(nums):
            if num > target:
                return False
            elif num == target:
                return True
            elif recursive(nums[i + 1:], target - nums[i]):
                return True
        return False

    sum_v = sum(nums)
    if sum_v % 2 == 1:
        return False
    nums = sorted(nums, reverse=True)
    return recursive(nums, sum_v // 2)

pathSum(dp) O(n)

假设所有路径都从 root 出发。维护一个”老的累计和” oldPathSum 和当前累计和 currPathSum：当 oldPathSum == currPathSum - target 时，就找到一条满足条件的路径，因此 result += cache.get(oldPathSum, 0)。

注意：进入节点时 cache[currPathSum] = cache.get(currPathSum, 0) + 1，递归子节点；离开节点时 cache[currPathSum] -= 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(root, target):

    def recursive(root, cur_sum):
        if root:
            nonlocal ret
            cur_sum += root.val
            ret += cache.get(cur_sum - target, 0)
            cache[cur_sum] = cache.get(cur_sum, 0) + 1
            recursive(root.left, cur_sum)
            recursive(root.right, cur_sum)
            cache[cur_sum] -= 1

    ret = 0
    cache = {0: 1}
    recursive(root, 0)
    return ret

findAnagrams(cache) O(n)

用一个长度 26 的桶记录当前子串字符频次。每次滑动窗口更新桶，与 target 桶比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def solution(s, p):
    import collections
    ret = []
    p_counter = collections.Counter(p)
    s_counter = collections.Counter(s[:len(p) - 1])
    for i in range(len(p) - 1, len(s)):
        s_counter[s[i]] += 1
        pre_i = i - len(p) + 1
        if s_counter == p_counter:
            ret.append(pre_i)
        s_counter[s[pre_i]] -= 1
        if s_counter[s[pre_i]] == 0:
            del s_counter[s[pre_i]]
    return ret


def solution(s, p):
    l = len(p)
    p_frequency = [0] * 26
    ss_frequency = [0] * 26
    res = []
    for c in p:
        p_frequency[ord(c) - 97] += 1
    for c in s[0:l]:
        ss_frequency[ord(c) - 97] += 1
    if p_frequency == ss_frequency:
        res.append(0)

    for i in range(1, len(s) - l + 1):
        ss_frequency[ord(s[i - 1]) - 97] -= 1
        ss_frequency[ord(s[i + l - 1]) - 97] += 1
        if p_frequency == ss_frequency:
            res.append(i)

    return res

findDisappearedNumbers(trick) (n)

遍历数组，把”已出现”的对应位置标记为负数。最后剩下正数的下标 +1 就是缺失的数。

1
2
3
4
5
6
7
8
9
10
11
12
def solution(nums):
    n = len(nums)
    for i in range(n):
        _num = abs(nums[i])
        if _num <= n:
            nums[_num - 1] = -abs(nums[_num - 1])

    ret = []
    for i in range(n):
        if nums[i] > 0:
            ret.append(i + 1)
    return ret

findTargetSumWays(dp) O(n*2s) s=sum(nums)

dp 矩阵 dp[0:n][-s:s]：第 0 行 dp[0][±nums[0]] = 1；后续行 dp[i][j] = dp[i][j - nums[i]] + dp[i][j + nums[i]]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(nums, S):
    sum_v = sum(nums)
    if sum_v < S: 
        return 0
    n = len(nums)
    dp = [0] * (2 * sum_v + 1)
    dp[nums[0]] += 1
    dp[-nums[0]] += 1
    for n in nums[1:]:
        _dp = [0] * (2 * sum_v + 1)
        for i in range(-sum_v, sum_v + 1):
            if i + n <= sum_v:
                _dp[i] += dp[i + n]
            if i - n >= -sum_v:
                _dp[i] += dp[i - n]
        dp = _dp
    return dp[S]

diameterOfBinaryTree(tree dp) (n)

从叶子开始，每个父节点更新 result = max(result, a + b + 1)，a/b 分别是来自左、右子树的最长路径长度。返回 max(a, b) 给上一层作为它能向上延伸的最长链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(root):

    def recusive(root):
        nonlocal ret
        if not root:
            return 0, 0

        l = recusive(root.left)
        r = recusive(root.right)
        ret = max(ret, max(l) + max(r))
        return max(l) + 1, max(r) + 1

    ret = 0
    recusive(root)
    return ret

subarraySum(hash trick) O(n)

跟 findTargetSumWays 思路类似：前缀和 + 哈希。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# O(n^2)
def solution(nums, k):
    n = len(nums)
    ret = 0
    dp = [[0] * (n + 1) for _ in range(n)]  # (start_pos, len)
    for i in range(1, n + 1):
        for j in range(0, n - i + 1):
            if i == 1:
                dp[j][i] = nums[j]
            else:
                dp[j][i] = nums[j] + dp[j + 1][i - 1]
            if dp[j][i] == k:
                ret += 1
    return ret

# O(n)
def solution(nums, k):
    cache = {0: 1}
    cur_sum = 0
    ret = 0
    for n in nums:
        cur_sum += n
        ret += cache.get(cur_sum - k, 0)
        cache[cur_sum] = cache.get(cur_sum, 0) + 1
    return ret

findUnsortedSubarray(trick) O(n)

先从左往右扫，维护当前最大值，发现 nums[i] < cur_max 就更新 right。再从右往左扫，维护当前最小值，发现 nums[i] > cur_min 就更新 left。最终结果 max(right - left + 1, 0)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(nums):
    n = len(nums)
    if n <= 1:
        return 0
    right = 0
    cur_max = nums[0]
    for i in range(1, n):
        if nums[i] < cur_max:
            right = i
        cur_max = max(cur_max, nums[i])
        

    cur_min = nums[-1]
    left = len(nums)-1
    for i in range(n - 2, -1, -1):
        if nums[i] > cur_min:
            left = i
        cur_min = min(cur_min, nums[i])
    return max(right - left + 1, 0)

mergeTrees(recursive) O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(t1, t2):

    def recursive(t1, t2):
        if not t1 and not t2:
            return None
        elif not t1:
            return t2
        elif not t2:
            return t1
        else:
            t1.left = recursive(t1.left, t2.left)
            t1.right = recursive(t1.right, t2.right)
            t1.val = t1.val + t2.val
            return t1

    return recursive(t1, t2)

leastInterval(trick) O(n)

1
2
3
4
5
6
7
8
9
10
11
12
def solution(tasks, n):
    cache = [0] * 26
    for c in tasks:
        cache[ord(c) - ord('A')] += 1
    cache.sort(reverse=True)
    max_v = cache[0] - 1
    idle_slots = max_v * n
    for i in range(1, len(cache)):
        if cache[i] == 0:
            break
        idle_slots -= min(cache[i], max_v)
    return idle_slots + len(tasks) if idle_slots > 0 else len(tasks)

countSubstrings

countSubstrings() O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
n = len(s)
if n <= 1:
    return n
dp = [[0] * (n + 1) for _ in range(n)]  # (start_pos, len)
ret = 0
for i in range(1, n + 1):
    for j in range(0, n - i + 1):
        if i == 1 or (i == 2 and
                      s[j] == s[j + 1]) or (s[j] == s[j + i - 1] and
                                            dp[j + 1][i - 2]):
            dp[j][i] = 1
            ret += 1
return ret

countSubstrings(Manacher’s Algorithm?) O(n)

dailyTemperatures(stack) O(n)

单调栈。把比栈顶小的值入栈；遇到比栈顶大的就不断弹栈，把弹出位置的答案设为 current_position - popped_position。

1
2
3
4
5
6
7
8
9
10
11
def solution(T):
    ret = [0] * len(T)
    stack = [(T[0], 0)]
    for i in range(1, len(T)):
        top = stack[-1]
        if T[i] > top[0]:
            while stack and T[i] > stack[-1][0]:
                _t = stack.pop()
                ret[_t[1]] = i - _t[1]
        stack.append((T[i], i))
    return ret