分享｜如何科学刷题？ - 讨论 - 力扣（LeetCode）

滑动窗口与双指针

分享丨【算法题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环） - 讨论 - 力扣（LeetCode）

定长滑动窗口

当题目要求在固定长度 $k$ 的连续子数组 / 子串中求最大值、最小值、计数、满足条件的窗口数量等时，优先考虑定长滑动窗口

定长滑窗套路（三步）：

  1. 入：下标为 $i$ 的元素进入窗口，更新相关统计量。如果窗口左端点 $i−k+1<0$，说明尚未形成第一个窗口，重复第一步
  2. 更新答案：此时窗口长度为 $k$，符合题目要求，用相关统计量更新答案
  3. 出：下标为 $i−k+1$ 的元素离开窗口，更新相关统计量，为下一个循环做准备。

1456. 定长子串中元音的最大数目 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = vowel = 0
        for i, c in enumerate(s):  # 枚举窗口右端点 i
            # 1. 右端点进入窗口
            if c in "aeiou":
                vowel += 1

            left = i - k + 1  # 窗口左端点
            if left < 0:  # 窗口长度不足 k，尚未形成第一个窗口
                continue

            # 2. 更新答案
            ans = max(ans, vowel)

            # 3. 左端点离开窗口，为下一个循环做准备
            if s[left] in "aeiou":
                vowel -= 1

        return ans

1423. 可获得的最大点数 - 力扣（LeetCode）

从头尾抽可以逆向思维一下，变成标准的k滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        m = n - k # 反向窗口大小

        if m == 0:
            return sum(cardPoints)
        
        min_s = float("inf")
        cur = 0
        for i, point in enumerate(cardPoints):
            cur += point
            left = i - m + 1

            if left < 0:
                continue
            min_s = min(min_s, cur)

            cur -= cardPoints[left]
        
        return sum(cardPoints) - min_s

1888. 使二进制字符串字符交替的最少反转次数 - 力扣（LeetCode）

“循环移动 + 求最优” → 复制数组/字符串 + 定长滑动窗口

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
class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        ss = s + s

        diff0 = 0  # 当前窗口与 010101... 不同的位置数
        diff1 = 0  # 当前窗口与 101010... 不同的位置数

        ans = n

        # 一共只需要检查 n 种不同的循环移动
        # 因此 right 最多走到 2n - 2
        for right in range(2 * n - 1):

            # target0: 偶数下标为 0，奇数下标为 1
            # target1: 偶数下标为 1，奇数下标为 0
            target0 = "0" if right % 2 == 0 else "1"
            target1 = "1" if right % 2 == 0 else "0"

            if ss[right] != target0:
                diff0 += 1
            if ss[right] != target1:
                diff1 += 1

            left = right - n + 1

            if left < 0:
                continue

            ans = min(ans, diff0, diff1)

            target0 = "0" if left % 2 == 0 else "1"
            target1 = "1" if left % 2 == 0 else "0"

            if ss[left] != target0:
                diff0 -= 1

            if ss[left] != target1:
                diff1 -= 1

        return ans

不定长滑动窗口

当题目要求一个连续区间，但区间长度不固定，并且随着右端点移动，可以通过移动左端点使窗口重新满足条件时使用

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，求子数组个数

滑动窗口相当于在维护一个队列，右指针的移动可以视作入队，左指针的移动可以视作出队

求最长子数组

3. 无重复字符的最长子串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        window = set() # 维护从下标 left 到下标 right 的字符
        ans = 0
        for right, c in enumerate(s):
            # 在加入 c 之前，先移出窗口内的 c
            while c in window:
                window.remove(s[left])
                left += 1
            window.add(c)
            ans = max(ans, right - left + 1)
        return ans

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

见到从两端删除元素就可以转化为找中间区间，从最小操作变成找中间部分的最长区间

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
class Solution:
    def minOperations(self, nums: list[int], x: int) -> int:
        target = sum(nums) - x

        # 剪枝
        # x 比整个数组和大或者最小的比 x 大
        if target < 0 or min(nums) > x:
            return -1

        left = 0
        cur = 0
        ans = -1

        for right, num in enumerate(nums):
            cur += num

            # nums 都是正数，和太大就缩小窗口
            while cur > target:
                cur -= nums[left]
                left += 1

            # 必须是“恰好等于 target”
            if cur == target:
                ans = max(ans, right - left + 1)

        # 找不到和为 target 的连续子数组
        if ans == -1:
            return -1

        return len(nums) - ans

1004. 最大连续1的个数 III - 力扣（LeetCode）

注意先进入区间再删

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = ans = 0
        window_0 = 0
        for right, num in enumerate(nums):
            # right 先进入窗口
            if num == 0:
                window_0 += 1
            while window_0 > k:
                if nums[left] == 0:
                    window_0 -= 1
                left += 1

            ans = max(ans, right - left + 1)
        return ans

求最短子数组

需要在满足条件时进行更新

209. 长度最小的子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minSubArrayLen(self, target: int, nums: list[int]) -> int:
        n = len(nums)
        left = cur = 0
        ans = n + 1
        for right, num in enumerate(nums):
            cur += num
            while cur >= target:
                ans = min(ans, right - left + 1)
                cur -= nums[left]
                left += 1
        return ans if ans <= n else 0

3795. 不同元素和至少为 K 的最短子数组长度 - 力扣（LeetCode）

76. 最小覆盖子串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        Count_t = Counter(t)
        Count_w = Counter()
        ans_l, ans_r = -1, len(s)
        left = 0
        for right, c in enumerate(s):
            Count_w[c] += 1
            while Count_w >= Count_t:
                if right - left < ans_r - ans_l:
                    ans_l, ans_r = left, right
                Count_w[s[left]] -= 1
                left += 1
        return "" if ans_l == -1 else s[ans_l : ans_r + 1]

二分算法

分享丨【算法题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小） - 讨论 - 力扣（LeetCode）

二分查找

当数据本身具有有序性，需要快速寻找

  • 某个元素
  • 第一个 >= target
  • 第一个 > target
  • 最后一个 < target
  • 最后一个 <= target
  • 插入位置

时使用普通二分查找

目标 含义 区间
lower_bound 第一个 ≥ target 左侧：nums[i] < target
右侧：nums[i] >= target
upper_bound 第一个 > target 左侧：nums[i] <= target
右侧：nums[i] > target		 
1
2
3
4
5
6
7
8
9
10
11
12
13
def bisect_left(num, x):
    left = 0
    right = len(num)

    while left < right:
        mid = (left + right) // 2

        if num[mid] < x:
            left = mid + 1
        else:
            right = mid

    return left

1818. 绝对差值和 - 力扣（LeetCode）

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
class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        MOD = 10**9 + 7
        # nums1 中任意一个元素都可以被拿来替换
        arr = sorted(nums1)

        total = 0
        max_gain = 0
        n = len(nums1)

        for a, b in zip(nums1, nums2):
            # 当前这一对原本贡献的绝对差
            old_diff = abs(a - b)
            total += old_diff

            # 在 arr 中找第一个 >= b 的位置
            j = bisect_left(arr, b)

            # 默认不替换，新的差值仍然是 old_diff
            new_diff = old_diff

            # 候选 1：第一个 >= b 的数
            if j < n:
                new_diff = min(new_diff, abs(arr[j] - b))

            # 候选 2：最后一个 < b 的数
            if j > 0:
                new_diff = min(new_diff, abs(arr[j - 1] - b))
            max_gain = max(max_gain, old_diff - new_diff)
        
        return (total - max_gain) % MOD

658. 找到 K 个最接近的元素 - 力扣（LeetCode）

把二分查找和滑动窗口融合起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)

        right = bisect_left(arr, x)
        left = right - 1

        for _ in range(k):
            if left < 0:
                right += 1
            elif right >= n:
                left -= 1
            elif x - arr[left] <= arr[right] - x:
                left -= 1
            else:
                right += 1
        return arr[left + 1 : right]

二分答案

答案本身是一个数，并且随着这个数变大或变小，是否可行呈现单调性

  1. 题目要求优化一个数值？
  2. 这个答案有没有明确范围？
  3. 假设答案是 mid，能不能写 check(mid)？
  4. check(mid) 是否具有单调性？

如果都满足就是

求最小可行值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def check(val):

False False False True True True
                  ↑
              找第一个 True
    
left = 最小可能答案
right = 最大可能答案

while left < right:
    mid = (left + right) // 2

    if check(mid):
        right = mid
    else:
        left = mid + 1

return left

最重要的就是把上下界，也就是可能的答案确定好

1283. 使结果不超过阈值的最小除数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def smallestDivisor(self, nums: list[int], threshold: int) -> int:
        def check(div):
            total = 0
            for num in nums:
                total += (num + div - 1) // div
                if total > threshold:
                    return False
            return True

        left = 1
        right = max(nums)
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

1011. 在 D 天内送达包裹的能力 - 力扣（LeetCode）

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
class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def check(cap):
            cnt = 1       # 当前用了多少天
            cur = cap     # 当前这一天还剩多少容量

            for weight in weights:
                cur -= weight

                # 当前这一天装不下，换下一天
                if cur < 0:
                    cnt += 1
                    cur = cap - weight

                    if cnt > days:
                        return False

            return True

        # 最小容量至少要能装下最重的包裹
        left = max(weights)

        # 最大容量为一次把所有包裹运完
        right = sum(weights)

        # 找最小可行容量
        while left < right:
            mid = (left + right) // 2

            if check(mid):
                right = mid
            else:
                left = mid + 1

        return left

2594. 修车的最少时间 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        def check(t):
            total = 0
            for rank in ranks:
                total += isqrt(t // rank)
                if total >= cars:
                    return True
            return False

        left = 1
        right = min(ranks) * cars * cars
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

求最大可行值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def check(val):

True True True False False
          ↑
      最后一个 True

left = 最小可能答案
right = 最大可能答案        
        
while left < right:
    mid = (left + right + 1) // 2 # 让mid偏右

    if check(mid):
        left = mid
    else:
        right = mid - 1

return left

275. H 指数 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def hIndex(self, citations: list[int]) -> int:
        def check(h):
            cnt = 0
            for cite in citations:
                if cite >= h:
                    cnt += 1
                if cnt >= h:
                    return True
            return False

        left = 0
        right = len(citations)
        while left < right:
            mid = (left + right + 1) // 2
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

2226. 每个小孩最多能分到多少糖果 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        def check(num):
            cnt = 0
            for x in candies:
                cnt += x // num
                if cnt >= k:
                    return True
            return False

        left = 0
        right = max(candies)
        while left < right:
            mid = (left + right + 1) // 2
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

2141. 同时运行 N 台电脑的最长时间 - 力扣（LeetCode）

最小化最大值

本质上就是二分答案求最小，要求在多个最大值里找最小

410. 分割数组的最大值 - 力扣（LeetCode）

1760. 袋子里最少数目的球 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def check(cost):
            cnt = 0
            for num in nums:
                # 把 num 拆成每份最多 cost 时，需要的最少操作次数
                cnt += (num - 1) // cost
                if cnt > maxOperations:
                    return False
            return True

        left = 1
        right = max(nums)

        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

2560. 打家劫舍 IV - 力扣（LeetCode）

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
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:

        def check(min_val):
            cnt = 0
            prev = False

            for num in nums:
                if num <= min_val and not prev:
                    cnt += 1
                    prev = True
                    if cnt >= k:
                        return True
                else:
                    prev = False
            return False

        left = min(nums)
        right = max(nums)

        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

3613. 最小化连通分量的最大成本 - 力扣（LeetCode）

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
class UnionFind:
    def __init__(self, n):
        self.parents = list(range(n))
        self.count = n

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.parents[root_x] = self.parents[root_y]
        self.count -= 1
        return True


class Solution:
    def minCost(self, n: int, edges: List[List[int]], k: int) -> int:
        def check(max_cost):
            uf = UnionFind(n)
            for u, v, w in edges:
                if w <= max_cost:
                    if uf.union(u, v) and uf.count <= k:
                        return True
            return False

        if k == n:
            return 0

        left = 0
        right = max(w for _, _, w in edges)
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

第 K 小/大

第 K 小但不能直接排序 → 二分答案 + 计数

对于第 $k$ 小/大问题，有如下转化套路：

  • 第 $k$ 小等价于：求最小的 $x$，满足 $≤x$ 的数至少有 $k$ 个，最小可行值
  • 第 $k$ 大等价于：求最大的 $x$，满足 $≥x$ 的数至少有 $k$ 个，最大可行值

一般规定 $k$ 从 1 开始，而不是像数组下标那样从 0 开始

可排序的话用堆应该会更快

378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode） 找最小可行值

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
class Solution:
    def kthSmallest(self, matrix: list[list[int]], k: int) -> int:

        def check(num):
            cnt = 0
            # 从右上角开始
            i, j = 0, len(matrix) - 1

            while i < len(matrix) and j > -1:
                if matrix[i][j] <= num:
                # 当前行 0~j 都 <= num
                    cnt += j + 1
                    i += 1
                    
                    # 已经至少有 k 个
                    if cnt >= k:
                        return True
                else:
                    j -= 1
            return False

        left, right = matrix[0][0], matrix[-1][-1]
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

1201. 丑数 III - 力扣（LeetCode） 其实相当于是求最小可行值

3971. 最大总价值 - 力扣（LeetCode）

特殊的，找到能保留下来k个的最大可行值，然后再去累计这 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
25
26
27
28
29
30
31
32
class Solution:
    def maxTotalValue(self, value: list[int], decay: list[int], m: int) -> int:
        def check(low):
            # >= low 的价值是否至少有 m 个
            cnt = 0
            for v, d in zip(value, decay):
                if v >= low:
                    cnt += (v - low) // d + 1
                    if cnt >= m:
                        return True
            return False

        left = 0
        MOD = 10**9 + 7
        right = max(value)
        while left < right:
            mid = (left + right + 1) // 2  # 找最大的 low
            if check(mid):
                left = mid
            else:
                right = mid - 1
        
        low = left
        ans = 0
        for v, d in zip(value, decay):
            if v > low:
                k = (v - low - 1) // d + 1
                m -= k
                ans += (v * 2 - d * (k - 1)) * k
        ans //= 2
        ans += m * low  # 剩余的用low补齐
        return ans % MOD

719. 找出第 K 小的数对距离 - 力扣（LeetCode）

找最小可行值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def smallestDistancePair(self, nums: list[int], k: int) -> int:
        nums.sort()

        def check(mx):
            cnt = i = 0
            for j, x in enumerate(nums):
                while x - nums[i] > mx:
                    i += 1
                cnt += j - i # 计算比 mx 更小的个数
                # 这里 i 无需重置，因为得到的肯定比之前大
                if cnt >= k:
                    return True
            return False

        left, right = 0, nums[-1] - nums[0]
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

如果改成第 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
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def kthLargestDistance(self, nums: List[int], k: int) -> int:
        nums.sort()

        # 是否至少有 k 个数对距离 >= mx
        def check(mx):
            cnt = 0
            i = 0

            for j, x in enumerate(nums):
                while x - nums[i] >= mx:
                    i += 1

                # nums[0] ~ nums[i-1]
                # 和 nums[j] 的距离都 >= mx
                cnt += i

                if cnt >= k:
                    return True

            return False

        left = 0
        right = nums[-1] - nums[0]

        # 最大可行值
        while left < right:
            mid = (left + right + 1) // 2

            if check(mid):
                left = mid
            else:
                right = mid - 1

        return left

数据结构

分享丨【算法题单】常用数据结构（前缀和/栈/队列/堆/字典树/并查集/树状数组/线段树） - 讨论 - 力扣（LeetCode）

枚举右，维护左

对于 双变量问题，可以枚举一个变量，转化成 单变量问题

一般来说是将前半部门变成可维护的量，只移动一个变量，相当于倒过来循环

1. 两数之和 - 力扣（LeetCode）

121. 买卖股票的最佳时机 - 力扣（LeetCode）

1010. 总持续时间可被 60 整除的歌曲 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        ans = 0
        cnt = [0] * 60

        for t in time:
            ans += cnt[(60 - t % 60) % 60]
            cnt[t % 60] += 1
        return ans

2874. 有序三元组中的最大值 II - 力扣（LeetCode）

和买卖股票的最佳时机相似，因为都是正数，所以只需要维护最大差值和前序的最大值

1
2
3
4
5
6
7
8
9
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = 0
        max_diff = pre_max = 0
        for x in nums:
            ans = max(ans, max_diff * x)
            max_diff = max(max_diff, pre_max - x)
            pre_max = max(pre_max, x)
        return ans

624. 数组列表中的最大距离 - 力扣（LeetCode）

3584. 子序列首尾元素的最大乘积 - 力扣（LeetCode）

问题转化成：任意下标相差至少为 $m−1$的两数之积的最大值

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maximumProduct(self, nums: List[int], m: int) -> int:
        ans = mx = float("-inf")
        mn = float("inf")
        for i in range(m - 1, len(nums)):
            # 维护左边 [0,i-m+1] 中的最小值和最大值
            head = nums[i - m + 1]
            mn = min(mn, head)
            mx = max(mx, head)
            x = nums[i]
            ans = max(ans, x * mn, x * mx)
        return ans

面试题 16.24. 数对和 - 力扣（LeetCode）

2748. 美丽下标对的数目 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        ans = 0

        # cnt[d]：前面首位数字为 d 的数有多少个
        cnt = [0] * 10

        for num in nums:
            # 当前数作为右端点 j
            last = num % 10

            # 枚举前面可能的首位数字
            for first in range(1, 10):
                if gcd(first, last) == 1:
                    ans += cnt[first]
            
            first = num
            while first >= 10:
                first //= 10
                
            # 当前数加入历史，供后面的 j 使用
            cnt[first] += 1
        return ans

2506. 统计相似字符串对的数目 - 力扣（LeetCode）

可以用 frozenset作为dict的键，也可以用位运算维护字母表

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def similarPairs(self, words: list[str]) -> int:
        cnt = defaultdict(int)
        ans = 0
        for word in words:
            # contain = frozenset(word)
            contain = 0
            for c in word:
                contain |= 1 << (ord(c) - ord("a")) # 第 k 位为 1 的数
            ans += cnt[contain]
            cnt[contain] += 1
        return ans

2555. 两个线段获得的最多奖品 - 力扣（LeetCode）

滑动窗口枚举

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
class Solution:
    def maximizeWin(self, prizePositions: List[int], k: int) -> int:
        n = len(prizePositions)
        # best[i]：
        # 前 i 个奖品中，一个区间最多能拿多少个
        best = [0] * (n + 1)

        ans = 0
        left = 0

        for right, x in enumerate(prizePositions):

            # 保证当前区间长度 <= k
            while x - prizePositions[left] > k:
                left += 1

            # 当前这个区间能覆盖的奖品数量
            cur = right - left + 1

            # 当前区间 + 当前区间左边的最优区间
            ans = max(ans, cur + best[left])
            
            # 更新前缀最大值
            best[right + 1] = max(best[right], cur)

        return ans

前缀和

需要多次查询连续区间的信息时使用

常见：

  • 区间和
  • 某类元素数量
  • 区间差值

左闭右开公式：子数组 [left,right) 的元素和为 sum[right]−sum[left]

把下标区间定义成左闭右开，就不需要加一减一了

1
2
3
prefix = [0] * (len(nums) + 1)
for i, x in enumerate(nums):
    prefix[i + 1] = prefix[i] + x
$$ prefix[i] = nums[0] + nums[1] + \cdots + nums[i-1] $$

prefix[i] 表示前 i 个元素的和，所以

$$ sum(l,r)=prefix[r+1]-prefix[l] $$
left 和 right 一般是数组的含义

53. 最大子数组和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        ans = float("-inf")
        min_prefix = prefix_sum = 0
        for x in nums:
            prefix_sum += x
            ans = max(ans, prefix_sum - min_prefix)
            min_prefix = min(min_prefix, prefix_sum)
        return ans

也可以直接dp

1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        ans = dp = float("-inf")

        for num in nums:
            dp = max(dp + num, num)
            ans = max(ans, dp)
        return ans

哈希表

计数时常用

560. 和为 K 的子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix = defaultdict(int)
        prefix[0] = 1

        cur = ans = 0

        for num in nums:
            cur += num
            ans += prefix[cur - k]
            prefix[cur] += 1

        return ans

974. 和可被 K 整除的子数组 - 力扣（LeetCode） 类似

面试题 17.05. 字母与数字 - 力扣（LeetCode）

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
class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        # 记录每个前缀和第一次出现的位置
        first = {0: -1}

        cur = 0          # 当前前缀和
        max_len = 0      # 最长子数组长度
        start = 0        # 最长子数组起点

        for i, s in enumerate(array):
            # 字母记为 +1，数字记为 -1
            if s.isalpha():
                cur += 1
            else:
                cur -= 1

            # 前缀和相同，说明中间这段字母和数字数量相等
            if cur in first:
                length = i - first[cur]

                if length > max_len:
                    max_len = length
                    start = first[cur] + 1
            else:
                # 只记录第一次出现的位置，方便得到最长长度
                first[cur] = i

        return array[start:start + max_len]

3714. 最长的平衡子串 II - 力扣（LeetCode）

核心：把平衡子串分为只包含 1 种、2 种、3 种字母 三种情况分别处理

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
class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)

        # 一种字母
        ans = i = 0
        while i < n:
            start = i
            i += 1
            while i < n and s[i] == s[i - 1]:
                i += 1
            ans = max(ans, i - start)

        # 两种字母
        # 用+1 -1 的方式找平衡
        def f(x, y):
            nonlocal ans
            i = 0
            while i < n:
                pos = {0: i - 1}
                d = 0
                while i < n and (s[i] == x or s[i] == y):
                    d += 1 if s[i] == x else -1
                    if d in pos:
                        ans = max(ans, i - pos[d])
                    else:
                        pos[d] = i
                    i += 1
                i += 1

        f("a", "b")
        f("a", "c")
        f("b", "c")

        # 三种字母
        # 记录差值，就只有两项
        pos = {(0, 0): -1}
        cnt = defaultdict(int)
        for i, c in enumerate(s):
            cnt[c] += 1
            p = (cnt["a"] - cnt["b"], cnt["b"] - cnt["c"])
            if p in pos:
                ans = max(ans, i - pos[p])
            else:
                pos[p] = i
        return ans

距离和

需要大量计算

$$ \sum|a_i-x| $$
并且元素可以变成有序状态时常用
  • 把所有数变成 query 的操作次数
  • 相同元素之间的下标距离和

1685. 有序数组中差绝对值之和 - 力扣（LeetCode）

利用有序，所以绝对值就可以分为左右两种符号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        ans = []
        n = len(nums)

        # 前缀和：prefix[i] 表示 nums[0:i] 的元素和
        prefix = [0] * (n + 1)
        for i, num in enumerate(nums, 1):
            prefix[i] = prefix[i - 1] + num

        for i, num in enumerate(nums):
            # nums 已排序
            # 左侧元素都 <= num，因此绝对值可写成 num - nums[j]
            left = i * num - prefix[i]

            # 右侧元素都 >= num，因此绝对值可写成 nums[j] - num
            right = (prefix[n] - prefix[i]) - (n - i) * num

            # 当前 num 与其他所有元素的绝对差之和
            ans.append(left + right)

        return ans

2602. 使数组元素全部相等的最少操作次数 - 力扣（LeetCode）

同样思路，但是可以利用二分来找分界点，注意需要把无序先变成有序才行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        nums.sort() # 转有序才能这么做
        prefix = [0] * (n + 1)
        for i, num in enumerate(nums, 1):
            prefix[i] = prefix[i - 1] + num

        ans = []
        for q in queries:
            j = bisect_left(nums, q)
            left = q * j - prefix[j]
            right = prefix[n] - prefix[j] - q * (n - j)
            ans.append(left + right)
        return ans

2615. 等值距离和 - 力扣（LeetCode）

重要，理解转化的思路，把相同的抽出来以后，再用前缀和做累加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        group = defaultdict(list)
        for i, x in enumerate(nums):
            group[x].append(i) # 相同元素分到同一组
        ans = [0] * len(nums)

        for a in group.values():
            n = len(a)
            prefix = [0] * (n + 1)
            for i in range(1, n + 1):
                prefix[i] = prefix[i - 1] + a[i - 1]
            for j, target in enumerate(a):
                left = j * target - prefix[j]
                right = prefix[n] - prefix[j] - (n - j) * target
                ans[target] = left + right
        return ans

1703. 得到连续 K 个 1 的最少相邻交换次数 - 力扣（LeetCode）

将“移动到连续位置”转化为“移动到同一位置”

假设选中了 $k$ 个 1，它们原来的位置是：

$$ p_0,p_1,\dots,p_{k-1} $$
把它们移动到连续的位置：
$$ t,t+1,t+2,\dots,t+k-1 $$
代价是
$$ \sum_{i=0}^{k-1}|p_i-(t+i)| $$
把括号整理一下：
$$ p_i-(t+i) = (p_i-i)-t $$
所以定义 $q_i=p_i-i$，就可以把代价写成
$$ \sum_{i=0}^{k-1}|q_i-t| $$
找一个位置 $t$，让所有 $q_i$ 到 $t$ 的距离之和最小

于是需要取中位数，后面的就是前缀和的事了

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
class Solution:
    def minMoves(self, nums: List[int], k: int) -> int:
        # 所有 1 的原始位置
        pos = [i for i, x in enumerate(nums) if x == 1]

        # pos[i] - i：
        # 将“移动到连续位置”转化为“移动到同一位置”
        q = [p - i for i, p in enumerate(pos)]

        # q 的前缀和，方便 O(1) 计算区间和
        prefix = [0] * (len(q) + 1)

        for i in range(1, len(q) + 1):
            prefix[i] = prefix[i - 1] + q[i - 1]

        ans = float("inf")
        m = len(q)

        # 枚举连续的 k 个 1
        for l in range(m - k + 1):
            r = l + k - 1

            # 中位数位置
            mid = (l + r) // 2
            median = q[mid]

            left = (mid - l) * median - (prefix[mid] - prefix[l])
            right = prefix[r + 1] - prefix[mid + 1] - median * (r - mid)

            ans = min(ans, left + right)
        return ans

二维前缀和

矩阵 + 多次矩形区域求和

前缀和：

$$ pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + mat[i][j] $$
区间和：
$$ sum(r_2,c_2,r_1,c_1)= pre[r_2+1][c_2+1] - pre[r_1][c_2+1] - pre[r_2+1][c_1] + pre[r_1][c_1] $$
[1314. 矩阵区域和 - 力扣（LeetCode）](https://leetcode.cn/problems/matrix-block-sum/) 
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
class Solution:
    def matrixBlockSum(self, mat: list[list[int]], k: int) -> list[list[int]]:
        m = len(mat)
        n = len(mat[0])

        prefix = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m):
            for j in range(n):
                prefix[i + 1][j + 1] = (
                    prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + mat[i][j]
                )

        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                r1 = max(0, i - k)
                c1 = max(0, j - k)
                r2 = min(i + k, m - 1)
                c2 = min(j + k, n - 1)

                ans[i][j] = (
                    prefix[r2 + 1][c2 + 1]
                    - prefix[r1][c2 + 1]
                    - prefix[r2 + 1][c1]
                    + prefix[r1][c1]
                )
        return ans

差分

一维差分

差分与前缀和的关系，类似导数与积分的关系

当题目频繁对一段区间做修改时，不要逐个位置改，而只记录“这个变化从哪里开始、从哪里结束”，最后再用前缀和还原

定义差分数组

$$ d[i] = a[i] - a[i-1] $$
`d[i]` 表示从位置 $i $ 开始，数值发生了多少变化

对于一个闭区间 [l, r] 加上 x：

$$ diff[l] += x\\ diff[r+1] -= x $$
需要+1保证 $r$ 还能被正常计数

diff[max_end + 1] 的作用只是负责把最后一个区间的影响关掉

0-based 更符合 Python

2848. 与车相交的点 - 力扣（LeetCode）

1-base

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        max_end = max(end for start, end in nums)

        diff = [0] * (max_end + 2) # 因为给的数据是1-base，所以扩两个

        for start, end in nums:
            diff[start] += 1
            diff[end + 1] -= 1

        ans = 0
        cur = 0

        for i in range(1, max_end + 1): # 掐头去尾
            cur += diff[i]

            if cur > 0:
                ans += 1

        return ans

1109. 航班预订统计 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def corpFlightBookings(self, bookings: list[list[int]], n: int) -> list[int]:
        diff = [0] * (n + 2) # 1-base

        for start, end, seats in bookings:
            diff[start] += seats
            diff[end + 1] -= seats

        cur = 0
        answer = []

        for i in range(1, n + 1):
            cur += diff[i]
            answer.append(cur)
        return answer

1893. 检查是否区域内所有整数都被覆盖 - 力扣（LeetCode）

3964. 照亮道路的最少灯泡数 - 力扣（LeetCode）

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
class Solution:
    def minLights(self, lights: list[int]) -> int:
        n = len(lights)
        diff = [0] * (n + 1) # 0-base

        for i, v in enumerate(lights):
            if v > 0:
                left = max(i - v, 0)
                right = min(i + v, n - 1)

                diff[left] += 1
                diff[right + 1] -= 1
        ans = 0
        cover = 0

        for i in range(n):
            cover += diff[i]

            # 当前位置没被照亮，必须补灯
            if cover == 0:
                ans += 1
                cover += 1
                
                # 新灯覆盖 [i, i+2]
                diff[min(i + 3, n)] -= 1

        return ans

995. K 连续位的最小翻转次数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        diff = [0] * (n + 1) # 0-base
        ans = 0
        
        # 当前累计翻转次数
        flip = 0
        
        for i in range(n):
            flip += diff[i]
            cur = nums[i] ^ (flip % 2) # 0 ^ 1 = 1
            if cur == 1:
                continue
                
            # 当前是 0，必须从 i 开始翻 k 个
            if i + k > n:
                return -1

            ans += 1
            flip += 1
            diff[i + k] -= 1
        return ans

二维差分

2536. 子矩阵元素加 1 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        diff = [[0] * (n + 1) for _ in range(n + 1)]

        for r1, c1, r2, c2 in queries:
            diff[r1][c1] += 1
            diff[r1][c2 + 1] -= 1
            diff[r2 + 1][c1] -= 1
            diff[r2 + 1][c2 + 1] += 1

        ans = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                up = ans[i - 1][j] if i > 0 else 0
                left = ans[i][j - 1] if j > 0 else 0
                left_up = ans[i - 1][j - 1] if i > 0 and j > 0 else 0

                ans[i][j] = diff[i][j] + up + left - left_up
        return ans

栈

844. 比较含退格的字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def build(s):
            st = []
            for c in s:
                if c!= "#":
                    st.append(c)
                elif st:
                    st.pop()
            return st
        return build(s) == build(t)

2434. 使用机器人打印字典序最小的字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def robotWithString(self, s: str) -> str:
        n = len(s)

        # suffix_min[i] 表示 s[i:] 中的最小字符
        suffix_min = ["{"] * (n + 1)

        for i in range(n - 1, -1, -1):
            suffix_min[i] = min(s[i], suffix_min[i + 1])

        st = []
        ans = []

        for i, c in enumerate(s):
            # 操作1：s 的首字符进入 t
            st.append(c)
            
            # s[0:i+1] 已经处理完了
            # 所以后面剩余的是 s[i+1:]
            while st and st[-1] <= suffix_min[i + 1]:
                ans.append(st.pop())

        return "".join(ans)

3170. 删除星号以后字典序最小的字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def clearStars(self, s: str) -> str:
        s = list(s)
        stack = [[] for _ in range(26)]
        for i, c in enumerate(s):
            if c != "*":
                stack[ord(c) - ord("a")].append(i)
                continue
            for st in stack:
                if st:
                    s[st.pop()] = "*"
                    break

        return "".join(c for c in s if c != "*")

碰到纯字母的题可以这么做

邻项消除

2197. 替换数组中的非互质数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def replaceNonCoprimes(self, nums: list[int]) -> list[int]:
        st = []

        for x in nums:
            while st and gcd(st[-1], x) > 1:
                y = st.pop()
                g = gcd(x, y) # 最大公约数 GCD
                x = x // g * y # 最小公倍数 LCM

            st.append(x)
        return st

3703. 移除K-平衡子字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def removeSubstring(self, s: str, k: int) -> str:
        st = []  # 栈中保存 [字符, 连续出现次数]
        for b in s:
            if st and st[-1][0] == b:
                st[-1][1] += 1  # 连续相同括号个数 +1
            else:
                st.append([b, 1])  # 新的括号

            # 栈顶的 k 个右括号与栈顶下面的 k 个左括号抵消
            if b == ")" and len(st) > 1 and st[-1][1] == k and st[-2][1] >= k:
                st.pop()
                st[-1][1] -= k
                if st[-1][1] == 0:
                    st.pop()
        return "".join(b * cnt for b, cnt in st)

735. 小行星碰撞 - 力扣（LeetCode）

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
class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        st = []
        for x in asteroids:
            # 向右的小行星不会立刻和前面的碰撞
            if x > 0:
                st.append(x)
                continue

            # x < 0，只有栈顶 > 0 时才会发生碰撞
            while st and st[-1] > 0:
                top = st[-1]

                if top < -x:
                    # 栈顶更小，被 x 撞掉
                    st.pop()
                    continue

                elif top == -x:
                    # 一样大，两者都消失
                    st.pop()

                # top >= -x 时，x 都没了
                break

            else:
                # while 没有通过 break 结束
                # 说明 x 活下来了
                st.append(x)
        return st

合法括号字符串

看见匹配字符串大概率就是栈

20. 有效的括号 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2:
            return False
        mp = {")": "(", "]": "[", "}": "{"}
        st = []
        for c in s:
            if c not in mp:
                st.append(c)
            elif not st or st.pop() != mp[c]:
                return False
        return not st

678. 有效的括号字符串 - 力扣（LeetCode）

注意这里有序号约束

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
class Solution:
    def checkValidString(self, s: str) -> bool:
        left = []   # '(' 的下标
        star = []   # '*' 的下标

        for i, c in enumerate(s):
            if c == "(":
                left.append(i)

            elif c == "*":
                star.append(i)

            else:  # ')'
                if left:
                    left.pop()
                elif star:
                    star.pop()
                else:
                    return False

        # 用剩余的 * 去匹配剩余的 (
        while left and star:
            # * 必须出现在 ( 后面，才能充当 ')'
            if left[-1] < star[-1]:
                left.pop()
                star.pop()
            else:
                return False

        return not left

32. 最长有效括号 - 力扣（LeetCode）

注意要考虑编号，记录有效区间的开始，不能直接去匹配计数，会导致记录异常数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        st = [-1]
        ans = 0
        for i, c in enumerate(s):
            if c == "(":
                st.append(i)
            else:
                st.pop()
                if st:
                    ans = max(i - st[-1], ans)
                else:
                    st.append(i)
        return ans

表达式解析

用栈来做数学题，主要是针对加减乘除运算规律

1006. 笨阶乘 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def clumsy(self, n: int) -> int:
        st = [n]
        op = 0  # 记录下个符号，"+""-"就append
        for x in range(n - 1, 0, -1):
            if op == 0:
                st[-1] *= x
            elif op == 1:
                st[-1] = int(st[-1] / x)
            elif op == 2:
                st.append(x)
            else:
                st.append(-x)
            op = (op + 1) % 4

        return sum(st)

8. 字符串转换整数 (atoi) - 力扣（LeetCode）

在计算这块sign直接用+-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
class Solution:
    def myAtoi(self, s: str) -> int:
        n = len(s)
        i = 0

        # 1. 跳过前导空格
        while i < n and s[i] == " ":
            i += 1
        
        # 2. 处理符号
        sign = 1
        if i < n and s[i] in "+-":
            sign = 1 if s[i] == "+" else -1
            i += 1
        
        MX = (1 << 31) - 1
        num = 0

        # 3. 连续读取数字
        while i < n and "0" <= s[i] <= "9":
            num = num * 10 + int(s[i])
            
            # 4. 截断
            if num > MX:
                return MX if sign > 0 else -(1 << 31)
            i += 1
        return sign * num

224. 基本计算器 - 力扣（LeetCode）

有 + - ( )，难点是括号

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 Solution:
    def calculate(self, s: str) -> int:
        st = []

        res = 0
        num = 0
        sign = 1

        for c in s:
            if c.isdigit():
                num = num * 10 + int(c) # 累计计数

            elif c == "+":
                res += sign * num
                num = 0
                sign = 1

            elif c == "-":
                res += sign * num
                num = 0
                sign = -1

            elif c == "(":
                # 保存括号外的状态
                st.append(res)
                st.append(sign)

                # 进入新的括号层
                res = 0
                sign = 1

            elif c == ")":
                # 先结算括号中最后一个数字
                res += sign * num
                num = 0

                # 括号整体乘括号前符号
                prev_sign = st.pop()
                res *= prev_sign

                # 加上括号之前的结果
                prev_res = st.pop()
                res += prev_res

            # 空格直接忽略

        # 最后一个数字还没结算
        res += sign * num

        return res

227. 基本计算器 II - 力扣（LeetCode）

有 + - * /，没有括号，难点是乘除优先级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def calculate(self, s: str) -> int:
        st = []
        num = 0
        sign = "+"

        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if c in "+-*/" or i == len(s) - 1:
                # 这里的 sign 是num的前一个符号
                if sign == "+":
                    st.append(num)
                elif sign == "-":
                    st.append(-num)
                elif sign == "*":
                    st[-1] *= num
                else:
                    st[-1] = int(st[-1] / num)
                sign = c
                num = 0
        return sum(st)

单调栈

当题目要求“对每个位置，快速找到左边/右边第一个比它大或比它小的元素”时，优先考虑单调栈

739. 每日温度 - 力扣（LeetCode）

496. 下一个更大元素 I - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
        st = []
        mp = {}
        
        for num in nums2:
            while st and st[-1] < num:
                mp[st.pop()] = num
            st.append(num)

        ans = []
        for num in nums1:
            ans.append(mp.get(num,-1))
            
        return ans

503. 下一个更大元素 II - 力扣（LeetCode）

可以直接复制一份，也可以取余做，取余注意不要二次进栈

2866. 美丽塔 II - 力扣（LeetCode）

单调栈 + DP

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 Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)

        left = [0] * n
        right = [0] * n

        st = []

        for i, h in enumerate(maxHeights):
            while st and maxHeights[st[-1]] > h:
                st.pop()
            if st:
                j = st[-1]
                left[i] = left[j] + (i - j) * h
            else:
                left[i] = (i + 1) * h
            st.append(i)

        st = []

        for i in range(n - 1, -1, -1):
            h = maxHeights[i]
            while st and maxHeights[st[-1]] > h:
                st.pop()
            if st:
                j = st[-1]
                right[i] = right[j] + (j - i) * h
            else:
                right[i] = (n - i) * h
            st.append(i)

        ans = 0

        for i in range(n):
            ans = max(ans, left[i] + right[i] - maxHeights[i])

        return ans

队列

需要按照“先进入的先处理”的顺序执行时，优先考虑队列

和定长滑动窗口一样，入-更新-出

239. 滑动窗口最大值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()
        ans = []

        for right in range(len(nums)):
            while dq and nums[right] >= nums[dq[-1]]:
                dq.pop()
            dq.append(right)
            left = right - k + 1
            if left < 0:
                continue
            if dq[0] < left:
                dq.popleft()
            ans.append(nums[dq[0]])
        return ans

1438. 绝对差不超过限制的最长连续子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def longestSubarray(self, nums: list[int], limit: int) -> int:
        mx = deque()
        mn = deque()
        left = 0
        ans = 0

        for right in range(len(nums)):
            while mx and nums[right] >= nums[mx[-1]]:
                mx.pop()
            while mn and nums[right] <= nums[mn[-1]]:
                mn.pop()
            mx.append(right)
            mn.append(right)
            while nums[mx[0]] - nums[mn[0]] > limit:
                left += 1
                # 判断是否出队
                if left > mx[0]:
                    mx.popleft()
                if left > mn[0]:
                    mn.popleft()

            ans = max(ans, right - left + 1)
        return ans

堆

需要频繁操作最大或者最小，前K大/小的时候用

常用函数：

1
2
3
4
heap = []

heapq.heappush(heap, x) # 逐个 heappush 复杂度为 O(nlogn)
x = heapq.heappop(heap) # 弹出最小值(python默认是最小堆)
1
2
3
nums = [3, 1, 5, 2, 4]

heapq.heapify(nums) # 堆化的复杂度是 O(n)

1046. 最后一块石头的重量 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-x for x in stones]
        heapq.heapify(heap)
        while len(heap) >= 2:
            y = -heapq.heappop(heap)
            x = -heapq.heappop(heap)
            if x == y:
                continue
            else:
                heapq.heappush(heap, -(y - x))

        return -heap[0] if len(heap) == 1 else 0

2406. 将区间分为最少组数 - 力扣（LeetCode）

经典题，区间排序左端点，然后用堆来排序右端点，看合并还是新开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort()  # 按左端点排序

        heap = []  # 小根堆：记录每个组最后一个区间的右端点

        for left, right in intervals:
            # 最早结束的组已经和当前区间不重叠，可以复用
            if heap and heap[0] < left:
                heapq.heappop(heap)

            # 当前区间放入某一组
            heapq.heappush(heap, right)

        return len(heap)

2462. 雇佣 K 位工人的总代价 - 力扣（LeetCode）

有限制，维护两个堆

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
class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)

        left_heap = []
        right_heap = []

        l = 0
        r = n - 1

        # 初始化左侧候选
        while l <= r and len(left_heap) < candidates:
            heapq.heappush(left_heap, (costs[l], l))
            l += 1

        # 初始化右侧候选
        while l <= r and len(right_heap) < candidates:
            heapq.heappush(right_heap, (costs[r], r))
            r -= 1

        ans = 0

        for _ in range(k):
            # 右堆为空，或者左堆堆顶更优
            if not right_heap or (
                left_heap and left_heap[0] <= right_heap[0]
            ):
                cost, idx = heapq.heappop(left_heap)
                ans += cost

                # 从左边补充新的候选
                if l <= r:
                    heapq.heappush(left_heap, (costs[l], l))
                    l += 1

            else:
                cost, idx = heapq.heappop(right_heap)
                ans += cost

                # 从右边补充新的候选
                if l <= r:
                    heapq.heappush(right_heap, (costs[r], r))
                    r -= 1

        return ans

1834. 单线程 CPU - 力扣（LeetCode）

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
import heapq


class Solution:
    def getOrder(self, tasks: list[list[int]]) -> list[int]:
        n = len(tasks)

        # (进入时间, 执行时间, 原始下标)
        tasks = [
            (enqueue, processing, i) for i, (enqueue, processing) in enumerate(tasks)
        ]

        # 按进入时间排序
        tasks.sort()

        heap = []
        ans = []

        i = 0
        time = 0

        while i < n or heap:

            # 当前没有可执行任务
            # 直接跳到下一个任务到达的时间
            if not heap and time < tasks[i][0]:
                time = tasks[i][0]

            # 把当前时刻已经到达的任务全部加入堆
            while i < n and tasks[i][0] <= time:
                enqueue, processing, idx = tasks[i]

                heapq.heappush(heap, (processing, idx))

                i += 1

            # 选择执行时间最短的任务
            processing, idx = heapq.heappop(heap)

            ans.append(idx)

            # CPU 执行完这个任务
            time += processing

        return ans

1792. 最大平均通过率 - 力扣（LeetCode） 不能直接存放数值，应该堆存放收益

23. 合并 K 个升序链表 - 力扣（LeetCode）

hot 100 hard

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
import heapq

class Solution:
    def mergeKLists(self, lists: list[ListNode | None]) -> ListNode | None:
        dummy = ListNode(0)
        cur = dummy

        hp = []

        for i, node in enumerate(lists):
            if node is not None:
                heapq.heappush(hp, (node.val, i))

        while hp:
            _, i = heapq.heappop(hp)

            node = lists[i]

            # 直接连接原节点
            cur.next = node
            cur = cur.next

            # 当前链表向后移动
            lists[i] = node.next

            if lists[i] is not None:
                heapq.heappush(hp, (lists[i].val, i))

        return dummy.next

632. 最小区间 - 力扣（LeetCode）

和合并K个有序类似

1
2
3
4
5
6
7
8
9
10
11
每个列表取一个数
      ↓
当前区间 [最小值, 最大值]
      ↓
记录答案
      ↓
找到最小值来自哪个列表
      ↓
该列表向后移动一位
      ↓
重复

最大值需要维护，最小值直接看堆

第 K 小/大

有的可以用二分解决

378. 有序矩阵中第 K 小的元素 - 力扣（LeetCode）

堆做法，从速度上来看二分答案更快

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

class Solution:
    def kthSmallest(self, matrix: list[list[int]], k: int) -> int:
        n = len(matrix)

        heap = []

        # 每一行先放第一个元素
        for i in range(n):
            heapq.heappush(heap, (matrix[i][0], i, 0))

        # 弹出 k 次
        for _ in range(k):
            val, i, j = heapq.heappop(heap)

            # 当前行还有下一个元素
            if j + 1 < n:
                heapq.heappush(
                    heap,
                    (matrix[i][j + 1], i, j + 1)
                )

        return val

264. 丑数 II - 力扣（LeetCode）

感觉这是通用数学方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        hp = [1]
        seen = {1}

        for _ in range(n):
            x = heapq.heappop(hp)
            for f in (2, 3, 5):
                nxt = x * f
                if nxt not in seen:
                    seen.add(nxt)
                    heapq.heappush(hp, nxt)

        return x

2386. 找出数组的第 K 大和 - 力扣（LeetCode）

这里的数组可以中间删掉部分，所以可以先累计所有大于0的，再把数组绝对值化作为损失

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        max_sum = sum(x for x in nums if x > 0)
        arr = sorted(abs(x) for x in nums)

        if k == 1:
            return max_sum
        loss = 0
        hp = [(arr[0], 0)]

        for _ in range(k - 1):
            loss, i = heapq.heappop(hp)
            if i + 1 < len(arr):
                heapq.heappush(hp, (loss + arr[i + 1], i + 1))
                heapq.heappush(hp, (loss - arr[i] + arr[i + 1], i + 1))
        return max_sum - loss

并查集

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
class UnionFind:
    def __init__(self, n):
        # parent[i] 表示 i 的父节点
        self.parent = list(range(n))
        # size[i] 表示以 i 为根的集合大小
        self.size = [1] * n
        # 当前连通块数量
        self.count = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """
        合并 x 和 y 所在的集合
        如果原本不连通，返回 True
        如果原本已经连通，返回 False
        """
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False

        if self.size[root_x] < self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]

        self.count -=1
        return True

    def connected(self, x, y):
        """
        判断 x 和 y 是否连通
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        获取 x 所在连通块的大小
        """
        return self.size[self.find(x)]

例题：给定 $n$ 个节点（编号从 0 到 $n-1$）和 $m$ 条无向边，每条边包含两个节点和一个成本。计算连接所有节点的最小成本。若无法连通所有节点，返回 −1

输入：第一行输入两个整数 $n$ 和 $m$：

接下来 $ m$ 行，每行包含三个整数 u、v、w，表示节点 u 和节点 v 之间有一条成本为 w 的边

输出：输出一个整数，表示连接所有节点的最小成本。若无法连通所有节点，输出 -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
def solve():
    n, m = map(int, input().split())

    edges = []

    for _ in range(m):
        u, v, w = map(int, input().split())
        edges.append((w, u, v))

    # 按照边权排序
    edges.sort()

    uf = UnionFind(n)

    ans = 0
    cnt = 0

    for w, u, v in edges:
        # 如果 u、v 原本不连通，则选择这条边
        if uf.union(u, v):
            ans += w
            cnt += 1

            if cnt == n - 1:
                break

    if cnt == n - 1:
        print(ans)
    else:
        print(-1)

动态规划

分享丨【算法题单】动态规划（入门/背包/划分/状态机/区间/状压/数位/树形/优化） - 讨论 - 力扣（LeetCode）

有的动态规划也可以用递归做

一般来说dp[i] 会 开(n+1) 或 (n+2) 个，用来存放初始状态

核心：初始化

入门DP

377. 组合总和 Ⅳ - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        @cache
        def dfs(remain):
            if remain == 0:
                return 1
            ans = 0

            for x in nums:
                if x <= remain:
                    ans += dfs(remain - x)
            return ans

        return dfs(target)

198. 打家劫舍 - 力扣（LeetCode）

213. 打家劫舍 II - 力扣（LeetCode）

这里的函数就是打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def rob(self, nums: list[int]) -> int:
        def fun_rob(nums):
            n = len(nums)
            f0 = 0
            f1 = 0
            for i in range(0, n):
                new_f = max(f1, f0 + nums[i])
                f0 = f1
                f1 = new_f
            return f1

        return max(nums[0] + fun_rob(nums[2:-1]), fun_rob(nums[1:]))

有环形就要考虑第一家偷还是不偷，两种情况

3840. 打家劫舍 V - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def rob(self, nums: List[int], colors: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        dp[1] = nums[0]

        for i in range(2, n + 1):
            if colors[i - 1] != colors[i - 2]:
                # 不相同直接拿
                dp[i] = dp[i - 1] + nums[i - 1]
            else:
                # 如果颜色相同就是打家劫舍
                dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])
        return dp[n]

最大子数组和

这里有两种做法：

  1. 定义转移方程，$f[i] = max(f[i-1], 0) + arr[i]$，也叫做 Kadane 算法
  2. 前缀和

53. 最大子数组和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        ans = float("-inf")
        cur = 0
        for x in nums:
            cur = max(cur, 0) + x
            ans = max(ans, cur)
        return ans

1749. 任意子数组和的绝对值的最大值 - 力扣（LeetCode）

只要是涉及绝对值的，可以变成正负各求一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_cur = 0
        min_cur = 0

        max_sum = 0
        min_sum = 0

        for x in nums:
            max_cur = max(max_cur, 0) + x
            min_cur = min(min_cur, 0) + x

            max_sum = max(max_sum, max_cur)
            min_sum = min(min_sum, min_cur)

        return max(max_sum, -min_sum)

网格图 DP

对于一些二维 DP（例如背包、最长公共子序列），如果把 DP 矩阵画出来，其实状态转移可以视作在网格图上的移动

62. 不同路径 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if i == 1 and j == 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        return dp[m][n]

120. 三角形最小路径和 - 力扣（LeetCode）

三角形的题目可以从底往上走，这样好优化

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        m, n = len(triangle), len(triangle[-1])
        dp = [[0] * (i + 1) for i in range(n)]
        dp[-1] = triangle[-1]
        for i in range(n - 2, -1, -1):
            for j, x in enumerate(triangle[i]):
                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + x

        return dp[0][0]

931. 下降路径最小和 - 力扣（LeetCode）

0-1 背包

每个物品只能选一次，即要么选，要么不选。所以 0-1 背包是「选或不选」的代表

416. 分割等和子集 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        S = sum(nums)
        if S % 2 == 1:
            return False
        target = S // 2

        dp = [False] * (target + 1)
        dp[0] = True
        for num in nums:
            # 0-1背包固定写法，从背后算，避免多次选
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[target]

494. 目标和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        s = sum(nums)
        if target > s or (s - target) % 2:
            return 0
        bag = (s - target) // 2

        dp = [0] * (bag + 1)
        dp[0] = 1
        for num in nums:
            for j in range(bag, num - 1, -1):
                dp[j] += dp[j - num]

        return dp[bag]

474. 一和零 - 力扣（LeetCode）

二维背包，和一维的 0/1 背包写法差不多

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for s in strs:
            zero = s.count("0")
            one = s.count("1")

            for i in range(m, zero - 1, -1):
                for j in range(n, one - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1)

        return dp[m][n]

完全背包

物品可以重复选，无个数限制

所以和0-1背包类似，不过反过来

322. 零钱兑换 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        n = len(coins)
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] = min(dp[j], dp[j - coin] + 1)
        return dp[amount] if dp[amount] < float("inf") else -1

518. 零钱兑换 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        n = len(coins)
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] += dp[j - coin]

        return dp[amount]

279. 完全平方数 - 力扣（LeetCode）

经典线性 DP

最长公共子序列

LCS 是 Longest Common Subsequence，最长公共子序列

子序列不要求连续，只要求顺序不变

1143. 最长公共子序列 - 力扣（LeetCode）

递归搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n, m = len(s), len(t)

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> int:
            if i < 0 or j < 0:
                return 0
            if s[i] == t[j]:
                return dfs(i - 1, j - 1) + 1
            return max(dfs(i - 1, j), dfs(i, j - 1))

        return dfs(n - 1, m - 1)

转为dp写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(
                        dp[i - 1][j],
                        dp[i][j - 1]
                    )

        return dp[m][n]

583. 两个字符串的删除操作 - 力扣（LeetCode）

DP注意初始化，初始化可以用dfs考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 注意初始化
        for i in range(m + 1):
            dp[i][0] = i

        for j in range(n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1

        return dp[m][n]

72. 编辑距离 - 力扣（LeetCode）

在删除基础上加替换和插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        @cache
        def dfs(i, j):
            if i < 0:
                return j + 1
            if j < 0:
                return i + 1
            if word1[i] == word2[j]:
                return dfs(i - 1, j - 1)
            return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) + 1

        return dfs(m-1, n-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 注意初始化
        for i in range(m + 1):
            dp[i][0] = i

        for j in range(n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

        return dp[m][n]

最长递增子序列

LIS 是 Longest Increasing Subsequence， 最长递增子序列，> 关系

子序列不要求连续，只要求保持原顺序

300. 最长递增子序列 - 力扣（LeetCode）

dfs做法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)

        @cache
        def dfs(i):
            res = 0
            for j in range(i):
                if nums[j] < nums[i]:
                    res = max(res, dfs(j))
            return res + 1

        return max(dfs(i) for i in range(n))

改为DP做法

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

其实有点类似背包问题

贪心 + 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)

        g = [] # g[i]= 长度为 i+1 的递增子序列的最小结尾


        for x in nums:
            # 找第一个 >= x 的位置 j
            j = bisect_left(g,x) 
            # 不存在，LIS长度增加
            if j == len(g):
                g.append(x)
            # 存在，长度不变，结尾变小
            else:
                g[j] = x
        
        return len(g)

354. 俄罗斯套娃信封问题 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        # 转为最长递增子序列问题
        g = []

        for _, h in envelopes:
            j = bisect_left(g, h)
            if j == len(g):
                g.append(h)
            else:
                g[j] = h

        return len(g)

最长非递减子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from bisect import bisect_right

class Solution:
    def lengthOfLNDS(self, nums: list[int]) -> int:
        g = []

        for x in nums:
            j = bisect_right(g, x)

            if j == len(g):
                g.append(x)
            else:
                g[j] = x

        return len(g)

划分型 DP

139. 单词拆分 - 力扣（LeetCode）

枚举最后一段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordset = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n + 1):

            for j in range(i):
                if dp[j] and s[j:i] in wordset:
                    dp[i] = True
                    break
        return dp[n]

91. 解码方法 - 力扣（LeetCode）

类似受条件限制的爬楼梯 DP，一位 / 两位转移

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(1, n + 1):
            if s[i - 1] != "0":
                dp[i] += dp[i - 1]
            if i >= 2 and 10 <= int(s[i - 2 : i]) <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

1043. 分隔数组以得到最大和 - 力扣（LeetCode）

枚举最后一段长度

$$ dp[i] = \max_{1\le j\le k}(dp[i-j] + j\times \max(arr[i-j:i])) $$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxSumAfterPartitioning(self, arr: list[int], k: int) -> int:
        n = len(arr)

        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            mx = 0

            # 枚举最后一段长度 j
            for j in range(1, min(k, i) + 1):

                # 最后一段不断向左扩展
                mx = max(mx, arr[i - j])

                dp[i] = max(
                    dp[i],
                    dp[i - j] + mx * j
                )

        return dp[n]

状态机 DP

一般定义 f[i][j] 表示前缀 a[:i] 在状态 j 下的最优值，$j$ 一般为有限小数

121. 买卖股票的最佳时机 - 力扣（LeetCode）

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

无限次交易，要定义持有状态

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n + 1)]
        dp[0][1] = float("-inf")

        for i in range(1, n + 1):
            dp[i][0] = max(dp[i - 1][1] + prices[i - 1], dp[i - 1][0])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1])

        return dp[n][0]

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

限制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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        @cache
        def dfs(i, j, hold):
            if j < 0:
                return float("-inf")
            if i < 0:
                # 没持有股票：合法，利润为 0
                if not hold:
                    return 0

                # 没有任何一天，却要求手里持有股票
                # 属于非法状态
                return float("-inf")
            if hold:
                # 当前第 i 天结束后手里有股票，有两种来源：

                # 1. 今天买入
                #    昨天必须是不持有状态
                #    买股票需要支付 prices[i]
                buy = dfs(i - 1, j, False) - prices[i]

                # 2. 今天不操作
                #    昨天就已经持有股票
                keep = dfs(i - 1, j, True)

                return max(keep, buy)

            else:
                # 当前第 i 天结束后手里没有股票，也有两种来源：

                # 1. 今天卖出
                #    昨天必须持有股票
                #    今天卖出后完成了一次交易
                #    所以昨天最多只能完成 j - 1 次交易
                sell = dfs(i - 1, j - 1, True) + prices[i]

                # 2. 今天不操作
                #    昨天就没有持有股票
                keep = dfs(i - 1, j, False)

                return max(sell, keep)

        return dfs(len(prices) - 1, k, False)

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)
        dp = [[0] * 2 for _ in range(n + 2)]
        dp[1][1] = float("-inf")

        for i in range(2, n + 2):
            dp[i][0] = max(dp[i - 1][1] + prices[i - 2], dp[i - 1][0])
            dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i - 2])

        return dp[n + 1][0]

区间 DP

从数组的左右两端不断缩短，求解关于某段下标区间的最优值

一般定义 f[i][j] 表示下标区间 [i,j] 的最优值

516. 最长回文子序列 - 力扣（LeetCode）

DFS做法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @cache
        def dfs(i, j):
            if i > j:
                return 0
            if i == j:
                return 1
            if s[i] == s[j]:
                return dfs(i + 1, j - 1) + 2
            return max(dfs(i + 1, j), dfs(i, j - 1))

        return dfs(0, len(s) - 1)

转DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:

        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

        return dp[0][n - 1]

链表

分享丨【算法题单】链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树） - 讨论 - 力扣（LeetCode）

删除节点

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode | None) -> ListNode | None:
        dummy = ListNode(0, head)
        cur = head
        pre = dummy
        while cur:
            if cur.next and cur.val == cur.next.val:
                val = cur.val

                while cur and cur.val == val:
                    cur = cur.next

                pre.next = cur
            else:
                pre = cur
                cur = cur.next

        return dummy.next

1171. 从链表中删去总和值为零的连续节点 - 力扣（LeetCode）

把前缀和的思路带进来，只不过这里存的是链表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def removeZeroSumSublists(self, head: ListNode | None) -> ListNode | None:
        dummy = ListNode(0, head)
        mp = {} # 无需提前存0，因为从dummy开始

        prefix = 0
        cur = dummy

        while cur:
            prefix += cur.val
            mp[prefix] = cur
            cur = cur.next

        prefix = 0
        cur = dummy
        while cur:
            prefix += cur.val
            cur.next = mp[prefix].next
            cur = cur.next

        return dummy.next

插入节点

147. 对链表进行插入排序 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cur = head

        while cur:
            nxt = cur.next

            pre = dummy
            while pre.next and pre.next.val <= cur.val:
                pre = pre.next
            cur.next = pre.next
            pre.next = cur

            cur = nxt
        return dummy.next

反转链表

206. 反转链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        cur = head
        pre = None
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

92. 反转链表 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reverseBetween(
        self, head: ListNode | None, left: int, right: int
    ) -> ListNode | None:
        dummy = ListNode(0, head)
        p0 = dummy
        for _ in range(left - 1):
            p0 = p0.next
        pre = None
        cur = p0.next

        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

        p0.next.next = cur
        p0.next = pre
        return dummy.next

25. K 个一组翻转链表 - 力扣（LeetCode）

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
class Solution:
    def reverseKGroup(self, head: ListNode | None, k: int) -> ListNode | None:
        dummy = ListNode(0, head)
        group_prev = dummy # 起点的前一个
        while True:
            # 判断是否有 k 个节点
            end = group_prev
            for _ in range(k):
                end = end.next
                if not end:
                    return dummy.next

            # 保存下一组起点
            group_next = end.next
            # 反转当前 k 个节点
            pre = group_next # 重点，因为本来应该是None，这里直接接下一组的头
            cur = group_prev.next
            tail = cur
            for _ in range(k):
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            # 重新连接
            group_prev.next = pre
            group_prev = tail

快慢指针

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)
        slow = fast = dummy
        for _ in range(n):
            fast = fast.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next

        return dummy.next

1721. 交换链表中的节点 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        cur = head
        for _ in range(k - 1):
            cur = cur.next
        p1 = cur
        p2 = head

        while cur.next:
            cur = cur.next
            p2 = p2.next
        p1.val, p2.val = p2.val, p1.val
        return head

141. 环形链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        dummy = ListNode(0, head)
        slow = fast = dummy
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

142. 环形链表 II - 力扣（LeetCode）

Floyd 判圈

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:  # 相遇
                slow = head
                while fast is not slow:  # 再走 a 步
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

合并链表

21. 合并两个有序链表 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def mergeTwoLists(
        self, list1: ListNode | None, list2: ListNode | None
    ) -> ListNode | None:
        dummy = ListNode(0)
        cur = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dummy.next

445. 两数相加 II - 力扣（LeetCode）

注意，即使两边链表都空了，也要加上进位数，所以最好一起放到循环里

这里是因为是正序存放元素，需要先反转一次，从低位开始加

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
class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        def reverse(head):
            cur = head
            pre = None
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            return pre

        h1 = reverse(l1)
        h2 = reverse(l2)

        dummy = ListNode(0)
        cur = dummy
        add = 0
        while h1 or h2 or add:
            val = add
            if h1:
                val += h1.val
                h1 = h1.next
            if h2:
                val += h2.val
                h2 = h2.next
            add = val // 10
            cur.next = ListNode(val % 10)
            cur = cur.next

        return reverse(dummy.next)

二叉树

分享丨【算法题单】链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树） - 讨论 - 力扣（LeetCode）

遍历二叉树

144. 二叉树的前序遍历 - 力扣（LeetCode）

94. 二叉树的中序遍历 - 力扣（LeetCode）

145. 二叉树的后序遍历 - 力扣（LeetCode）

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
# 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]:
        ans = []

        def dfs(node):
            if node is None:
                return
            ans.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ans
    
class Solution:
    def inorderTraversal(self, root: TreeNode | None) -> list[int]:
        ans = []

        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            ans.append(node.val)
            dfs(node.right)

        dfs(root)
        return ans

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []

        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            dfs(node.right)
            ans.append(node.val)

        dfs(root)
        return ans

DFS 递归

在递归的过程中维护值，要求返回是数值或者True/False

最大深度延伸

104. 二叉树的最大深度 - 力扣（LeetCode） 核心基础

1
2
3
4
5
6
7
class Solution:
    def maxDepth(self, root: TreeNode | None) -> int:
        if root is None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return 1 + max(left, right)

110. 平衡二叉树 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isBalanced(self, root: TreeNode | None) -> bool:
        def maxDepth(root):
            if root is None:
                return 0
            left = maxDepth(root.left)
            right = maxDepth(root.right)
            return 1 + max(left, right)

        if root is None:
            return True

        return (
            abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
            and self.isBalanced(root.left)
            and self.isBalanced(root.right)
        )

如果把不平衡带到递归里表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isBalanced(self, root: TreeNode | None) -> bool:
        def maxDepth(root):
            if root is None:
                return 0
            left = maxDepth(root.left)
            if left == -1:
                return -1
            right = maxDepth(root.right)
            if right == -1:
                return -1
            if abs(left - right) > 1:
                return -1
            return 1 + max(left, right)

        return maxDepth(root) != -1

543. 二叉树的直径 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode | None) -> int:
        ans = 0

        def maxDepth(node):
            nonlocal ans

            if node is None:
                return 0

            left = maxDepth(node.left)
            right = maxDepth(node.right)

            # 经过当前节点的最长路径
            ans = max(ans, left + right)

            # 返回当前子树的最大深度
            return 1 + max(left, right)

        maxDepth(root)
        return ans

124. 二叉树中的最大路径和 - 力扣（LeetCode）

和直径类似，返回的是类似深度的信息，中间用ans来计算答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxPathSum(self, root: TreeNode | None) -> int:
        if root is None:
            return 0
        ans = float("-inf")

        def dfs(node):
            nonlocal ans
            if node is None:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)
            ans = max(ans, left + right + node.val)
            return max(max(left, right) + node.val, 0)

        dfs(root)
        return ans

自顶向下 DFS

112. 路径总和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def hasPathSum(self, root: TreeNode | None, targetSum: int) -> bool:
        if root is None:
            return False

        if root.left is None and root.right is None:
            return root.val == targetSum

        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(
            root.right, targetSum - root.val
        )

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def sumNumbers(self, root: TreeNode | None) -> int:
        def dfs(node, num):
            if node is None:
                return 0
            num = 10 * num + node.val
            if node.left is None and node.right is None:
                return num
            return dfs(node.left, num) + dfs(node.right, num)

        return dfs(root, 0)

二叉树结构

100. 相同的树 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
class Solution:
    def isSameTree(self, p: TreeNode | None, q: TreeNode | None) -> bool:
        if p is None or q is None:
            return p is q
        return (
            p.val == q.val
            and self.isSameTree(p.left, q.left)
            and self.isSameTree(p.right, q.right)
        )

101. 对称二叉树 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isSymmetric(self, root: TreeNode | None) -> bool:
        def isMirror(p, q):
            if p is None or q is None:
                return p is q
            return (
                p.val == q.val
                and isMirror(p.left, q.right)
                and isMirror(p.right, q.left)
            )

        return isMirror(root.left, root.right)

951. 翻转等价二叉树 - 力扣（LeetCode）

直接递归判断镜像与非镜像即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if root1 is None or root2 is None:
            return root1 is root2
        if root1.val != root2.val:
            return False
        return (
            self.flipEquiv(root1.left, root2.left)
            and self.flipEquiv(root1.right, root2.right)
        ) or (
            self.flipEquiv(root1.left, root2.right)
            and self.flipEquiv(root1.right, root2.left)
        )

226. 翻转二叉树 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        left = self.invertTree(root.left) 
        right = self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

617. 合并二叉树 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def mergeTrees(
        self, root1: TreeNode | None, root2: TreeNode | None
    ) -> TreeNode | None:
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        return TreeNode(
            root1.val + root2.val,
            self.mergeTrees(root1.left, root2.left),  # 合并左子树
            self.mergeTrees(root1.right, root2.right),
        )  # 合并右子树

二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

朴素的递归，中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isValidBST(self, root: TreeNode | None) -> bool:
        pre = float("-inf")

        def dfs(node):
            nonlocal pre
            if node is None:
                return True

            if not dfs(node.left):
                return False
            if node.val <= pre:
                return False
            pre = node.val
            return dfs(node.right)

        return dfs(root)

上下界递归

往左走上界就变成当前node的值，往右界走下界就变成当前node的值

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isValidBST(self, root: TreeNode | None) -> bool:

        def dfs(node, low, high):
            if node is None:
                return True

            if not low < node.val < high:
                return False

            return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)

        return dfs(root, -inf, inf)

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

类似二叉搜索树的遍历，直接从底下开始计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        ans = 0

        def dfs(node):
            nonlocal k, ans
            if node is None:
                return
            dfs(node.left)
            k -= 1
            if k == 0:
                ans = node.val
                return
            dfs(node.right)

        dfs(root)
        return ans

回溯

这种回溯写法会比较固定，满足条件的一条if，另一边继续dfs，最后一起恢复现场

257. 二叉树的所有路径 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def binaryTreePaths(self, root: TreeNode | None) -> list[str]:
        ans = []
        path = []

        def dfs(node):
            if node is None:
                return
            path.append(node.val)
            if node.left is None and node.right is None:
                ans.append("->".join(map(str, path)))
            else:
                dfs(node.left)
                dfs(node.right)
            path.pop()

        dfs(root)
        return ans

113. 路径总和 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def pathSum(self, root: TreeNode | None, targetSum: int) -> list[list[int]]:

        ans = []
        path = []

        def dfs(node, prefix):
            if node is None:
                return
            prefix += node.val
            path.append(node.val)
            if node.left is None and node.right is None and prefix == targetSum:
                ans.append(path.copy())
            else:
                dfs(node.left, prefix)
                dfs(node.right, prefix)
            prefix -= node.val
            path.pop()

        dfs(root, 0)
        return ans

437. 路径总和 III - 力扣（LeetCode）

区间要想到前缀和，因为这里不一定从头开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans = 0
        prefix = defaultdict(int)
        prefix[0] = 1

        def dfs(node, s):
            nonlocal ans
            if node is None:
                return
            s += node.val
            ans += prefix[s - targetSum]
            prefix[s] += 1
            dfs(node.left, s)
            dfs(node.right, s)

            prefix[s] -= 1

        dfs(root, 0)
        return ans

最近公共祖先

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

满足左中右的顺序，如果是最近的公共祖先就会不满足都大于或都小于了

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lowestCommonAncestor(
        self, root: TreeNode, p: TreeNode, q: TreeNode
    ) -> TreeNode:

        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        return root

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

无法利用左中右了，只能从底往上找

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        if root is None or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        return left if left else right

层序遍历 BFS

102. 二叉树的层序遍历 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def levelOrder(self, root: TreeNode | None) -> list[list[int]]:
        if root is None:
            return []

        dq = deque([root])
        ans = []
        while dq:
            n = len(dq)
            layer = []
            for _ in range(n):
                node = dq.popleft()
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)
                layer.append(node.val)
            ans.append(layer)
        return ans

199. 二叉树的右视图 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        dq = deque([root])
        ans = []
        while dq:
            n = len(dq)
            for i in range(n):
                node = dq.popleft()
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)
                if i == n - 1:
                    ans.append(node.val)
        return ans

回溯

分享丨【算法题单】链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树） - 讨论 - 力扣（LeetCode）

子集型

核心是选或不选

78. 子集 - 力扣（LeetCode）

选或不选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        ans = []
        path = []
        n = len(nums)

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return
            path.append(nums[i])
            dfs(i + 1)
            path.pop()
            dfs(i + 1)

        dfs(0)
        return ans

用组合的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        ans = []
        path = []
        n = len(nums)

        def dfs(i):
            ans.append(path.copy())

            for j in range(i, n):
                path.append(nums[j])
                dfs(j + 1)
                path.pop()

        dfs(0)
        return ans

2597. 美丽子集的数目 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def beautifulSubsets(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        cnt = defaultdict(int)

        def dfs(i):
            if i == n:
                return 1
            # 不选 nums[i]
            ans = dfs(i + 1)
            # 选 nums[i]
            x = nums[i]
            if cnt[x - k] == 0:
                cnt[x] += 1
                ans += dfs(i + 1)
                cnt[x] -= 1
            return ans

        return dfs(0) - 1

39. 组合总和 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        path = []
        ans = []
        n = len(candidates)

        def dfs(i, remain):
            if remain < 0:
                return
            if remain == 0:
                ans.append(path.copy())
                return
            if i == n:
                return
            path.append(candidates[i])
            dfs(i, remain - candidates[i])
            path.pop()
            dfs(i + 1, remain)

        dfs(0, target)
        return ans

划分型

131. 分割回文串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def partition(self, s: str) -> list[list[str]]:
        ans = []
        path = []
        n = len(s)

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return
            for end in range(i, n):
                sub = s[i : end + 1]

                if sub != sub[::-1]:
                    continue

                path.append(sub)
                dfs(end + 1)
                path.pop()

        dfs(0)
        return ans

这里直接用 [::-1]判断回文

93. 复原 IP 地址 - 力扣（LeetCode）

切还是不切

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
class Solution:
    def restoreIpAddresses(self, s: str) -> list[str]:
        ans = []
        path = [0] * 4
        n = len(s)

        def dfs(i, j, ip_val):
            if i == n:
                if j == 4:
                    a, b, c, _ = path
                    ans.append(f"{s[:a]}.{s[a:b]}.{s[b:c]}.{s[c:]}")
                return
            if j == 4:
                return
            ip_val = ip_val * 10 + int(s[i])

            if ip_val > 255:
                return
            if ip_val > 0:
                dfs(i + 1, j, ip_val)
            path[j] = i + 1
            dfs(i + 1, j + 1, 0)

        dfs(0, 0, 0)
        return ans

140. 单词拆分 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        word_set = set(wordDict)
        n = len(s)
        path = []
        ans = []

        def dfs(i, j):
            if i == n:
                if j == n:
                    ans.append(" ".join(word for word in path))
                return
            if s[j : i + 1] in word_set:
                path.append(s[j : i + 1])
                dfs(i + 1, i + 1)
                path.pop()
            dfs(i + 1, j)

        dfs(0, 0)
        return ans

组合型

直接枚举，利用条件截断

77. 组合 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        ans = []
        path = []

        def dfs(i):
            if len(path) == k:
                ans.append(path.copy())
                return

            # 剪枝：剩余数字不够
            if n - i + 1 < k - len(path):
                return

            for j in range(i, n + 1):
                path.append(j)
                dfs(j + 1)
                path.pop()

        dfs(1)
        return ans

216. 组合总和 III - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        path = []

        def dfs(i):
            if len(path) == k:
                if sum(path) == n:
                    ans.append(path.copy())
                return

            for j in range(i, 10):
                path.append(j)
                dfs(j + 1)
                path.pop()

        dfs(1)
        return ans

22. 括号生成 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def generateParenthesis(self, n: int) -> list[str]:

        path = []
        ans = []

        def dfs(left, right):
            if left == n and right == n:
                ans.append("".join(path))
                return

            if left < n:
                path.append("(")
                dfs(left + 1, right)
                path.pop()

            if right < left:
                path.append(")")
                dfs(left, right + 1)
                path.pop()

        dfs(0, 0)
        return ans

排序型

一般就是全排列，但是调序

46. 全排列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        path = []
        ans = []
        n = len(nums)
        used = [False] * n

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return

            for j in range(n):
                if not used[j]:
                    used[j] = True
                    path.append(nums[j])
                    dfs(i + 1)
                    path.pop()
                    used[j] = False

        dfs(0)
        return ans

51. N 皇后 - 力扣（LeetCode）

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
class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        path = []
        ans = []
        cols = set()
        diag1 = set()
        diag2 = set()

        def dfs(row):
            if row == n:
                res = ["." * c + "Q" + "." * (n - c - 1) for c in path]
                ans.append(res)
                return
            for col in range(n):
                if col in cols or row - col in diag1 or row + col in diag2:
                    continue
                path.append(col)
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)

                dfs(row + 1)

                path.pop()
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        dfs(0)
        return ans

含重复元素

90. 子集 II - 力扣（LeetCode）

注意，有重复元素的时候经常要排序

延续子集选或不选的思想，但是这里要跳过重复值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        path = []
        ans = []
        n = len(nums)

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return
            path.append(nums[i])
            dfs(i + 1)
            path.pop()
            j = i + 1
            while j < n and nums[j] == nums[i]: # 这种写法是针对排序后的
                j += 1
            dfs(j)

        dfs(0)
        return ans

40. 组合总和 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        ans = []
        path = []
        n = len(candidates)

        def dfs(i, s):
            if s > target:
                return
            if i == n:
                if s == target:
                    ans.append(path.copy())
                return
            path.append(candidates[i])
            dfs(i + 1, s + candidates[i])
            path.pop()
            j = i + 1
            while j < n and candidates[j] == candidates[i]:
                j += 1
            dfs(j, s)

        dfs(0, 0)
        return ans

491. 非递减子序列 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def findSubsequences(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans = []
        path = []

        def dfs(i):
            if i == n:
                if len(path) > 1:
                    ans.append(path.copy())
                return

            # 选 nums[i]
            if not path or nums[i] >= path[-1]:
                path.append(nums[i])
                dfs(i + 1)
                path.pop()

            # 不选 nums[i]，避免重复
            if not path or nums[i] != path[-1]:
                dfs(i + 1)

        dfs(0)
        return ans

搜索

外层循环负责寻找起点，内部dfs用于迭代任务匹配

79. 单词搜索 - 力扣（LeetCode）

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
class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:

        cnt = len(word)
        ans = False
        m, n = len(board), len(board[0])
        used = [[False] * n for _ in range(m)]

        def dfs(i, j, k):
            nonlocal ans
            if ans or i < 0 or i > m - 1 or j < 0 or j > n - 1 or used[i][j]:
                return
            if board[i][j] != word[k]:
                return
            # 已经匹配到最后一个字符
            if k == cnt - 1:
                ans = True
                return
            used[i][j] = True

            dfs(i, j + 1, k + 1)
            dfs(i + 1, j, k + 1)
            dfs(i - 1, j, k + 1)
            dfs(i, j - 1, k + 1)

            used[i][j] = False

        for i in range(m):
            for j in range(n):
                dfs(i, j, 0)
                if ans:
                    return True
        return False

1219. 黄金矿工 - 力扣（LeetCode）

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
class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        used = [[False] * n for _ in range(m)]

        def dfs(i, j, k):
            nonlocal ans
            if (
                i > m - 1
                or i < 0
                or j > n - 1
                or j < 0
                or used[i][j]
                or grid[i][j] == 0
            ):
                ans = max(ans, k)
                return
            k += grid[i][j]
            used[i][j] = True
            dfs(i, j + 1, k)
            dfs(i, j - 1, k)
            dfs(i + 1, j, k)
            dfs(i - 1, j, k)
            used[i][j] = False
            k -= grid[i][j]

        for i in range(m):
            for j in range(n):
                dfs(i, j, 0)

        return ans

面试常见题

中心拓展法

5. 最长回文子串 - 力扣（LeetCode）

分奇偶的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ans_left = ans_right = 0

        for i in range(n):
            l = r = i
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # 循环结束后，s[l+1] 到 s[r-1] 是回文串
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r

        for i in range(n - 1):
            l, r = i, i + 1
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r

        return s[ans_left:ans_right]

合二为一，用一个循环统一枚举这两种情况

  • 每个字符都可以作为回文中心，共 $n$ 个
  • 每两个相邻字符之间也可以作为回文中心，共 $n-1$ 个

一共有

$$ 2n-1 $$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ans_left = ans_right = 0

        for i in range(2 * n - 1):
            l, r = i // 2, (i + 1) // 2
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # 循环结束后，s[l+1] 到 s[r-1] 是回文串
            if r - l - 1 > ans_right - ans_left:
                ans_left, ans_right = l + 1, r  # 左闭右开区间

        return s[ans_left: ans_right]

647. 回文子串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        ans = 0
        for i in range(2 * n - 1):
            l, r = i // 2, (i + 1) // 2
            while l >= 0 and r < n and s[l] == s[r]:
                ans += 1
                l -= 1
                r += 1
        return ans

区间

763. 划分字母区间 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        last = {c: i for i, c in enumerate(s)} # 每个字母最后出现的下标
        ans = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c]) # 更新当前区间右端点的最大值
            if i == end: # 当前区间合并完毕
                ans.append(end - start + 1)
                start = i + 1
        return ans

1326. 灌溉花园的最少水龙头数目 - 力扣（LeetCode）

560. 和为 K 的子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans = 0
        mp = {0: 1}
        prefix = 0

        for num in nums:
            prefix += num
            ans += mp.get(prefix - k, 0)
            mp[prefix] = mp.get(prefix, 0) + 1

        return ans

862. 和至少为 K 的最短子数组 - 力扣（LeetCode）

这种做法会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        ans = float("inf")
        latest = {0: -1}
        prefix = 0
        min_prefix = 0

        for i, num in enumerate(nums):
            prefix += num
            max_prefix = prefix - k

            for target in range(min_prefix, max_prefix + 1):
                if target in latest:
                    ans = min(ans, i - latest[target])

            min_prefix = min(min_prefix, prefix)
            latest[prefix] = i

        return -1 if ans == float("inf") else ans

用双端队列代替遍历查找，就可以跳过不存在的那些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        ans = float("inf")
        prefix = 0
        dq = deque([(0, -1)])

        for i, num in enumerate(nums):
            prefix += num
            # 找到满足和 >= k 的子数组
            while dq and prefix - dq[0][0] >= k:
                _, j = dq.popleft()
                ans = min(ans, i - j)

            # 删除不可能成为最优解的前缀和
            # 新候选前缀和小且编号更大更适合作为答案
            while dq and dq[-1][0] >= prefix:
                dq.pop()

            dq.append((prefix, i))
        return -1 if ans == float("inf") else ans

数组

215. 数组中的第K个最大元素 - 力扣（LeetCode）

Quick Select

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
class Solution:
    def partition(self, nums: List[int], left: int, right: int) -> int:
        i = randint(left, right)
        pivot = nums[i]
        nums[i], nums[left] = nums[left], nums[i]
        i, j = left + 1, right
        while True:
            while i <= j and nums[i] < pivot:
                i += 1
            # 此时 nums[i] >= pivot

            while i <= j and nums[j] > pivot:
                j -= 1
            # 此时 nums[j] <= pivot

            if i >= j:
                break
            # 维持循环不变量
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1
        # 循环结束后
        # [ pivot | <=pivot | >=pivot ]
        #   ^             ^   ^     ^
        #   left          j   i     right
        nums[left], nums[j] = nums[j], nums[left]
        return j

    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        target_index = n - k
        left, right = 0, n - 1
        while True:
            i = self.partition(nums, left, right)
            if i == target_index:
                return nums[i]
            if i > target_index:
                right = i - 1
            else:
                left = i + 1

堆选择

1
2
3
4
5
6
7
8
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]