哈希表

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

暴力解法

遍历，时间复杂度为$O(N^2)$，空间复杂度为$O(1)$

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return []

哈希表

时间复杂度$O(N)$，空间复杂度$O(N)$，为哈希表的开销

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

python 的 dict 和 C++ 的 unordered_map 基本一致

涉及到in判断就不能用defaultdict

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

解释：

  • 在 strs 中没有字符串可以通过重新排列来形成 "bat"
  • 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此
  • 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此

示例 2:

输入: strs = [“”]

输出: [[“”]]

示例 3:

输入: strs = [“a”]

输出: [[“a”]]

可以重构的字符串在排序后结果相同，可以以此作为哈希表的键，原字符串作为值，最后输出哈希表值的元组

哈希表排序

1
2
3
4
5
6
7
8
9
10
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # key 不存在时，自动给一个空列表
        mp = defaultdict(list)

        for st in strs:
            key = "".join(sorted(st))  # sorted排序出来是list
            mp[key].append(st)

        return list(mp.values())

这里用的不是sort而是sorted，因为st是字符串，而且不能对原对象产生修改

sorted不对原对象修改，可用于字符串、列表、任何可迭代对象，生成list，所以需要"".join转为str

时间复杂度为O(nklogk)，k为strs中字符串的最大长度，空间复杂度为nk

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度

请你设计并实现时间复杂度为 O(n) 的算法解决此问题

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

1
2
输入：nums = [1,0,1,2]
输出：3

既然要时间复杂度为O(n)那必然不能暴力枚举了

如果对每个数都向左、向右扩展，那最坏会退化成O(n²)

破解方法：只有当一个数是“连续序列起点”时，才从它开始向右数

不需要重复数字，直接用set快速剔除，保留不同数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)
        ans = 0
        for num in nums_set: # 遍历哈希表
            # 没有更小的起始数时开始计算
            if num - 1 in nums_set:
                continue
            max_len = 1
            while num + max_len in nums_set:
                max_len += 1
            ans = max(ans, max_len)

        return ans

一个小优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)
        n = len(nums_set)
        ans = 0
        for num in nums_set:  # 遍历哈希表
            # 没有更小的起始数时开始计算
            if num - 1 in nums_set:
                continue
            max_len = 1
            while num + max_len in nums_set:
                max_len += 1
            ans = max(ans, max_len)
            if ans * 2 >= n: # ans 不可能变得更大
                break
        return ans

如果长度已经超过一半了，那一定就是最长的

双指针

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

请注意 ，必须在不复制数组的情况下原地对数组进行操作

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

交换法

不复制数组只能是直接交换，末尾都是0，头部都是非0值

从左到右遍历数组，维护一个下标指向下一个“应该放非零元素的位置”

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i0 = 0
        for i in range(len(nums)):
            if nums[i]: # 把非0的往左边放
                nums[i], nums[i0] = nums[i0], nums[i]
                i0 += 1

先填充后补0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        idx = 0
        # 先把非0的放入前端
        for num in nums:
            if num != 0:
                nums[idx] = num
                idx += 1
        # 后端补0
        for i in range(idx, n):
            nums[i] = 0

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量

示例 1：

1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2：

1
2
输入：height = [1,1]
输出：1

发现盛水量等于(right-left)*min(height[left],height[right])

直接用双指针走就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxArea(self, height: List[int]) -> int:
        area, ans = 0, 0
        left, right = 0, len(height) - 1
        while left < right:
            area = min(height[left], height[right]) * (right - left)
            ans = max(ans, area)
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return ans

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

排序 + 双指针

首先注意到不能有重复输出(不同排列方式)，所以最好的去重就是先排序，后续只需要移动指针判断是否值相等跳过自动就实现去重

固定一个，从左往右走

剩下两个使用左右指针，和小于0加左边，和大于0加右边，如果和为0输出，这个时候左右指针同时向中心移动，注意，移动时候需要判断是否值重复，不然会有重复输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        ans = []
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 最小和>0，直接结束
            if nums[i] + nums[i + 1] + nums[i + 2] > 0: 
                break
            # 最大和<0，直接右移
            if nums[i] + nums[-1] + nums[-2] < 0:
                continue
            j, k = i + 1, n - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s == 0:
                    ans.append([nums[i], nums[j], nums[k]])
                    j += 1
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                elif s < 0:
                    j += 1
                else:
                    k -= 1
        return ans

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水(蓝色部分表示雨水)。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

首先要知道雨水怎么接的，看图可以发现是凹处能接到水，转为代码语言就是高度小于左侧右侧最大值其中较小值的地方

前后缀

具体来说，对于下标i，能接的雨水量等于下标i处的水能到达的最大高度减去heigh[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        leftmax = list()
        rightmax = list()
        max_l, max_r = 0, 0  # 当前最大值
        for i in range(n):
            max_l = max(max_l, height[i])
            max_r = max(max_r, height[n - 1 - i])
            leftmax.append(max_l)
            rightmax.append(max_r)

        rightmax = rightmax[::-1] # 反转right

        water = 0
        for i in range(n):
            water += min(leftmax[i], rightmax[i]) - height[i] # 两者小值-高度

        return water

时间复杂度和空间复杂度都是O(n)

能否降低空间复杂度呢？

相向双指针

因为虽然不知道右侧最大值，但是右侧的max至少大于等于现在右指针的高度

在「谁小移动谁」的规则下，相遇的位置一定是最高的柱子，这个柱子是无法接水的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height)-1
        water = 0
        leftmax, rightmax = 0, 0
        while left < right:
            leftmax = max(leftmax, height[left])
            rightmax = max(rightmax, height[right])
            if leftmax < rightmax:
                water += leftmax - height[left]
                left += 1
            else:
                water += rightmax - height[right]
                right -= 1

        return water

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        st = []
        ans = 0
        for i in range(n):
            # 当前柱子 height[i] 作为“右边界”
            # 如果比栈顶柱子高，说明可以形成一个“凹槽”
            while st and height[i] >= height[st[-1]]:
                bottom_h = height[st.pop()]
                # 如果栈空，说明左边没有更高的柱子，无法形成容器
                if len(st) == 0:
                    break
                left = st[-1]
                dh = min(height[left], height[i]) - bottom_h
                ans += dh * (i - left - 1)
            st.append(i)
        return ans

找被两堵墙夹住的低谷，并按层结算

滑动窗口

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

哈希集合（布尔数组）

出现了不重复，要想到使用set，但是还需要记录长度，所以又要用到左右指针

左指针记录无重复字符串的开端，右指针记录无重复字符串的尾端，长度为right-left+1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        left = 0
        max_len = 0
        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left]) # 删除直到无s[right]
                left += 1
            seen.add(s[right])
            max_len = max(max_len, right - left + 1)
        return max_len

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • s 和 p 仅包含小写字母

方法一：滑动窗口

异位词其实就是组成的字母相同，如果枚举匹配那么复杂度直接爆炸，构建一个和p相同长度的滑动窗口

统计数量就行(注意，这是因为这里只有小写字母)，如果有字符或者空格就比较麻烦了

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 findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)
        if s_len < p_len: # p长度必须小于等于s
            return []
        ans = []
        s_count = [0] * 26
        p_count = [0] * 26
        for i in range(p_len):
            p_count[ord(p[i]) - ord("a")] += 1
            s_count[ord(s[i]) - ord("a")] += 1
        if p_count == s_count:
            ans.append(0)

        for i in range(s_len - p_len):
            s_count[ord(s[i]) - ord("a")] -= 1  # 剔除窗口头部字母
            s_count[ord(s[i + p_len]) - ord("a")] += 1  # 加入窗口下一个字母

            if s_count == p_count:
                ans.append(i + 1)

        return ans

方法二：定长窗口

定长，不断右移，判断是否匹配，匹配则加入左端点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cnt_p = Counter(p)  # 统计 p 的每种字母的出现次数
        cnt_s = Counter()  # 统计 s 的长为 len(p) 的子串 t 的每种字母的出现次数
        ans = []

        for right, c in enumerate(s):
            cnt_s[c] += 1  # 右端点字母进入窗口
            left = right - len(p) + 1
            if left < 0:  # 窗口长度不足 len(p)
                continue
            if cnt_s == cnt_p:  # t 和 p 的每种字母的出现次数都相同
                ans.append(left)
            cnt_s[s[left]] -= 1  # 左端点字母离开窗口
        return ans

最小覆盖子串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口子串，使得该子串包含 t 中的每一个字符(包括重复字符)。如果没有这样的子串，返回空字符串 ""

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

创建计数表，不断滑动，如果子串涵盖t，就不断右移左端点直到不涵盖

移动过程中更新最短子串的左右端点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt_t = Counter(t) # t 中字母的出现次数
        cnt_s = Counter()  # s 子串字母的出现次数
        ans_left, ans_right = -1, len(s)
        left = 0

        for right, c in enumerate(s): # 移动子串右端点
            cnt_s[c] += 1 # 右端点字母移入子串
            while cnt_s >= cnt_t: # 涵盖 
                if right - left < ans_right - ans_left: # 找到更短的子串
                    ans_left, ans_right = left, right
                cnt_s[s[left]] -= 1  # 左端点字母移出子串
                left += 1

        return "" if ans_left < 0 else s[ans_left : ans_right + 1]

时间复杂度为O(|∑|m+n)，空间复杂度为O(|∑|)

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度

如果不存在符合条件的子数组，返回 0

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

同样滑动窗口，不断右扩即可

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        s = l =0
        min_len = inf
        for r in range(len(nums)):
            s += nums[r]
            while s >= target: # 满足要求
                min_len = min(min_len, r - l + 1)
                s -= nums[l]
                l += 1 # 左端点右移
        return min_len if min_len <=n else 0

子串

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数

子数组是数组中元素的连续非空序列。

示例 1：

1
2
输入：nums = [1,1,1], k = 2
输出：2

示例 2：

1
2
输入：nums = [1,2,3], k = 3
输出：2

前缀和 + 哈希表优化

比如需要从下标i到j的子串，那么是不是可以等价于从0到j的子串减去从0到i的子串，这样只要遍历一次就能获得所有的子串

prefix2 - prefix1 = k 转变为查找已经存进哈希表的值里有没有等于 prefix2 - k 的

注意，要在哈希表里默认加一个0，这样才能准确认到自身单元素的情况

1
2
3
4
5
6
7
8
9
10
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix = defaultdict(int)
        prefix[0] = 1
        ans = s = 0
        for x in nums:
            s += x
            ans += prefix[s - k]
            prefix[s] += 1
        return ans

改成计算元素和等于 k 的最长子数组

同样做法，但是这个时候要把计数改为最早出现位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestSubarraySumK(self, nums: List[int], k: int) -> int:
        first = {0: -1}   # 前缀和 -> 最早出现位置
        s = 0
        ans = 0

        for i, x in enumerate(nums):
            s += x
            if s - k in first:
                ans = max(ans, i - first[s - k])
            if s not in first:      # 只记录第一次出现
                first[s] = i

        return ans

改成计算元素和等于 k 的最短子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def shortestSubarraySumK(self, nums: List[int], k: int) -> int:
        last = {0: -1}    # 前缀和 -> 最近一次出现位置
        s = 0
        ans = float('inf')

        for i, x in enumerate(nums):
            s += x
            if s - k in last:
                ans = min(ans, i - last[s - k])
            last[s] = i   # 覆盖，保留最近位置

        return ans if ans != float('inf') else 0

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

1
2
输入：nums = [1], k = 1
输出：[1]

在python中

结构 C++ Python
堆 priority_queue heapq
队列 deque deque
哈希 unordered_map dict

单调队列

  1. 右边入（元素进入队尾，同时维护队列单调性）
  2. 左边出（元素离开队首）
  3. 记录/维护答案（根据队首）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        dq = deque()
        ans = []
        for i, num in enumerate(nums):
            # 1. 进
            while dq and num >= nums[dq[-1]]:
                dq.pop()
            dq.append(i)
            # 2. 出
            left = i - k + 1
            # 因为每次只移动一步，所以最多只会有一个不合规
            if dq[0] < left:
                dq.popleft()
            # 3. 记录答案
            if left >= 0:
                ans.append(nums[dq[0]])

        return ans

绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：nums = [8,2,4,7], limit = 4
输出：2 
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此，满足题意的最长子数组的长度为 2 。

示例 2：

1
2
3
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4 
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：

1
2
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

类似滑动窗口最大值的做法，但是这里需要维护两个双端队列，因为绝对差是最大值-最小值

而且刚刚是固定窗口，这题不固定窗口，和滑动窗口一样，right就直接用i，不断移left

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 longestSubarray(self, nums: List[int], limit: int) -> int:
        min_q = deque()
        max_q = deque()
        ans = left = 0
        for i, num in enumerate(nums):
            # 1. 右边入
            while min_q and num < nums[min_q[-1]]:
                min_q.pop()
            min_q.append(i)
            while max_q and num > nums[max_q[-1]]:
                max_q.pop()
            max_q.append(i)
            # 2. 左边出
            while nums[max_q[0]] - nums[min_q[0]] > limit:
                left += 1
                # 因为每次只移动一步，所以最多只会有一个不合规
                if min_q[0] < left:
                    min_q.popleft()
                if max_q[0] < left:
                    max_q.popleft()
            ans = max(ans, i - left + 1)
        return ans

普通数组

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组(子数组最少包含一个元素)，返回其最大和

子数组是数组中的一个连续部分

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大为 6

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解

动态规划

第一思路应该会想到和和为 K 的子数组这道题一样的前缀和，但是更简单，只需要判断是从当前位置重新开始还是继续延伸

用 $f[i]$ 表示以第 $i$ 个数结尾的连续子数组的最大和
$$
f[i] =
\begin{cases}
nums[i], & i = 0 \\
\max(f[i-1], 0) + nums[i], & i \ge 1
\end{cases}
$$

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

如果是返回最小值

1
2
3
4
5
6
7
8
class Solution:
    def minSubArray(self, nums: List[int]) -> int:
        ans = inf 
        f = 0
        for x in nums:
            f = min(f, 0) + x
            ans = min(ans, f)
        return ans

如果改成返回和最大的子数组

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

        start = 0          # 当前子数组起点
        best_l = best_r = 0

        for i, x in enumerate(nums):
            if f < 0:
                f = x
                start = i   # 重新开始
            else:
                f += x

            if f > ans:
                ans = f
                best_l = start
                best_r = i

        return nums[best_l:best_r + 1]

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

1
2
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]

合并区间首先排序区间，这样方便边界判定，合并以后只需要看前一个的Right和后一个Left是否有重叠，没重叠就开新区间

1
2
3
4
5
6
7
8
9
10
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])  # 按起点排序
        ans = []
        for x in intervals:
            if ans and x[0] <= ans[-1][1]: # 如果新区间起点小于合并区间中和殿
                ans[-1][1] = max(ans[-1][1], x[1]) # 合并区间
            else:
                ans.append(x)  # 新开区间
        return ans

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

示例 1:

1
2
3
4
5
6
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

首先，要考虑k大于数组长度，会出现一些循环，所以需要计算最终实际的轮转数k%len(nums)

移动起始会发现就是把后k个元素放到前面

数组翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n

        def reverse(l, r):
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

这种方法每个元素都被翻转两次，时间复杂度为O(n)，空间复杂度为O(1)，最推荐

切片拼接

相当于使用额外的数组

将原数组下标为i的元素放至新数组下标为 (i+k) mod n 的位置，最后将新数组拷贝至原数组即可

1
2
3
4
5
6
7
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        nums[:] = nums[-k:] + nums[:-k]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        res = [0] * n

        for i in range(n):
            res[(i + k) % n] = nums[i]

        nums[:] = res

有额外开支，空间复杂度为O(n)

环状替换

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 rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        move = 0
        for start in range(n):
            if move >= n:
                break
            cur = start
            prev = nums[start]

            while True:
                nxt = (cur + k) % n
                nums[nxt], prev = prev, nums[nxt]
                cur = nxt
                move += 1

                if cur == start:
                    break

除了自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题

示例 1:

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？(出于对空间复杂度分析的目的，输出数组 不被视为 额外空间)

最直觉的想法一定是总乘积 / nums[i]，但是这里限制了除法

左右乘积列表

answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积，换句话说，如果知道了 i 左边所有数的乘积，以及 i 右边所有数的乘积，就可以算出 answer[i]

  • 定义 pre[i] 表示从 nums[0] 到 nums[i−1] 的乘积
  • 定义 suf[i] 表示从 nums[i+1] 到 nums[n−1] 的乘积

$$
pre[i] = pre[i-1]\cdot nums[i-1]\\
suf[i] = suf[i+1]\cdot nums[i+1]
$$

初始值全定为1，负责边界
$$
answer[i] = pre[i]\cdot suf[i]
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1] * n
        for i in range(1, n):
            pre[i] = pre[i - 1] * nums[i - 1]
        suf = [1] * n
        for i in range(n - 2, -1, -1):
            suf[i] = suf[i + 1] * nums[i + 1]
        ans = [0] * n
        for i in range(n):
            ans[i] = pre[i] * suf[i]
        return ans

怎么才能让空间复杂度降为O(1)呢

就不构建两个数组，直接把乘操作放到一个数组的两步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n
        # 前缀乘积
        for i in range(1, n):
            ans[i] = ans[i - 1] * nums[i - 1]
        # 后缀乘积（用一个变量来记录）
        suf = 1
        for i in range(n - 1, -1, -1): # 注意这里要从n-1开始了
            ans[i] *= suf
            suf *= nums[i]

        return ans

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案

示例 1：

1
2
3
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

1
2
3
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

1
2
3
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

哈希保底

因为限制了内存，没法直接用哈希表，如果不限制内存：

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

        for x in nums:
            if x > 0:
                mp[x] = True

        n = len(nums)
        for i in range(1, n + 2):
            if i not in mp:
                return i

置换法

最关键的点：如果数组长度是 n，在恢复后，数组应当有 [1, 2, ..., N] 的形式

找第一个不符合的位置，如果都符合就是都存在，返回n+1

对于num[i]，匹配的位置应该是nums[nums[i]-1]，注意要判断那个位置坐的对不对了已经，如果对了就不要重复换，避免死循环

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

        # 第一阶段：把能放到正确位置的数放到正确位置
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                correct_dix = nums[i] - 1
                nums[i], nums[correct_dix] = nums[correct_dix], nums[i]

        # 第二阶段：找第一个不符合 nums[i] == i + 1 的位置
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        # 如果 1 ~ n 都在，答案就是 n + 1
        return n + 1

矩阵

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 **0 **，请使用原地算法

示例 1：

1
2
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

1
2
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

使用标记数组

最直观的做法，遍历矩阵，用标记数组记录是否有0出现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        row, col = [False] * m, [False] * n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = col[j] = True
        
        for i in range(m):
            for j in range(n):
                if row[i] or col[j]:
                    matrix[i][j] = 0

这种方法：时间复杂度：O(m * n)，空间复杂度：O(m + n)

更近一步就是将空间复杂度降低至O(1)

使用两个标记变量

可以把矩阵的第一行和第一列的位置用来作为标记，因为如果一行或者一列上有0，那么这些位置本身也要置0

但这样的话无法记录它们本身是否为0，所以需要引入两个标记变量来分别记录第一行和第一列是否原本包含0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        flag_col0 = any(matrix[i][0] == 0 for i in range(m))
        flag_row0 = any(matrix[0][j] == 0 for j in range(n))

        for i in range(1, m): # 无需遍历第一行
            for j in range(1, n): # 无需遍历第一列
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        for i in range(1, m): # 跳过第一行，留到最后修改
            for j in range(1, n): # 跳过第一列，留到最后修改
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        # 如果第一列一开始就包含 0，那么把第一列全变成 0
        if flag_col0:
            for i in range(m):
                matrix[i][0] = 0
		 # 如果第一行一开始就包含 0，那么把第一行全变成 0
        if flag_row0:
            for j in range(n):
                matrix[0][j] = 0

时间复杂度：O(m * n)，循环遍历矩阵两次

空间复杂度：O(1)

压缩到1个标记变量实在是可读性太差了，放弃

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素

示例 1：

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

按层模拟

把向右移和向下移看作一组，把向左移和向上移看作一组，每一组必须在除去扫过的部分还有矩阵才能继续

必须半圈检查一次，不然容易有一条边被重复输出

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 spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        left, right = 0, len(matrix[0]) - 1
        top, bottom = 0, len(matrix) - 1
        ans = []
        while left <= right and top <= bottom:
            # 从左往右
            for j in range(left, right + 1):
                ans.append(matrix[top][j])
            top += 1
            # 从上往下
            for i in range(top, bottom + 1):
                ans.append(matrix[i][right])
            right -= 1
            
            # 必须满足才能继续输出
            if top > bottom or left > right:
                break

            # 从右往左
            for j in range(right, left - 1, -1):
                ans.append(matrix[bottom][j])
            bottom -= 1
            # 从下往上
            for i in range(bottom, top - 1, -1):
                ans.append(matrix[i][left])
            left += 1
        return ans

时间复杂度为O(mn)，空间复杂度为O(1)

标记法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        ans = []
        i = j = di = 0
        for _ in range(m * n):
            ans.append(matrix[i][j])
            matrix[i][j] = None
            x, y = i + DIRS[di][0], j + DIRS[di][1]
            if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] is None:
                di = (di + 1) % 4

            i += DIRS[di][0]
            j += DIRS[di][1]

        return ans

用DIRS来记录方向，x,y判断是否越界，越界了就调整方向，总数一定是m*n

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度

必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像

示例 1：

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

1
2
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

经过书写可得交换下标的结论

[i][j]->[j][n-i-1]->[n-i-1][n-j-1]->[n-j-1][i]->[i][j]

原地旋转

可以知道只需要旋转n//2行

1
2
3
4
5
6
7
8
9
10
(0,0)  (0,1)  (0,2)  (0,3)  (0,4)
  .      A      .      .      .
(1,0)  (1,1)  (1,2)  (1,3)  (1,4)
  .      .      .      .      B
(2,0)  (2,1)  (2,2)  (2,3)  (2,4)
  .      .      .      .      .
(3,0)  (3,1)  (3,2)  (3,3)  (3,4)
  D      .      .      .      .
(4,0)  (4,1)  (4,2)  (4,3)  (4,4)
  .      .      .      C      .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(0, n // 2):
            for j in range(i, n - i - 1):
                (
                    matrix[i][j],
                    matrix[j][n - i - 1],
                    matrix[n - i - 1][n - j - 1],
                    matrix[n - j - 1][i],
                ) = (
                    matrix[n - j - 1][i],
                    matrix[i][j],
                    matrix[j][n - i - 1],
                    matrix[n - i - 1][n - j - 1],
                )

用翻转代替旋转

因为直接用旋转需要思考，还不够直观，如果直接用多次翻转来等效旋转会更简单

顺时针旋转90°相当于(i, j) → (j, n - 1 - i)

这相当于先转置(i, j) → (j, i)，而后对每行做一个翻转实现

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        # 对角线翻转
        for i in range(m):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # 水平翻转
        for row in matrix:
            row.reverse()

拓展：

如果要逆时针旋转90°呢？

旋转 90° 的标准坐标变换是(i, j) → (n - 1 - j, i)

那么相当于先转置后上下翻转

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)

        # 对角线翻转
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # 上下翻转（整体行顺序反转）
        matrix.reverse()

如果旋转180°相当于上下翻转再左右翻转

1
2
3
4
5
6
7
8
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        # 上下翻转
        matrix.reverse()
        
        # 每一行左右翻转
        for row in matrix:
            row.reverse()

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false

示例 1： 

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

因为满足严格递增，可以把矩阵拉平为数组，使用二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        left, right = -1, m * n
        while left + 1 < right:
            mid = left + (right - left) // 2
            r = mid // n
            c = mid % n
            x = matrix[r][c]
            if x == target:
                return True
            elif x < target:
                left = mid
            else:
                right = mid
        return False

搜索二维矩阵II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例 1：

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

1
2
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

Z 字形查找

利用单调性不断裁剪搜索空间，以右上角开始，如果值大了往左边移动，值小了向下移动，直到越界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1
        while i < m and j >= 0:
            cur = matrix[i][j]

            if cur < target:
                i += 1
            elif cur > target:
                j -= 1
            else:
                return True

        return False

时间复杂度O(m+n)，空间复杂度O(1)

二分法

这里由于上下行并没有完全的大小关系，每一行都是递增，所以只能逐行二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        for row in matrix:
            if row[0] > target:
                return False
            if row[-1] < target:
                continue
            if row[self.lower_bound(row, target)] == target:
                return True

    def lower_bound(self, nums: List[int], target: int):
        left, right = -1, len(nums)
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid
        return right

但是这样其实效率很低，时间复杂度是O(mlogn)

链表

在链表题中常用dummy，用 dummy 节点就不需要专门处理第一个节点，在最后返回 dummy.next 即可，这是链表题里的常规技巧

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

图示两个链表在节点 c1 开始相交**：**

题目数据 保证 整个链式结构中不存在环

注意，函数返回结果后，链表必须 保持其原始结构

自定义评测：

评测系统 的输入如下(你设计的程序 不适用 此输入)：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案

示例 1：

1
2
3
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 (注意，如果两个链表相交则不能为 0)

示例 2：

1
2
3
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值

双指针

用两个指针分别从A，B的头开始遍历，指向None时指向另一个的头

假设两个链表有相交，那么走了A再走B会到达同一位置，也就是交界点；如果没有相交，就同时指向None，也会相等从而跳出循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def getIntersectionNode(
        self, headA: ListNode, headB: ListNode
    ) -> Optional[ListNode]:

        pA, pB = headA, headB
        while pA is not pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA

        return pA

时间复杂度为O(m+n)，空间复杂度为O(1)

环形链表

给你一个链表的头节点 head ，判断链表中是否有环

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况

如果链表中存在环 ，则返回 true 。 否则，返回 false

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

快慢指针

如果有环形，两个指针虽然步数不一样，那么在多步以后应该指向同一位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

时间复杂度仍为O(n)，空间复杂度为O(1)

环形链表 II

给定一个链表的头节点head，返回链表开始入环的第一个节点，如果链表无环，则返回 null

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)

如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况

不允许修改 链表

示例 1：

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环

**进阶：**你是否可以使用 O(1) 空间解决此题？

方法一：哈希表

遍历记录head，找到第一个重复的位置即为入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        seen = set()
        while head:
            if head in seen:
                return head
            seen.add(head)
            head = head.next
       	return None

这种方法时间复杂度为O(n)，空间复杂度也为O(n)

方法二：快慢指针

  • a = 头到入口距离
  • b = 入口到相遇点距离
  • c = 环长

相遇时：慢指针走了 a + b，快指针走了 a + b + k·c

因为 fast 速度是 slow 的 2 倍：2(a + b) = a + b + k·c

整理得到：
$$
a + b = k·c\qquad a = k·c − b \qquad a = (c − b) + (k−1)c
$$
这意味着：从头走 a 步等价于从相遇点在环上走 c − b 步(再加若干整圈)

而 c − b 正好是从相遇点回到入口的距离

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None

        slow = head
        fast = head
        # 第一阶段：判断是否有环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                break
        else:
            # 没有环
            return None
        
       	# 第二阶段：寻找入口
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next

        return slow

这种做法时间复杂度O(n)，空间复杂度只有O(1)，只用到快慢指针

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

示例 1：

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

1
2
输入：head = []
输出：[]

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

迭代三指针法

核心思路：先存next再断开连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        cur = head

        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        return prev

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false

示例 1：

1
2
输入：head = [1,2,2,1]
输出：true

示例 2

1
2
输入：head = [1,2]
输出：false

**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

快慢指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True

        # 1. 找中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 反转后半部分
        prev = None
        cur = slow  # 注意，是从slow开始
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        # 3. 比较两部分
        p1, p2 = head, prev
        while p2:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next

        return True

如果要恢复链表就要多做一次反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True

        # 1. 找中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 反转后半部分
        second = self.reverse(slow)

        # 3. 比较两部分
        p1, p2 = head, second
        result = True
        while p2:
            if p1.val != p2.val:
                result = False
                break
            p1 = p1.next
            p2 = p2.next

        # 4. 再反转一次，恢复链表
        self.reverse(second)

        return result

    def reverse(self, head):
        prev = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

反转链表II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表

示例 1：

1
2
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

1
2
输入：head = [5], left = 1, right = 1
输出：[5]

局部链表反转 + 断开后重连

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        p0 = dummy
        for _ in range(left - 1):
            p0 = p0.next # 找到反转区间前一个节点

        prev = None
        cur = p0.next

        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
            
        # 把两边重新接上
        p0.next.next = cur # 反转后的尾连上right的后一个节点
        p0.next = prev # 接上反转后的头
        return dummy.next
1
2
3
dummy -> 1 -> 2 -> 3 -> 4 -> 5
         ↑
         p0

K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换

示例 1：

1
2
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

1
2
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

可以借鉴反转链表II的思路

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        n = 0
        cur = head
        while cur:
            n += 1 # 获取链表长度
            cur = cur.next

        dummy = ListNode(next=head)
        p0 = dummy # p0代表反转链表的前一个node
        prev = None
        cur = p0.next

        while n >= k: # 判断反转是否结束
            n -= k
            for _ in range(k): # k个反转
                nxt = cur.next
                cur.next = prev
                prev = cur
                cur = nxt
            nxt = p0.next # p0的next成为新的p0
            p0.next.next = cur # 将下一段的头接到反转头的next
            p0.next = prev # 将反转尾接到p0的next
            p0 = nxt # 更新p0
        return dummy.next

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头

示例 1：

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

和正常算术一个思想，最主要的是怎么把握进位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        carry = 0
        cur = dummy
        while l1 or l2 or carry:
            if l1: carry += l1.val  # 节点值和进位加在一起
            if l2: carry += l2.val  # 节点值和进位加在一起
            # 必须创建新的节点，val是int不是节点
            cur.next = ListNode(carry % 10)
            carry //= 10  # 新的进位
            cur = cur.next  # 下一个节点

            if l1: l1 = l1.next
            if l2: l2 = l2.next
        
        return dummy.next

时间复杂度O(max(m,n))，空间复杂度O(1)

两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表

你可以假设除了数字 0 之外，这两个数字都不会以零开头

示例1：

1
2
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

1
2
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

**进阶：**如果输入链表不能翻转该如何解决？

反转

反转链表 + 两数相加 = 两数相加 II

其实反转过来就是两数相加，注意结果也要反转

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
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    cur = head

    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        l1 = reverseList(l1)
        l2 = reverseList(l2)

        dummy = ListNode(0)
        carry = 0
        cur = dummy
        while l1 or l2 or carry:
            if l1: carry += l1.val
            if l2: carry += l2.val
            cur.next = ListNode(carry % 10)
            carry //= 10
            cur = cur.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return reverseList(dummy.next)

如果不用反转

利用栈的后进先出特性

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        st1, st2 = [], []

        while l1:
            st1.append(l1.val)
            l1 = l1.next
        while l2:
            st2.append(l2.val)
            l2 = l2.next

        carry = 0
        head = None
        while st1 or st2 or carry:
            if st1: carry += st1.pop()
            if st2: carry += st2.pop()
            # 尾插法
            node = ListNode(carry%10)
            node.next = head
            head = node

            carry //= 10

        return head

但是额外用栈，空间复杂度变为O(n)

删除链表中的节点

有一个单链表的 head，我们想删除它其中的一个节点 node

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点

删除节点并不是指从内存中删除它。这里的意思是：

  • 给定节点的值不应该存在于链表中
  • 链表中的节点数应该减少 1
  • node 前面的所有值顺序相同
  • node 后面的所有值顺序相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

由于prev不可得，那只能把后一个节点的内容复制到当前节点，然后删除后一个节点，这是一种伪删除手段

删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

示例 1：

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

**进阶：**你能尝试使用一趟扫描实现吗？

方法一：栈

用栈就能很快实现后进先出，从而快速定位并移除

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 removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        stack = list()
        dummy = ListNode(0, head)
        cur = dummy
        while cur:
            stack.append(cur)
            cur = cur.next
        
        # 每弹一次，相当于从后往前移动一个位置
        for _ in range(n):
            stack.pop()
        
        # 获取删除节点的前驱
        prev = stack[-1]
        prev.next = prev.next.next

        return dummy.next

时间复杂度O(n)，空间复杂度O(n)，但是只扫描链表一次

方法二：双指针

让快指针先走n步，然后移动慢指针

那么当快指针走到链表尾部时，慢指针到达倒数第 n 个位置的前驱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head) # 用哨兵是避免删除后为空报错
        fast = slow = dummy
        #  fast 先走 n 步
        for _ in range(n):
            fast = fast.next

        while fast.next: # 让slow停在要删除节点的前一个节点
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return dummy.next

时间复杂度O(n)，空间复杂度O(1)，且只扫描链表一次，快慢指针是最优雅的做法

删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次，返回已排序的链表

示例

1
2
输入：head = [1,1,2,3,3]
输出：[1,2,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return head
        cur = head
        while cur.next: # 注意这里是看cur.next
            if cur.next.val == cur.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

删除排序链表中的重复元素 II

给定一个已排序的链表的头 head，删除原始链表中所有重复数字的节点，只留下不同的数字，返回已排序的链表

示例 1：

1
2
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

需要对逻辑很清晰，需要在while里嵌套while

重复的元素在链表中出现的位置是连续的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        cur = dummy
        while cur.next and cur.next.next: # 至少还要有两个节点才能有的删
            val = cur.next.val # 记录值
            if cur.next.next.val == val: # 如果后点的值与前点重复
                while cur.next and cur.next.val == val: # 删除到cur.next不再为该值
                    cur.next = cur.next.next
            else:
                cur = cur.nex # 往后移动
        return dummy.next

两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即，只能进行节点交换)

示例 1：

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

1
2
输入：head = []
输出：[]

示例 3：

1
2
输入：head = [1]
输出：[1]

迭代

标准结构为：

1
prev → node1 → node2 → nxt

要用prev把前后连接起来，不然单反转会导致前后不连续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next and prev.next.next:
            node1 = prev.next
            node2 = node1.next
            # 交换
            node1.next = node2.next
            node2.next = node1
            prev.next = node2
            # 移动prev
            prev = node1

        return dummy.next

时间复杂度O(n)，空间复杂度O(1)

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝，深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值

新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y，返回复制链表的头节点

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引(范围从 0 到 n-1)；如果不指向任何节点，则为 null

你的代码 只 接受原链表的头节点 head 作为传入参数

示例 1：

1
2
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

1
2
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

1
2
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

方法一：回溯+哈希表

如果是普通链表，可以直接按照遍历的顺序创建链表节点

因为随机指针的存在，当拷贝节点时，当前节点的随机指针指向的节点可能还没创建，所以需要先确保所有新节点都存在

第一遍循环对每个原节点，创建一个新节点，并记录val映射

第二遍循环再恢复边结构

用哈希表可以很快实现一一匹配

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
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if head is None:
            return None

        node_map = {}
        cur = head
        # 第一遍：建立原节点 -> 新节点映射
        while cur:
            node_map[cur] = Node(cur.val)
            cur = cur.next

        # 第二遍：连接 next 和 random
        cur = head
        while cur:
            # 用get主要是处理None的情况，能正常返回None
            # node_map[cur.next]碰到None会报错
            node_map[cur].next = node_map.get(cur.next)
            node_map[cur].random = node_map.get(cur.random)
            cur = cur.next

        return node_map[head]

时间复杂度O(n)，空间复杂度O(n)(哈希表开销)

方法二：迭代+拆分

如果为了让空间复杂度降为O(1)，不用哈希表保存“原节点 → 新节点”的映射，而是把映射关系临时嵌入链表结构中

用拓扑结构暂存映射信息，这是一种“结构编码映射”的技巧

成立的前提是：

  • 链表结构允许临时修改
  • 节点之间的物理邻接关系可被利用

如果结构是只读的，这个方法就不可行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


class Solution:
    def copyRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if head is None:
            return None

        # 复制每个节点，把新节点直接插到原节点的后面
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next

        # 遍历交错链表中的原链表节点
        cur = head
        while cur:
            if cur.random:
                # 要复制的 random 是 cur.random 的下一个节点
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 把交错链表分离成两个链表
        cur = head
        new_head = head.next

        while cur:
            now_node = cur.next
            cur.next = now_node.next
            if now_node.next:
                now_node.next = now_node.next.next
            cur = cur.next

        return new_head

链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例

1
2
3
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

直接采用快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

快指针或者快指针的next为空说明到尾了，此时慢指针一定在中间位置

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

迭代

先构建一个虚拟头节点，然后逐个比大小，直到结尾，注意，一个走到底以后要直接拼接另一个剩下的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:

        # 创建一个虚拟头节点(哨兵节点)
        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

时间复杂度O(m+n)，while 循环的次数不会超过两个链表的长度之和，空间复杂度为O(1)

可发展到排序链表上用

排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表

示例 1：

1
2
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

1
2
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

1
2
输入：head = []
输出：[]

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

方法一：自顶向下归并排序

直接对一整条链表排序过于困难，有什么办法可以简化这个问题呢？

之前有合并过两个有序链表，那么是否可以把这个问题也简化成这样呢？

找到链表的中间结点head2的前一个节点，并断开head2与其前一个节点的连接，这样就把原链表均分成了两段更短的链表

递归调用 sortList，分别排序 head (前一半)和 head2

排序后，得到了两个有序链表，那么合并两个有序链表，得到排序后的链表，返回链表头节点

等于 链表的中间节点 + 合并两个有序链表

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 singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 快慢指针找中点
        slow = head
        fast = head
        while fast and fast.next:
            pre = slow # 记录slow的前一个位置，方便断开
            slow = slow.next
            fast = fast.next.next
        pre.next = None  # 断开 slow 的前一个节点和 slow 的连接
        return slow

    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        # 合并两个有序链表
        cur = dummy = ListNode(0)
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2.next
                list2 = list2.next
            cur = cur.next

        if list1:
            cur.next = list1
        if list2:
            cur.next = list2

        return dummy.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        head2 = self.middleNode(head)
        # 递归排序
        head = self.sortList(head)
        head2 = self.sortList(head2)

        return self.mergeTwoLists(head, head2)

sortList中并不排序，排序全部集中在合并函数中

每次递归都要用快慢指针找中点O(n)，所以时间复杂度是O(nlogn)

空间复杂度主要取决于递归调用的栈空间，空间复杂度为O(logn)

为了降低空间复杂度，把“自顶向下归并排序”改成“自底向上归并排序”

方法二：自底向上归并排序

从长度 = 1 的子链表开始，两两合并，长度翻倍，直到覆盖整个链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def getListLength(self, head: Optional[ListNode]) -> int:
        # 获取链表长度
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    def splitList(self, head: Optional[ListNode], size: int) -> Optional[ListNode]:
        cur = head
        for _ in range(size - 1):
            if cur is None:
                break
            cur = cur.next
        # 如果链表长度 <= size
        if cur is None or cur.next is None:
            return None  # 不做任何操作，返回空节点

        next_head = cur.next
        cur.next = None  # 断开 next_head 的前一个节点和 next_head 的连接
        # 返回切割后下一段的头
        return next_head

    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        # 合并链表得到有序链表
        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
        while cur.next:
            cur = cur.next
        # 返回合并后的头 和 尾
        return dummy.next, cur

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        length = self.getListLength(head)
        dummy = ListNode(0, head)
        step = 1
        while step < length:
            # 要记录合并后部分的尾
            new_list_tail = dummy
            cur = dummy.next
            while cur:
                # 从 cur 开始，分割出两段长为 step 的链表，头节点分别为 head1 和 head2
                head1 = cur
                head2 = self.splitList(head1, step)
                cur = self.splitList(head2, step)  # 下一次的头
                # 合并
                head, tail = self.mergeTwoLists(head1, head2)
                new_list_tail.next = head
                new_list_tail = tail
            step *= 2
        return dummy.next

这样就不需要递归，直接在链表上不断从小块到大块排序，空间复杂度降为O(1)

合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

1
2
输入：lists = []
输出：[]

示例 3：

1
2
输入：lists = [[]]
输出：[]

方法一：暴力排序

和排列两个有序链表一样，如果遍历每一个进行比较也可以实现

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cur = dummy

        while True:
            min_index = -1
            min_value = float("inf")

            # 在所有链表里找最小值
            for i in range(len(lists)):
                if lists[i] and lists[i].val < min_value:
                    min_value = lists[i].val
                    min_index = i

            # 如果没有找到，说明所有链表都空了
            if min_index == -1:
                break

            cur.next = lists[min_index]
            cur = cur.next

            # 对应链表前进一步
            lists[min_index] = lists[min_index].next

        return dummy.next

但这种做法的时间复杂度O(nk)，容易超时，k为链表个数

没有利用其它数据结果，空间复杂度O(1)

方法二：递归

从刚刚排序链表那题其实可以得到启发，可以对半来排序，自顶向下递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        m = len(lists)
        if m == 0:
            return None
        if m == 1:
            return lists[0] # 无需合并，直接返回

        left = self.mergeKLists(lists[: m // 2]) # 合并左半部分
        right = self.mergeKLists(lists[m // 2 :])  # 合并右半部分
        return self.mergeTwoLists(left, right) # 最后把左半和右半合并

    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        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

这种做法极大降低了时间复杂度O(nlogk)

但是利用递归需要消耗例外递归栈空间O(logk)

方法三：迭代

自底向上迭代

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        m = len(lists)
        if m == 0:
            return None
        step = 1
        while step < m:
            for i in range(0, m-step, step*2): # m-step隔开i+step避免越界
                lists[i] = self.mergeTwoLists(lists[i], lists[i+step])
            step = step*2
        return lists[0]

    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        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

思想和排序链表相同

LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

退出最久没使用的，相当于是退出离链表头最远的那个节点，怎么快速标记呢，可以用一个双端链表，让哨兵节点与尾连起来，形成链表环，也就是dummy.prev = back

另外要注意的是，不管get还是put都需要把查询到的key放到开头

所以直接创建一个push_front的工具函数，方便调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None


class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        # 初始化哨兵节点，自己连接自己，环结构
        self.dummy = Node()
        self.dummy.prev = self.dummy
        self.dummy.next = self.dummy
        self.key_to_node = {}

    def get_node(self, key: int):
        # 如果没有节点直接返回None
        if key not in self.key_to_node:
            return None
        # 如果存在，不管查询还是获取都需要放到头部
        # 可以相当于从后面把它删了重新建立一次
        node = self.key_to_node[key]
        self.remove(node)
        self.push_front(node)
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value
            return 
       	# 没有找到的话要创建
        self.key_to_node[key] = node = Node(key, value)
        self.push_front(node) # 放到开头
        # 如果超出存储
        if len(self.key_to_node) > self.capacity:
            back_node = self.dummy.prev
            # 删除key
            del self.key_to_node[back_node.key]
            self.remove(back_node)

    def remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def push_front(self, node: Node) -> None:
        # 插入补前后
        node.prev = self.dummy
        node.next = self.dummy.next
        # 给后节点补prev
        node.next.prev = node
        # 给dummy改next
        self.dummy.next = node
        


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

二叉树

遍历方式类：

DFS：Depth First Search(深度优先搜索)

BFS：Breadth-First Search(广度优先搜索)

树结构性质：

BST：Binary Search Tree(二叉搜索树) 满足：左子树 < 根 < 右子树

**递归：**由于子问题的规模比原问题小，不断递下去，总会有个尽头，即递归的边界条件(base case)

@二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历

示例 1：

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

什么是二叉树遍历

遍历方式 顺序
前序 Pre(Preorder) 根 → 左 → 右
中序 In(Inorder) 左 → 根 → 右
后序 Post(Postorder) 左 → 右 → 根 
1
2
3
4
5
6
7
8
9
10
11
                50
           /           \
         30             70
       /    \         /    \
     20      40     60      80
    /  \    /  \   /  \    /  \
   10  25  35  45 55  65  75  90
  /
 5

5 10 20 25 30 35 40 45 50 55 60 65 70 75 80 90

方法一：递归

按照这个遍历模式，可以利用递归走到子节点再往回慢慢加结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def dfs(node):
            if node is None:
                return

            dfs(node.left)
            result.append(node.val)
            dfs(node.right)

        dfs(root)
        return result

递归天然等价于“隐式栈”，后进先出(LIFO)

时间复杂度和空间复杂度均为O(n)

方法二：迭代

也可以把递归这个隐式栈显式写出来

  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
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            # 左子树处理完，回退
            cur = stack.pop()
            ans.append(cur.val)

            # 转向右子树
            cur = cur.right

        return ans

同样时间复杂度和空间复杂度均为O(n)

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 严格小于 当前节点的数
  • 节点的右子树只包含 严格大于 当前节点的数
  • 所有左子树和右子树自身必须也是二叉搜索树

示例 1：

1
2
输入：root = [2,1,3]
输出：true

示例 2：

1
2
3
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

这题的重点是不能只递归比较当前node的val和left\right的val

需要注意的是全局约束

  • 左子树所有值 < 当前节点

  • 右子树所有值 > 当前节点

1
2
3
4
5
  5
 / \
3   7
   /
  4   ← 这里违反了整体区间约束

前序遍历递归

空树判断为True，按照根-左-右的顺序去判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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 isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:
        if root is None:
            return True
        x = root.val
        return (
            left < x < right
            and self.isValidBST(root.left, left, x)   # 这里要跟着left
            and self.isValidBST(root.right, x, right) # 这里要跟着right
        )

中序遍历递归

二叉搜索树，中序遍历是自然的做法

中序遍历时，可以把二叉搜索树看成一个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    pre = -inf # 注意记录前一个值

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        # 判断左侧是否符合
        if not self.isValidBST(root.left):
            return False
        # 判断当前节点值是否大于前一个节点值
        if root.val <= self.pre:
            return False
        self.pre = root.val
        # 递归检查右子树
        return self.isValidBST(root.right)

后续遍历递归

利用特殊值来传递信息

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 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            if node is None:
                return inf, -inf  # 空节点返回特殊值

            l_min, l_max = dfs(node.left)
            r_min, r_max = dfs(node.right)

            x = node.val

            if x <= l_max or x >= r_min:
                return -inf, inf  # 返回必报错区间

            return min(l_min, x), max(r_max, x)

        return dfs(root)[1] != inf  # 如果区间为异常区间返回False

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

1
2
3
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案

示例 2：

1
2
3
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

对于任意节点：

  • 左子树所有值 < 当前节点值
  • 右子树所有值 > 当前节点值

如果对二叉搜索树(BST)做中序遍历，得到的一定是升序序列

题目其实在问：如何从一个有序数组构造一棵“尽量矮”的 BST？

所以核心就在于找中点，然后递归构造左右子树，选中点是为了保证左右规模接近，从而高度平衡(其实思想和二分也有点像)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        n = len(nums)
        mid = n // 2
        left = self.sortedArrayToBST(nums[:mid])
        right = self.sortedArrayToBST(nums[mid + 1 :])
        return TreeNode(nums[mid], left, right)

@二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

1
2
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

1
2
输入：root = [1,null,2]
输出：2

递归，自底向上

  • 空节点深度 = 0

  • 当前节点深度 = max(左子树深度, 右子树深度) + 1

左子树和右子树的最大深度又可以以同样的方式进行计算，可以先递归计算出其左子树和右子树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        l_depth = self.maxDepth(root.left)
        r_depth = self.maxDepth(root.right)

        return max(l_depth, r_depth) + 1

时间复杂度O(n)，n 为二叉树节点的数目

空间复杂度O(h)，h 是树高(递归栈深度)

平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树(是指该树所有节点的左右子树的高度相差不超过 1)

示例 1：

1
2
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

1
2
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

思路和获取二叉树的最大深度一样，但不一样的是多了一个比较，之前返回的都是数值

为了返回bool类型，利用-1传递False信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node):
            if node is None:
                return 0
            left = get_height(node.left)
            right = get_height(node.right)
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return max(left, right) + 1

        return get_height(root) != -1

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

1
2
3
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度

示例 2：

1
2
输入：root = [1,2]
输出：1

直径是什么，相当于某个节点的左边最大深度+右边最大深度，这个节点不一定是root

深度是节点数，直径是边数，所以不用另外+1

所以可以借助二叉树的最大深度来遍历找到最大直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0

        def depth(node):
            if node is None:
                return 0
            left = depth(node.left)
            right = depth(node.right)
            self.diameter = max(self.diameter, left + right)  # 这里记录直径
            return max(left, right) + 1  # 正常返回最大深度

        depth(root)
        return self.diameter

二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
1
2
3
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

分析下来其实可以发现，找路径和相当于是选走左边还是走右边或者是不走，所以dfs遍历的是最大累积和

结果记录的是当前 最大left + 最大right + node.val

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = -inf

        def dfs(node):
            if node is None:
                return 0
            l_val = dfs(node.left)
            r_val = dfs(node.right)
            nonlocal ans
            ans = max(ans, l_val + r_val + node.val)
            return max(max(l_val, r_val) + node.val, 0)

        dfs(root)
        return ans

二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

示例 1：

1
2
输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]

示例 2：

1
2
输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]

递归DFS

递归函数带深度参数 depth，如果 depth == len(ans)，说明这是这一层第一次来，就把当前节点值加入 ans

递归顺序：先右后左

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []

        def dfs(node, depth):
            if node is None:
                return
            if depth == len(ans):
                ans.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)

        dfs(root, 0)
        return ans

时间复杂度O(n)，空间复杂度为O(n)(深度)

BFS

借鉴二叉树的层序遍历做法，但是只取最右侧输出

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

@相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的

示例 1：

1
2
输入：p = [1,2,3], q = [1,2,3]
输出：true

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q  # 只有均为None时True
        return (
            p.val == q.val
            and self.isSameTree(p.left, q.left)
            and self.isSameTree(p.right, q.right)
        )

对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称

示例 1：

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

1
2
输入：root = [1,2,2,null,3,null,3]
输出：false

**进阶：**你可以运用递归和迭代两种方法解决这个问题吗？

方法一：递归

可以借鉴相同的树定义一个新函数，来判断左右两边是否对称相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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 isSymmetric(self, root: Optional[TreeNode]) -> 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)

直接比较根节点的左右两端

时间复杂度为O(n)，空间复杂度O(h)

方法二：迭代

用一个双端队列，不断比较，直到全部比完，从上到下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        dq = deque([(root.left, root.right)])

        while dq:
            t1, t2 = dq.popleft()
            if not t1 and not t2:
                continue
            if not t1 or not t2 or t1.val != t2.val:
                return False

            dq.append((t1.left, t2.right))
            dq.append((t1.right, t2.left))

        return True

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

示例 1

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

1
2
输入：root = []
输出：[]

递归

  • 递归翻转左子树
  • 递归翻转右子树
  • 在当前节点交换左右
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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 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 = right
        root.right = left
        return root

时间复杂度为O(n)，空间复杂度O(h)

也可以

  • 在当前节点交换左右
  • 递归翻转左子树
  • 递归翻转右子树
1
2
3
4
5
6
7
8
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

@二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 (即逐层地，从左到右访问所有节点)

示例 1：

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

双数组做法

一个数组存储下一层的节点，一个数组存储当前层的值，层层往下扫描

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
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        cur = [root]
        while cur:
            nxt = []
            vals = []
            for node in cur:
                vals.append(node.val)
                if node.left:
                    nxt.append(node.left)
                if node.right:
                    nxt.append(node.right)
            cur = nxt
            ans.append(vals)

        return ans

那能不能把cur和nxt数组合并到一起呢？这里再利用到队列

队列做法

“先进先出”的访问顺序

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 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans = []
        dq = deque([root])
        while dq:
            vals = []
            for _ in range(len(dq)):
                node = dq.popleft()
                vals.append(node.val)
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)
            ans.append(vals)
        return ans

找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点

示例:

1
2
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

可以采用层序遍历，然后输出最左的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        dq = deque([root])
        ans = root.val
        while dq:
            ans = dq[0].val
            for _ in range(len(dq)):
                node = dq.popleft()
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)
        return ans

或者从右往左读，这样最后一个读的节点就是左下角的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        dq = deque([root])
        while dq:
            node = dq.popleft()
            if node.right:
                dq.append(node.right)
            if node.left:
                dq.append(node.left)
        return node.val

其实本质还是层序的思路

二叉搜索树中第 K 小的元素

给定一个二叉搜索树BST的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素(k 从 1 开始计数)

示例 1：

1
2
输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

1
2
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

**进阶：**如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值，你将如何优化算法？

中序遍历

如果利用BST特性，左<根<右

那么就可以先走到最左边，然后回头慢慢找

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 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        node = root
        while True:
            # 走到最左底部，记录向左走时的node
            while node:
                stack.append(node)
                node = node.left
			
            node = stack.pop()
            k -= 1

            if k == 0:
                return node.val
			  # 注意转到右边，而不是一直从左边往回退 
            node = node.right

时间复杂度O(h+k)，空间复杂度O(h)

同理如果适合要做第k大也很简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 kthLargest(self, root: Optional[TreeNode], k: int) -> int:
        st = []
        node = root
        while True:
            while node:
                st.append(node)
                node = node.right

            node = st.pop()
            k -= 1
            if k == 0:
                return node.val
            node = node.left

如果树经常被修改，同时要频繁查询第 k 小，那么单纯中序遍历是低效的

要做的是让“第 k 小”变成O(log n)

核心思想：给每个节点增加一个统计量

在每个节点维护一个字段：size = 以该节点为根的子树节点总数

设当前节点为 node：

  • 左子树节点数 = left_size
  • 当前节点在整棵子树中的排名 = left_size + 1

于是：

  • 若 k ≤ left_size → 去左子树
  • 若 k = left_size + 1 → 当前节点
  • 若 k > left_size + 1 → 去右子树找第 k - left_size - 1 小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 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 MyBst:
    def __init__(self, root):
        self.root = root
        self._build_size(root)

    def _build_size(self, node):
        if node is None:
            return 0
        # 递归计算每个节点的子树大小
        node.size = 1 + self._build_size(node.left) + self._build_size(node.right)
        return node.size

    def kth_smallest(self, k: int) -> int:
        node = self.root
        while node:
            left_size = node.left.size if node.left else 0
            if k <= left_size:
                node = node.left
            elif k == left_size + 1:
                return node.val
            else:
                k -= left_size + 1
                node = node.right

    def kth_largest(self, k: int) -> int:
        node = self.root
        while node:
            right_size = node.right.size if node.right else 0
            if k <= right_size:
                node = node.right
            elif k == right_size + 1:
                return node.val
            else:
                k -= right_size + 1
                node = node.left

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        return MyBst(root).kth_smallest(k)

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同

示例 1：

1
2
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

**进阶：**你可以使用原地算法(O(1) 额外空间)展开这棵树吗？

分治DFS

递归展开左、右子树，记录左右子树的尾节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root is None:
            return None
        
        left_tail = self.flatten(root.left)
        right_tail = self.flatten(root.right)
        if left_tail:
            left_tail.right = root.right # 左子树末端接上原右子树
            root.right = root.left       # 根节点的右指针指向左子树
            root.left = None             # 左子树置空
        return right_tail or left_tail or root # 返回当前子树的末端节点

返回逻辑：

  1. 右子树存在 → 返回右子树末端
  2. 右子树不存在、左子树存在 → 返回左子树末端
  3. 左右子树都不存在（叶子节点） → 返回当前节点

时间复杂度O(n)，空间复杂度O(n)

@从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点

示例 1:

1
2
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

这两个序列的本质区别是：

  • 前序第一个元素一定是整棵树的根
  • 中序可以告诉你这个根的左右子树各有哪些节点

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        left_size = inorder.index(preorder[0]) # 前序的第一个数是根，在中序里找根的位置
        left = self.buildTree(preorder[1 : 1 + left_size], inorder[:left_size]) # 构建左树
        right = self.buildTree(preorder[1 + left_size :], inorder[1 + left_size :])
        return TreeNode(preorder[0], left, right)

时间复杂度O(n^2)，空间复杂度O(n^2)

同样思路可以解决其它组合

从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树

1
2
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        left_size = inorder.index(postorder[-1])
        left = self.buildTree(inorder[:left_size], postorder[:left_size])
        right = self.buildTree(inorder[left_size+1:],postorder[left_size:-1])
        return TreeNode(postorder[-1], left, right)

根据前序和后序遍历构造二叉树

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树

1
2
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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 constructFromPrePost(
        self, preorder: List[int], postorder: List[int]
    ) -> Optional[TreeNode]:
        if not preorder:
            return None
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        left_size = postorder.index(preorder[1]) + 1
        left = self.constructFromPrePost(
            preorder[1 : left_size + 1], postorder[:left_size]
        )
        right = self.constructFromPrePost(
            preorder[left_size + 1 :], postorder[left_size:-1]
        )
        return TreeNode(preorder[0], left, right)

代码其实有一点不严谨地方在于假设一定有左子树，如果没有左子树就会出错

路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的(只能从父节点到子节点)

示例 1：

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示

前缀和

类似之前和为 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
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefix = defaultdict(int)
        prefix[0] = 1
        ans = 0

        def dfs(node, s):
            if node is None:
                return
            nonlocal ans
            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

时间复杂度和空间复杂度均为O(n)

为什么要回溯减掉 prefix？

因为 prefix 表示的是：当前递归路径上的前缀和

当从左子树回到父节点时，这条路径已经“物理消失”，如果不剪掉会污染子树

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)”

示例 1：

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3

在树上做后序遍历：左右子树各自“向上汇报”自己有没有找到 p/q；第一次左右都汇报“找到了”的节点，就是最近公共祖先

后序递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        if root in (None, p, q):
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:  # 左右都找到
            return root     # 当前节点是最近公共祖先
        
        # 如果只有左子树找到，就返回左子树的返回值
        # 如果只有右子树找到，就返回右子树的返回值
        # 如果左右子树都没有找到，就返回 None
        return left or right

返回值在做“自底向上的信息汇报”，只是向父节点传递一个信号，这边找到了 p(或者 q)

当某个节点第一次同时接收到左右非空的返回值时，说明它是最底层的那个“分叉点”

图论

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
输出：3

选择DFS：Depth First Search(深度优先搜索)

对于岛屿可以在遇到’1’时走完，然后把这个岛设置为’2’方便检查

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 numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(i: int, j: int) -> None:
            # 出界，或者不是 '1'，就不再往下递归
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
                return
            grid[i][j] = "2"  # 插旗，避免来回横跳无限递归
            dfs(i, j - 1)
            dfs(i, j + 1)
            dfs(i - 1, j)
            dfs(i + 1, j)

        ans = 0
        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == "1": # 找到了一个新的岛
                    dfs(i, j)
                    ans += 1

        return ans

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1

示例 1：

1
2
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

1
2
3
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

多源 BFS

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 orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        fresh = 0
        q = []
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    fresh += 1  # 统计新鲜橘子个数
                elif x == 2:
                    q.append((i, j))  # 一开始就腐烂的橘子

        ans = 0
        while q and fresh:
            ans += 1  # 经过一分钟
            tmp = q
            q = []  # 每轮重新记录坏橘子位置，因为之前的已经被包起来了
            for x, y in tmp:  # 已经腐烂的橘子
                for i, j in (x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1):
                    if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:
                        fresh -= 1
                        grid[i][j] = 2  # 变成腐烂橘子
                        q.append((i, j))

        return -1 if fresh else ans

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

其实任务就变成了找环，如果有环结构肯定报错

给每门课加状态

  • 0 = 未访问

  • 1 = 访问中（递归栈中）

  • 2 = 已完成（访问过且无环）

如果处于遍历过的状态，再次遍历到肯定就有环，直接返回True，否则就是能正常遍历到结束

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 canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)

        color = [0] * numCourses
        # 返回 True 表示找到了环
        def dfs(x: int) -> bool:
            color[x] = 1 # x 正在访问中
            for nxt in graph[x]:
                # 情况一：colors == 1，表示发生循环依赖，找到了环
                # 情况二：colors == 0，没有访问过，继续递归获取信息
                # 情况三：colors == 2，重复访问，和之前一样无法找到环，跳过
                if color[nxt] == 1 or (color[nxt] == 0 and dfs(nxt)):
                    return True
            color[x] = 2
            return False

        for i in range(numCourses):
            if color[i] == 0 and dfs(i):
                return False
        return True

实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

推广到 26 种字母，其实就是一棵 26 叉树

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 Node:
    __slots__ = "son", "end"

    def __init__(self):
        self.son = {}
        self.end = False


class Trie:

    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.son:
                cur.son[c] = Node()
            cur = cur.son[c]
        cur.end = True

    def find(self, word: str) -> int:
        cur = self.root
        for c in word:
            if c not in cur.son:
                return 0
            cur = cur.son[c]
        return 2 if cur.end else 1

    def search(self, word: str) -> bool:
        return self.find(word) == 2

    def startsWith(self, prefix: str) -> bool:
        return self.find(prefix) != 0


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

回溯

子问题和原问题是相似的，这种从原问题到子问题的过程适合用递归解决

回溯有一个增量构造答案的过程，这个过程通常用递归实现

主要有几类问题：

  • 子集型(Subset / 组合选择问题)：每个元素只有 选 / 不选 两种状态
  • 组合型：从一组元素里选若干个，顺序不重要，需要防止回头
  • 排序类：顺序是重要的，一般需要在输入带上 used 数组

在回溯问题中，通常会维护两类变量：

  • path：当前正在构造的路径
  • ans：保存所有已经完成的结果

回溯的过程中，path 会不断被修改(添加 / 删除元素)，如果直接把 path 放入 ans，后续的修改会影响已经保存的结果，所以需要.copy()

@子集

给你一个整数数组 nums ，数组中的元素 互不相同，返回该数组所有可能的子集(幂集)

解集 不能 包含重复的子集，你可以按 任意顺序 返回解集

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

从输入角度考虑

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
            # 不选
            dfs(i + 1)
            # 选
            path.append(nums[i])
            dfs(i + 1)
            path.pop()  # 恢复状态，否则污染上一层
        dfs(0)
        return ans
1
2
3
4
5
        []
    /        \
 不选1        选1
  /  \       /  \
[]  [2]    [1] [1,2]

最重要的就是要记得回溯状态，把状态恢复到进入递归前的样子

从输出角度考虑

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())
            if i == n:
                return
            for j in range(i, n):
                path.append(nums[j])
                dfs(j + 1)
                path.pop()
        dfs(0)
        return ans
1
2
3
4
5
6
7
8
[]
├── 1
│   ├── 2
│   │   └── 3
│   └── 3
├── 2
│   └── 3
└── 3

在一棵树里不断扩展 path，然后回溯

分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]

子集型，但这里必须等到 字符串全部处理完 才能加入答案

枚举子串结束位置

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

        def dfs(i):
            if i == n: # s 分割完毕
                ans.append(path.copy())
                return

            for j in range(i, n): # 枚举子串的结束位置
                t = s[i : j + 1]  # 分割出子串 t
                if t == t[::-1]:  # 如果回文
                    path.append(t)
                    # 考虑剩余的 s[j+1:] 怎么分割
                    dfs(j + 1)
                    path.pop()

        dfs(0)
        return ans

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合

示例 1：

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

位置长度是固定的，所以用选或不选很好做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        path = []
        # 目前填了 left 个左括号，right 个右括号
        def dfs(left, right):
            if left == n and right == n: # 填完 2n 个括号
                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

@组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合

你可以按 任何顺序 返回答案

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

设 path 长为 m，那么还需要选 d=k-m 个数

设当前需要从[1，i]这i个数中选数，为了选出k个数必须满足$i\ge d$，不需要继续递归，这是一种剪枝技巧

组合枚举

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

        def dfs(i):
            d = k - len(path)
            if len(path) == k:
                ans.append(path.copy())
                return
            # i必须≥d，不然选不到k个数
            for j in range(i, d-1, -1):
                path.append(j)
                dfs(j - 1)
                path.pop()
        dfs(n)
        return ans

更快，多叉树

子集枚举

选 / 不选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 i < k - len(path):
                return
            dfs(i - 1)

            path.append(i)
            dfs(i - 1)
            path.pop()

        dfs(n)
        return ans

会稍微慢一点，二叉树

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

最重要的是每个数字可以重复使用无限次

为了避免重复组合，需要递归从当前下标及之后开始选

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

        def dfs(start, remain):
            if remain == 0:
                ans.append(path.copy())
                return
            if remain < 0:
                return
            for i in range(start, len(candidates)):
                num = candidates[i]
                path.append(num)
                dfs(i, remain - num)
                path.pop()

        dfs(0, target)
        return ans

组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回

示例 1:

1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

组合枚举

剩余和写法，输入时附带离和为n的差值

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

        def dfs(i, remain):
            d = k - len(path)
            # 再加最大的d个数也满足不了remain
            # 当d=0时，刚好右侧就是remain>0，那么只有remain = 0 才能往下
            if remain < 0 or remain > d * (2 * i - d + 1) // 2:
                return
            if len(path) == k: # 所以不需要额外判断
                ans.append(path.copy())
                return
            for j in range(i, d - 1, -1):
                path.append(j)
                dfs(j - 1, remain - j)
                path.pop()

        dfs(9, n)
        return ans

@全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

最主要的就是剔除已经用过的,利用set来实现删减

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

        def dfs(i, s):
            if i == n:
                ans.append(path.copy())
                return
            for x in s:
                path.append(x)
                dfs(i + 1, s - {x})  # 减去要带{},不然不是set减
                path.pop()

        dfs(0, set(nums))  # 转为set好进行删减操作
        return ans

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

1
2
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

示例 2：

1
2
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false

**进阶：**你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

把棋盘上每个格子都当成起点试一遍

从 (i,j) 这个格子开始，能不能匹配 word[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 exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        def dfs(i, j, k):
            if board[i][j] != word[k]: # 匹配失败
                return False
            if k == len(word) - 1: # 匹配成功！
                return True
            board[i][j] = "#" # 标记访问过
            for x, y in [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]:
                if 0 <= x < m and 0 <= y < n and dfs(x, y, k + 1):
                    return True
            board[i][j] = word[k]  # 还原标记
            return False  # 没搜到

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

        return False

还可以优化

如果 word 的某个字母的出现次数，比 board 中的这个字母的出现次数还要多，可以直接返回 false

如果 word 的尾字母更少，可以把word调转一下，这样可以减少递归次数

1
2
3
4
5
6
7
8
cnt = Counter()
for row in board:
    for c in row:
        cnt[c] +=1
if not cnt>= Counter(word): # 优化一
    return False
if cnt[word[-1]] < cnt[word[0]]: # 优化二
    word = word[::-1]

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)，注意 1 不对应任何字母

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2
3
4
5
            ""
     /      |       \
    a       b        c
  / | \   / | \    / | \
ad ae af bd be bf cd ce cf

DFS深度优先，沿着一条路径走到底再回退继续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        ans = []
        path = []

        def dfs(i):
            if i == n:
                ans.append("".join(path)) # 输出要字符串
                return
            for x in MAPPING[int(digits[i])]:
                path.append(x) # 保存的是list
                dfs(i + 1)
                path.pop()

        dfs(0)
        return ans

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法

不同行不同列，那么每行至少且至多一个皇后，每列也是

另外还有斜线要求，用r表示行号，c表示列号

因为是从上到下枚举，那么右上方向为r+c=定值，左上方向为r-c=定值

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 solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        col = [0] * n # 假设先全放0列

        def valid(r, c): # 判断当前位置是否有效
            for R in range(r): # 根据之前的Q位置
                C = col[R]
                if r + c == R + C or r - c == R - C:
                    return False
            # 如果都判断通过返回True
            return True

        def dfs(r, s):
            if r == n:
                ans.append(["." * c + "Q" + "." * (n - 1 - c) for c in col])
                return
            for c in s:
                if valid(r, c):
                    col[r] = c
                    dfs(r + 1, s - {c})

        dfs(0, set(range(n)))
        return ans

因为每次valid判断都要遍历，所以时间复杂度为O(n*n!)，空间复杂度为O(n)

二分查找

开区间写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def lower_bound(nums: List[int], target: int):
    left, right = -1, len(nums) # 开区间 (left, right)
    while left+1 < right: # 区间不为空
        mid = left + (right-left)//2
        # 循环不变量：
        # nums[left] < target
        # nums[right] >= target
        if nums[mid] >= target:
            right = mid  # 范围缩小到 (left, mid)
        else:
            left = mid   # 范围缩小到 (mid, right)
    # 循环结束后 left+1 = right
    # 此时 nums[left] < target 而 nums[right] >= target
    # 所以 right 就是第一个 >= target 的元素下标
    return right
目标 含义 修改条件
lower_bound 第一个 ≥ target nums[mid] >= target
upper_bound 第一个 > target nums[mid] > target
last ≤ target 最后一个 ≤ target nums[mid] > target（返回 left）
last < target 最后一个 < target nums[mid] >= target（返回 left）

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

1
2
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

1
2
输入: nums = [1,3,5,6], target = 7
输出: 4

涉及到O(log n)大概率就是二分题

因为是升序数组，所以就是很标准的二分写法

1
2
3
4
5
6
7
8
9
10
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = -1, len(nums)
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid
        return right

本质就是找

1
min i such that nums[i] >= target

所以就是lower_bound写法，其它情况都可以从这个情况稍加改变获得

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false

示例 1：

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

注意这个矩阵比较特别，下一行的最小数一定比上一行的最大数大，所以可以拼接起来成一行来看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        left, right = -1, m * n
        while left + 1 < right:
            mid = left + (right - left) // 2
            r = mid // n
            c = mid % n
            x = matrix[r][c]
            if x == target:
                return True
            elif x < target:
                left = mid
            else:
                right = mid
        return False

升级版看搜索二维矩阵 II(下一行的最小数不一定大于上一行的最大数)

在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

1
2
输入：nums = [], target = 0
输出：[-1,-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def lower_bound(nums: List[int], target: int) -> int:
    left, right = -1, len(nums)
    while left + 1 < right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid
        else:
            left = mid

    return right

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        end = lower_bound(nums, target + 1) - 1
        return [start, end]

第一次二分找第一个等于target的位置，第二次二分找第一个>target的位置，往前一位就是target的最后一个位置，[start, end]就是target的区间

寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

示例 1：

1
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

1
2
3
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

1
2
3
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

二分查找实际上是在查找第一个满足 nums[i] < nums[-1] 的位置

两段划分，均为升序序列，所以以最右侧元素作为标准进行对比

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = -1
        right = len(nums) - 1 # 主要是避免越界，采用-1
        while left + 1 < right:
            mid = left + (right - left) // 2

            if nums[mid] < nums[-1]:
                right = mid
            else:
                left = mid
        return nums[right]

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同

在传递给函数之前，nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)

例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2]

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

示例 1：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

1
2
输入：nums = [1], target = 0
输出：-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
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i = self.findMin(nums)
        if target > nums[-1]:
            return self.lower_bound(nums, -1, i, target)
        return self.lower_bound(nums, i - 1, len(nums), target)
	# 二分查找
    def lower_bound(self, nums: List[int], left: int, right: int, target: int) -> int:
        while left + 1 < right:  # 开区间不为空
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid
            else:
                left = mid

        return right if nums[right] == target else -1
	# 寻找旋转数组中的最小值
    def findMin(self, nums: List[int]) -> int:
        left = -1
        right = len(nums) - 1  # 主要是避免越界，采用-1
        while left + 1 < right:
            mid = left + (right - left) // 2

            if nums[mid] < nums[-1]:
                right = mid
            else:
                left = mid
        return right

如果要一次二分

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 search(self, nums: List[int], target: int) -> int:
        left, right = -1, len(nums)
        while left + 1 < right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    right = mid
                else:
                    left = mid
            else:
                if nums[mid] < target <= nums[-1]:
                    left = mid
                else:
                    right = mid

        if -1 < right < len(nums) and nums[right] == target:
            return right
        return -1

贪心算法

维度 DP 贪心
决策 多分支 单选择
是否回溯 是（隐式） 否
时间复杂度 通常较高 通常较低
正确性来源 完整枚举 数学证明
实现难度 高 低

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = inf
        max_profit = 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)

        return max_profit

维护两个数，最低成本以及最高收益

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

注意，每次是最多跳nums[i]

不断维护“当前能到达的最远位置”，只要没有出现断点，就一定能到终点

1
2
3
4
5
6
7
8
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0
        for i in range(len(nums)):
            if i > max_reach: # 表示当前位置是否可达
                return False
            max_reach = max(max_reach, i + nums[i])
        return True

跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处，返回到达 n - 1 的最小跳跃次数

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

dp写法：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        ans = [inf] * n
        ans[0] = 0
        for i in range(n - 1):
            step = nums[i]
            for j in range(1, min(step, n - 1 - i) + 1):
                ans[i + j] = min(ans[i + j], ans[i] + 1)

        return ans[n - 1]

时间复杂度O(n^2)，太大

贪心写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = 0
        cur_right = 0
        next_right = 0
        # 最后一个位置不用作为起跳点，所以到 n-2 即可
        for i in range(len(nums)-1):
            # 遍历的过程中，记录下一座桥的最远点
            next_right = max(next_right, i+nums[i])
            if i == cur_right: # 必须建桥
                cur_right = next_right # 建桥后到达的最远
                ans +=1
        return ans

不断维护“当前能到达的最远位置”，并且记录跳远次数，如果已经到达当前跳跃的最远就必须+1

灌溉花园的最少水龙头数目

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n]

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i - ranges[i], i + ranges[i]]

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 5, ranges = [3,4,1,1,0,0]
输出：1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2：

1
2
3
输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

主要是如何把问题变成跳跃游戏II

把区间变成跳跃能力

第i个水龙头能够覆盖[i-r,i+r]区间

那么转为在i-r这个位置最远能跳到i+r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        right_most = [0] * (n + 1)
        for i, r in enumerate(ranges):
            left = max(i - r, 0)
            right_most[left] = max(right_most[left], i + r) # 计算left位置能到达的最远端

        ans = 0
        cur_right = 0
        next_right = 0
        for i in range(n): # 如果走到 n-1 时没有返回 -1，那么必然可以到达 n
            next_right = max(next_right, right_most[i])
            if i == cur_right:
                if i == next_right: # 如果覆盖面积扩不大了，说明无法覆盖
                    return -1 
                cur_right = next_right
                ans += 1
        return ans

后半段和跳跃游戏II相同

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表

示例 1：

1
2
3
4
5
6
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

1
2
输入：s = "eccbbbbdec"
输出：[10]

首先要知道每个字母最右到哪，然后就变成了合并区间问题

当前区间必须扩展到“所有已出现字符的最远位置”

当前扫描位置 i 已经覆盖了区间内所有字符的最后一次出现时截断

1
2
3
4
5
6
7
8
9
10
11
12
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 end == i:
                ans.append(end - start + 1)  # 区间长度加入答案
                start = i + 1

        return ans

动态规划(dp)

0-1背包问题

有 $n$ 种物品，第 $i$ 种物品的体积为 $w[i]$，价值为 $v[i]$，每种物品至多选一个，求体积不超过 $capacity$ 时的最大价值和

回溯三问：

枚举第 $i$ 个物品选或不选：

  • 不选：剩余容量不变
  • 选：剩余容量减少 $w[i]$

子问题：在剩余容量为 $c$ 时，从前 $i$ 个物品中得到的最大价值和

下一个子问题（分类讨论）：

  • 不选：在剩余容量为 $c$ 时，从前 $i-1$ 个物品中得到的最大价值和
  • 选： 在剩余容量为 $c - w[i]$ 时，从前 $i-1$ 个物品中得到的最大价值和

dfs(i, c) = max(dfs(i-1, c), dfs(i-1, c - w[i]) + v[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from functools import cache
def zero_one_knapsack(capacity: int, w: list[int], v: list[int]) -> int:
    n = len(w)

    @cache
    def dfs(i: int, c: int) -> int:
        if i < 0:
            return 0

        if c < w[i]:
            return dfs(i - 1, c)

        return max(
            dfs(i - 1, c),
            dfs(i - 1, c - w[i]) + v[i]
        )

    return dfs(n - 1, capacity)

dfs(i,c) = min(dfs(i-1,c), dfs(i-1, c - w[i]) + v[i])

完全背包问题

有 $n$ 种物品，第 $i$ 种物品的体积为 $w[i]$，价值为 $v[i]$，每种物品可以无限次重复选，求体积不超过 $capacity$ 时的最大价值和

回溯三问：

枚举第 $i$ 种物品选一个或不选：

  • 不选：剩余容量不变
  • 选一个：剩余容量减少 $w[i]$

子问题：在剩余容量为 $c$ 时，从前 $i$ 种物品中得到的最大价值和

下一个子问题（分类讨论）：

  • 不选：在剩余容量为 $c$ 时，从前 $i-1$ 种物品中得到的最大价值和
  • 选一个：在剩余容量为 $c - w[i]$ 时，从前 $i$ 种物品中得到的最大价值和

dfs(i,c) = max(dfs(i-1,c), dfs(i, c - w[i]) + v[i])

常见变形：

  • 至多装capacity，求方案数/最大价值和
  • 恰好装capacity，求方案数/最大/最小价值和
  • 至少装capacity，求方案数/最小价值和

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额

示例 1：

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

这道题为0/1背包问题

自顶向下算：记忆化搜索

当前：第i个房间选/不选？

子问题：从前i个房间中得到的最大金额和

下一个子问题：

  • 选i：从前i-2个房间中得到的最大金额和
  • 不选i：从前i-1个房间中得到的最大金额和
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)

        def dfs(i):
            if i < 0:
                return 0
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            return res

        return dfs(n - 1)

按回溯实现写出来的会超时

把递归的计算结果保存下来，那么下次递归到同样的入参时，就直接返回先前保存的结果，这样就能避免超时

进行修改，完成记忆化搜索过程

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

        def dfs(i):
            if i < 0:
                return 0
            if cache[i] != -1:
                return cache[i]
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            cache[i] = res
            return res

        return dfs(n - 1)

用cache数组来记录

也可以用python的装饰器cache(推荐)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        @cache
        def dfs(i):
            if i < 0:
                return 0
            res = max(dfs(i - 1), dfs(i - 2) + nums[i])
            return res

        return dfs(n - 1)

单个状态的时间复杂度为O(1)，共有n个状态，所以时间复杂度为O(n)，空间复杂度也为O(n)

自底向上算：递推

dp[i]为从第 0 家到第 i 家，最多能偷多少钱
$$
dp[i] = \max (dp[i-1], dp[i-2]+nums[i])
$$
为了避免负数，拓展dp两个位置
$$
dp[i+2] = \max (dp[i+1], dp[i]+nums[i])
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i] 表示到“第 i-2 个房子”为止时，能偷到的最大金额
        dp = [0] * (n + 2)
        # 遍历每个房子
        for i in range(n):
            # 两种选择：
            # 1 不偷当前房子 -> 金额等于前一个状态 dp[i+1]
            # 2 偷当前房子 -> 金额等于 dp[i] + nums[i]
            #   因为偷了当前房子，就不能偷前一个房子
            dp[i + 2] = max(
                dp[i + 1],        # 不偷当前房子
                dp[i] + nums[i]   # 偷当前房子
            )

        # 最终结果存储在 dp[n+1]
        return dp[n + 1]

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集

0/1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        # 如果总和是奇数，不可能满足
        if total % 2 == 1:
            return False
        target = total // 2
        # dp[j] 表示：是否可以从 nums 中选出若干数，使和恰好等于 j
        dp = [False] * (target + 1)
        dp[0] = True  # 和为0一定可以
        # 遍历每个数字
        for num in nums:
            # 倒序遍历，保证每个 num 只使用一次
            for j in range(target, num - 1, -1):
                # 不选 num：dp[j] 保持原值
                # 选 num：如果之前能凑出 j-num，现在就能凑出 j
                dp[j] = dp[j] or dp[j - num]
        return dp[target]

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

自顶向下算：记忆化搜索

1
2
3
4
5
6
7
8
9
class Solution:
    def climbStairs(self, n: int) -> int:
        @cache
        def dfs(i):
            if i <= 2: # 剩两个台阶刚好直接两种方法
                return i
            return dfs(i - 1) + dfs(i - 2)

        return dfs(n)

自底向上算：递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        dp = [0] * (n + 1)

        dp[1] = 1
        dp[2] = 2

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

        return dp[n]

再进行空间优化就是把dp数组改为两个变量

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        f1 = 1
        f2 = 2

        for _ in range(3, n + 1):
            f1, f2 = f2, f1 + f2
        return f2

目标和

给你一个非负整数数组 nums 和一个整数 target

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1"

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

这道题可以转变为0/1背包问题

自顶向下算：记忆化搜索

假设nums的元素和为S，其中添加正号的元素之和为p，其余添加负号的元素（绝对值）之和为q

那么有p+q=S，又要满足p-q=target，所以得到
$$
\begin{aligned}
p &= \frac{S + target}{2} \\
q &= \frac{S - target}{2}
\end{aligned}
$$
所以转变为选多少个数为+号得到p，变为子集和问题，也就是0-1背包

dfs(i, c) = dfs(i-1, c) + dfs(i-1, c - w[i]))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        # # 如果 p 为负数，或者不是整数，则无解
        if target < 0 or target % 2:
            return 0
        target //= 2

        n = len(nums)

        @cache
        def dfs(i, c):
            if i < 0:
                return 1 if c == 0 else 0
            if c < nums[i]:
                return dfs(i - 1, c)
            # 求方案数所以用+而不是max
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])

        return dfs(n - 1, target)

时间复杂度取决于状态数，状态总数为n×p

递推

求方案数：
$$
dp[i][j] = dp[i-1][j] +dp[i-1][j-nums[i]]
$$
可以发现只依赖于上一个状态

就不需要[i]，直接创建dp[j]记录和为j的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        target += sum(nums)
        # 如果 p 为负数，或者不是整数，则无解
        if target < 0 or target % 2:
            return 0
        bag = target // 2 # 要凑出的子集和 p
        
        # dp[j]表示：从已经遍历过的数字中选一些，使得和为 j 的方案数
        dp = [0] * (bag + 1)
        dp[0] = 1
        # 遍历每一个数字
        for num in nums: # 控制第几个数允许被使用
            # 倒序遍历 j，防止一个 num 在同一轮被重复使用
            for j in range(bag, num - 1, -1):  
                dp[j] += dp[j - num]

        return dp[bag]

倒序遍历是为了避免同一个数会被用多次，确保 dp[j-num] 仍然是上一轮的状态，保证每个 num 在这一轮只会被使用一次

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额

计算并返回可以凑成总金额所需的 最少的硬币个数

如果没有任何一种硬币组合能组成总金额，返回 -1

你可以认为每种硬币的数量是无限的

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

完全背包问题

自顶向下算：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)

        @cache
        def dfs(i, c):
            if i < 0:
                return 0 if c == 0 else inf # 以inf作为失败标志
            if c < coins[i]:
                return dfs(i - 1, c)
            return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)

        ans = dfs(n - 1, amount)
        return ans if ans < inf else -1

自底向上算：递推

定义dp[j]为凑成金额$j$的最小硬币数

要找最小值，所以初始化为无穷大
$$
dp[j] = \min (dp[j], dp[j-coin]+1)
$$
因为是完全背包问题，允许重复使用，所以可以正序，不需要像0/1背包问题倒序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        # dp[j] 表示：凑出金额 j 所需要的最少硬币数量
        dp = [inf] * (amount + 1)
        dp[0] = 0
        # 遍历每一种硬币
        for coin in coins:
            # j 从 coin 开始，因为 j < coin 时无法使用该硬币
            # 正序遍历：允许同一种硬币被重复使用（完全背包）
            for j in range(coin, amount + 1):
                # 如果最后使用一枚 coin
                # 那么之前需要凑出 j-coin
                # 所以硬币数 = dp[j-coin] + 1
                dp[j] = min(
                    dp[j],           # 不使用当前 coin 的情况
                    dp[j - coin] + 1 # 使用当前 coin 的情况
                )
        return dp[amount] if dp[amount] < inf else -1

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是

示例 1：

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3
输入：n = 13
输出：2
解释：13 = 4 + 9

自底向上算：递推

先枚举物品，再枚举容量

完全背包问题

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

class Solution:
    def numSquares(self, n: int) -> int:
        # dp[j] 表示：和为 j 时，所需要的最少完全平方数数量
        dp = [inf] * (n + 1)
        # 凑出和为 0 不需要任何数
        dp[0] = 0

        # 枚举所有不超过 n 的完全平方数
        for num in range(1, int(n**0.5) + 1):
            # 当前可用的平方数
            square = num * num
            # 完全背包：正序遍历
            for j in range(square, n + 1):
                # 如果最后使用一个 square
                # 那么之前需要凑出 j - square
                dp[j] = min(
                    dp[j],               # 不使用当前平方数
                    dp[j - square] + 1   # 使用当前平方数
                )
        # dp[n] 就是凑出 n 的最少平方数数量
        return dp[n]

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

动态规划

状态转移：

对于每个位置 i，尝试最后一刀切在 j：

  • 前面 s[:j] 能拆
  • 后面 s[j:i] 在字典中

那么$dp[i] = True$

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]) -> bool:
        # 将 wordDict 转为 set 提高查找效率
        wordSet = set(wordDict)
        n = len(s)
        # dp[i] 表示：字符串前 i 个字符 s[:i] 是否可以被拆分
        dp = [False] * (n + 1)
        # 空字符串可以认为是可拆分的（递推起点）
        dp[0] = True
        # 判断 s[:i] 能否被拆分
        for i in range(1, n + 1):
            # 枚举最后一刀切在哪里
            # s[:j] | s[j:i]
            for j in range(i):
                # 如果前半段可以拆分且后半段是字典中的单词
                if dp[j] and s[j:i] in wordSet:
                    # 整个 s[:i] 也可以拆分
                    dp[i] = True
                    break
        return dp[n]

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

回溯

1
2
3
4
5
6
7
8
9
10
11
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[i] = \max(dp[i],dp[j]+1)\quad j<i \quad and \quad nums[j]<nums[i]
$$

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)
        # dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                # 如果 nums[i] 可以接在 nums[j] 后面
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        # LIS 可能以任何位置结尾
        return max(dp)

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

请注意，一个只包含一个元素的数组的乘积是这个元素的值

示例 1:

1
2
3
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

这题不能简单维护一个值，因为乘积需要维护最大值和最小值，因为负的值再乘负值可以得到很大的正值
$$
dpMax[i] = \max(nums[i],dpMax[i-1]\cdot nums[i],dpMin[i-1]\cdot nums[i])\\
dpMin[i] = \min(nums[i],dpMax[i-1]\cdot nums[i],dpMin[i-1]\cdot nums[i])
$$

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

        # dpMax[i]: 以 nums[i] 结尾的最大乘积
        # dpMin[i]: 以 nums[i] 结尾的最小乘积
        dpMax = [0] * n
        dpMin = [0] * n

        dpMax[0] = nums[0]
        dpMin[0] = nums[0]

        ans = nums[0]

        for i in range(1, n):
            a = nums[i]
            b = dpMax[i - 1] * nums[i]
            c = dpMin[i - 1] * nums[i]

            dpMax[i] = max(a, b, c)
            dpMin[i] = min(a, b, c)
            ans = max(ans, dpMax[i])
        return ans

因为第 i 个状态只依赖第 i-1 个状态，所以可以压成 O(1) 空间

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

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # mx: 以当前元素结尾的最大乘积
        # mn: 以当前元素结尾的最小乘积
        # ans: 全局最大答案
        mx = mn = ans = nums[0]

        for i in range(1, len(nums)):
            x = nums[i]

            # 先保存上一轮状态
            prev_mx, prev_mn = mx, mn
            mx = max(x, prev_mx * x, prev_mn * x)
            mn = min(x, prev_mx * x, prev_mn * x)

            # 更新全局答案
            ans = max(ans, mx)

        return ans

买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股

返回你能获得的最大利润

示例 1：

1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

1
2
3
4
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

回溯

$dfs(i,1)$代表第$i$天结束时，手里持有一股股票的情况下，能够获得的最大利润

状态转移方程
$$
dfs(i,0) = \max (dfs(i-1,0),; dfs(i-1,1) + prices[i])\\
dfs(i,1) = \max(dfs(i-1,1),; dfs(i-1,0) - prices[i])
$$
递归边界：

  • $dfs(-1,0) = 0$ 第 0 天开始未持有股票，利润为 0
  • $dfs(-1,1) = -\infty$ 第 0 天开始不可能持有股票

递归入口
$$
\max(dfs(n-1,0),; dfs(n-1,1)) = dfs(n-1,0)
$$
因为最后一天再持有肯定获得不了最大利润

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

        @cache
        def dfs(i, hold):
            if i < 0:
                return -inf if hold else 0
            if hold:
                return max(dfs(i - 1, True), dfs(i - 1, False) - prices[i])
            return max(dfs(i - 1, False), dfs(i - 1, True) + prices[i])

        return dfs(n - 1, False)

递推

改写递推
$$
dp[i][0] = \max(dp[i-1][0], dp[i-1][1]+prices[i])\\
dp[i][1] = \max(dp[i-1][1],dp[i-1][0]-prices[i])
$$
挪一位避免负数

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][0] = 0
        dp[0][1] = -inf
        for i in range(n):
            dp[i + 1][0] = max(dp[i][0], dp[i][1] + prices[i])
            dp[i + 1][1] = max(dp[i][1], dp[i][0] - prices[i])
        return dp[n][0]

买卖股票的最佳时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

示例 1:

1
2
3
输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

1
2
输入: prices = [1]
输出: 0

和上一题类似，只需简单修改

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

        @cache
        def dfs(i, hold):
            if i < 0:
                return -inf if hold else 0
            if hold:
                return max(dfs(i - 1, True), dfs(i - 2, False) - prices[i])
            return max(dfs(i - 1, False), dfs(i - 1, True) + prices[i])

        return dfs(n - 1, False)

return max(dfs(i - 1, True), dfs(i - 2, False) - prices[i]) 这是唯一变动，因为如果(i-1, False)可能会有在i-1卖出的情况，就无法买入了，所以需要避免，改为(i-2, False)

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

        dp = [[0] * 2 for _ in range(n + 2)]
        dp[0][0] = 0
        dp[0][1] = -inf
        dp[1][0] = 0
        dp[1][1] = -inf

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

右移两位即可

买卖股票的最佳时机 IV

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

示例 1：

1
2
3
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

1
2
3
4
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

相比之前的多了一个交易次数$j$，判断是否还>0就行，注意这题没有冷冻期

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

        @cache
        def dfs(i, j, hold):
            if j < 0:
                return -inf
            if i < 0:
                return -inf if hold else 0
            if hold:
                return max(dfs(i - 1, j, True), dfs(i - 1, j, False) - prices[i])
            return max(dfs(i - 1, j, False), dfs(i - 1, j - 1, True) + prices[i])

        return dfs(n - 1, k, False)

多维动态规划

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列

示例 1：

1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

1
2
3
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

回溯

选或者不选第$i/j$个
$$
\begin{aligned}
dfs(i,j) =
\begin{cases}
dfs(i-1,j-1) + 1, & s[i] = t[j] \\
\max(dfs(i-1,j), dfs(i,j-1)), & s[i] \ne t[j]
\end{cases}
\end{aligned}
$$

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

        @cache
        def dfs(i, j):
            if i < 0 or j < 0:
                return 0
            if text1[i] == text2[j]:
                return dfs(i - 1, j - 1) + 1
            return max(dfs(i - 1, j), dfs(i, j - 1))

        return dfs(m - 1, n - 1)

递推

进行改写
$$
\begin{aligned}
dp[i][j] =
\begin{cases}
dp[i-1][j-1] + 1, & s[i] = t[j] \\
\max(dp[i-1][j], dp[i][j-1]), & s[i] \ne t[j]
\end{cases}
\end{aligned}
$$
为了避免负数，移动一位
$$
\begin{aligned}
dp[i+1][j+1] =
\begin{cases}
dp[i][j] + 1, & s[i] = t[j] \\
\max(dp[i][j+1], dp[i+1][j]), & s[i] \ne t[j]
\end{cases}
\end{aligned}
$$

1
2
3
4
5
6
7
8
9
10
11
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, x in enumerate(text1):
            for j, y in enumerate(text2):
                if x == y:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
        return dp[m][n]

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

记忆化搜索

类似上一题，相等时不操作，直接前移

不相等时，要么删除，要么插入，要么替换
$$
\begin{aligned}
dfs(i,j) =
\begin{cases}
dfs(i-1,j-1) , & word_1[i] = word_2[j] \\
\min(dfs(i-1,j), dfs(i,j-1), dfs(i-1,j-1))+1, & word_1[i] \ne word_2[j]
\end{cases}
\end{aligned}
$$

第一项是插入，插入一样的以后退化成$(i-1,j-1)$，但是因为插入所以 $i$ 不动

第二项是删除，删除后$i$前移，$j$不动；第三项为替换，直接前移

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, j - 1), dfs(i - 1, j), dfs(i - 1, j - 1)) + 1

        return dfs(m - 1, n - 1)

递推
$$
\begin{aligned}
dp[i+1][j+1] =
\begin{cases}
dp[i][j], & word_1[i] = word_2[j] \\
\min(dp[i][j+1], dp[i+1][j],dp[i][j])+1, & word_1[i] \ne word_2[j]
\end{cases}
\end{aligned}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
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)]
        dp[0] = list(range(n + 1))
        for i, x in enumerate(word1):
            dp[i + 1][0] = i + 1
            for j, y in enumerate(word2):
                if x == y:
                    dp[i + 1][j + 1] = dp[i][j]
                else:
                    dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) + 1
        return dp[m][n]

其实相对来说记忆化搜索好写，这里递推要把初始条件嵌入进去

最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

1
2
3
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

1
2
3
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

直接回溯
$$
\begin{aligned}
dfs(i,j)=
\begin{cases}
dfs(i+1,j-1)+2, & s[i]=s[j] \\
\max(dfs(i+1,j),dfs(i,j-1)), & s[i]\ne s[j]
\end{cases}
\end{aligned}
$$

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)

        @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, n - 1)

改递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]

最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

用动态规划不太好写

用中心拓展法比较简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0

        def expand(left: int, right: int):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return left + 1, right - 1

        for i in range(len(s)):
            l1, r1 = expand(i, i)
            l2, r2 = expand(i, i + 1)
            if r1 - l1 > end - start:
                start, end = l1, r1
            if r2 - l2 > end - start:
                start, end = l2, r2

        return s[start : end + 1]

利用回文串的对称性，枚举所有可能的中心，并从中心向两边扩展，求出每个中心对应的最长回文，最终取最大值

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

1
2
输入：m = 3, n = 7
输出：28

示例 2：

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

记忆化搜索

状态定义与状态转移方程：
$$
dfs(i,j) = dfs(i-1,j)+dfs(i,j-1)
$$

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dfs(i, j):
            if i < 0 or j < 0:
                return 0
            if i == 0 and j == 0:
                return 1
            return dfs(i - 1, j) + dfs(i, j - 1)

        return dfs(m - 1, n - 1)

递推
$$
dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]
$$

1
2
3
4
5
6
7
8
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        dp[0][1] = 1 # 特殊初始化
        for i in range(m):
            for j in range(n):
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
        return dp[m][n]

如果极限优化

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

        return dp[-1]

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

示例 1：

1
2
3
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小

示例 2：

1
2
输入：grid = [[1,2,3],[4,5,6]]
输出：12

记忆化搜索

状态定义与状态转移方程：
$$
dfs(i,j) = \min(dfs(i-1,j),dfs(i,j-1)) + grid[i][j]
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        @cache
        def dfs(i, j):
            if i < 0 or j < 0:
                return inf

            if i == 0 and j == 0:
                return grid[0][0]

            return min(dfs(i - 1, j), dfs(i, j - 1)) + grid[i][j]

        return dfs(len(grid) - 1, len(grid[0]) - 1)

注意越界

递推
$$
dp[i][j] = \min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
$$

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

        return dp[m][n]
1
2
3
4
5
6
7
8
9
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        dp = [inf] * (len(grid[0]) + 1)
        dp[1] = 0
        for row in grid:
            for j, x in enumerate(row):
                dp[j + 1] = min(dp[j], dp[j + 1]) + x

        return dp[-1]

因为只需要两个状态，可以简化空间

栈

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

容易错误点：忽略最小栈的维护，因为要考虑到出栈以后最小值会发生变化，所以要记录每个值进入时的最小值，方便值出的时候快速更新最小值

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 MinStack:

    def __init__(self):
        self.stack = []
        self.min = [inf]

    def push(self, val: int) -> None:
        self.stack.append(val)
        self.min.append(min(val, self.min[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.min.pop()

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

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

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

1
2
3
输入：s = "()[]{}"

输出：true

示例 2：

1
2
3
输入：s = "([)]"

输出：false

邻项消除问题，这类问题都可以用栈解决

由于括号两两一对，所以长度必须为偶数

可以创建一个哈希表，保存每个右括号对应的左括号，这样可以直接判断栈顶的左括号是否与右括号为同一类型，从而省去大量 if-else 判断

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: # c是左括号
                st.append(c) # 入栈
            elif not st or st.pop()!=mp[c]: 
                return False # 没有左括号或者不匹配
        return not st # 栈内必须为空说明匹配完

如果左边直接入栈，如果右边就匹配，如果栈为空或者不匹配，直接返回False，移出栈顶

最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"

示例 1：

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

1
2
3
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

1
2
输入：s = ""
输出：0

维护一个栈，栈里存的是下标，初始化放入下标-1作为哨兵

弹栈代表碰到)，如果栈不为空说明匹配成功，栈顶编号为(的前一个编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        ans = 0

        for i, ch in enumerate(s):
            if ch == "(":
                stack.append(i)
            else:
                stack.pop()
                # 如果栈空了，说明没匹配上
                if not stack:
                    stack.append(i) # 标号作为新边界
                else:
                    # 如果匹配上
                    # stack[-1] 正好是当前这段左边界前一个位置
                    ans = max(ans, i-stack[-1])
        return ans

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

1
2
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

1
2
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

核心思想不是硬拼字符串，而是：

  • 遇到数字，解析完整重复次数 k
  • 遇到 [，把当前状态压栈
  • 遇到 ]，弹栈并把当前子串重复 k 次后接回去
  • 遇到普通字符，直接拼到当前子串

维护两个当前状态：

  • cur_num：当前解析到的重复次数
  • cur_str：当前这一层正在构造的字符串

维护一个栈 stack，栈里存的是进入 [ 之前的状态

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 decodeString(self, s: str) -> str:
        stack = []   # 栈：保存进入 '[' 前的状态 (之前的字符串, 重复次数)
        cur_str = "" # 当前层正在构造的字符串
        cur_num = 0  # 当前解析到的重复次数 k

        for c in s:
            if c.isdigit():
                # 如果是数字，更新重复次数
                # 这样可以处理多位数，例如 "12[a]"
                cur_num = cur_num * 10 + int(c)

            elif c.isalpha():
                # 普通字符，直接拼接到当前字符串
                cur_str += c

            elif c == "[":
                # 模拟递归
                stack.append((cur_str, cur_num))
                # 重置
                cur_str = ""
                cur_num = 0

            else:
                # 出栈
                prev_str, num = stack.pop()
                # 前缀加重复部分
                cur_str = prev_str + cur_str * num

        return cur_str

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

从左往右思考单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        # 结果数组，初始化为0
        # 默认值0表示：之后没有更高温度
        ans = [0] * n
        # 单调栈：存放的是“下标”
        # 栈中对应的温度保持单调递减
        stack = []
        for i in range(n):
            # 如果当前温度比栈顶对应的温度高, 说明找到了更高温度
            while stack and temperatures[i] > temperatures[stack[-1]]:
                j = stack.pop()
                # 等待天数 = 当前下标 - 之前下标
                ans[j] = i - j
            stack.append(i)
        return ans

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

经过分析，对于某根柱子来说，它能形成的最大矩形面积是找比它高度低的左右两端围成的矩形，边界设置为-1与n

需要三次循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left = [-1] * n  # 左边界数组，初始化为 -1
        st = []
        for i, h in enumerate(heights):
            # 找到左边第一个比当前柱子矮的柱子
            while st and heights[st[-1]] >= h: 
                st.pop() # 高的直接出栈
            if st:   # 如果栈不空，栈顶就是左边界索引
                left[i] = st[-1]
            st.append(i)

        right = [n] * n
        st.clear()
        for i in range(n - 1, -1, -1):
            h = heights[i]
            while st and heights[st[-1]] >= h:
                st.pop()
            if st:
                right[i] = st[-1]
            st.append(i)
        ans = 0
        for h, l, r in zip(heights, left, right):
            # 矩形宽度 = 右边界 - 左边界 - 1
            ans = max(ans, h * (r - l - 1))
        return ans

但其实发现，在找左边界的过程中，如果栈顶高度大于当前高度，那么对于栈顶，当前就是它的右边界

这样节省了一次循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left = [-1] * n  # 左边界数组，初始化为 -1
        right = [n] * n
        st = []
        for i, h in enumerate(heights):
            # 找到左边第一个比当前柱子矮的柱子
            while st and heights[st[-1]] >= h: 
                right[st.pop()] = i
            if st:   # 如果栈不空，栈顶就是左边界索引
                left[i] = st[-1]
            st.append(i)
        ans = 0
        for h, l, r in zip(heights, left, right):
            # 矩形宽度 = 右边界 - 左边界 - 1
            ans = max(ans, h * (r - l - 1))
        return ans

堆

堆一般适合解决

  • 找第 k 大 / 第 k 小
  • 优先队列（priority queue）

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

三路划分

把数组按某个 pivot 分成三段：大于 / 等于 / 小于 的方法，本质是在一次扫描中“同时处理比较和去重

三路划分也叫“荷兰国旗问题”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        pivot = random.choice(nums)

        left = [x for x in nums if x > pivot]
        mid = [x for x in nums if x == pivot]
        right = [x for x in nums if x < pivot]

        L, M = len(left), len(mid)

        if k <= L:
            # 第 k 大在比 pivot 大的集合里
            return self.findKthLargest(left, k)
        elif k <= L + M:
            # 第 k 大正好落在等于 pivot 的集合里
            return pivot
        else:
            # 第 k 大在比 pivot 小的集合里，注意要更新 k 的值
            return self.findKthLargest(right, k - L - M)

这样时间复杂度为O(n)，空间复杂度为O(n)

如果要空间复杂度为O(1)呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        target = n - k  # 第k大在升序列表中的位置为n-k
        left, right = 0, n - 1 # 闭区间

        while True:
            p = self.partition(nums, left, right)
            if p == target:
                return nums[p]
            elif p < target:
                left = p + 1
            else:
                right = p - 1

    def partition(
        self, nums: List[int], left: int, right: int) -> int:
        """
        在子数组 [left, right] 中随机选择一个基准元素 pivot
        经过原地划分后：
        - nums[left : p] < pivot
        - nums[p] = pivot
        - nums[p+1 : right+1] >= pivot
        返回 pivot 最终所在下标 p
        """
        i = random.randint(left,right)
        pivot = nums[i]
        nums[i], nums[right] = nums[right], nums[i]
        store_idx = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[store_idx], nums[i] = nums[i], nums[store_idx]
                store_idx += 1
        nums[store_idx], nums[right] = nums[right], nums[store_idx]
        return store_idx

前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

1
2
3
输入：nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

1
2
3
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

优先队列：堆

python里heapq是最小堆，头部是最小数

1
2
3
4
5
6
7
8
9
10
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)  # 统计频率
        heap = [] # 小顶堆，维护 k 个最大频率

        for num, freq in cnt.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)
        return [num for _, num in heap]

时间复杂度O(nlogn)，空间复杂度O(n)

桶排序

因为在优先队列需要不断排序，所以时间复杂度非线性

如果要降为线性可以维护一个频率桶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)  # 统计频率
        max_cnt = max(cnt.values())

        # 把出现次数相同的元素，放到同一个桶中
        buckets = [[] for _ in range(max_cnt + 1)]
        for num, freq in cnt.items():
            buckets[freq].append(num)

        # 倒序遍历buckets，把出现次数前k大的加入答案
        ans = []
        for freq in range(max_cnt, 0, -1):
            ans += buckets[freq] # 拼接结果
            if len(ans) >= k:
                return ans[:k]

技巧

只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

1
2
3
输入：nums = [2,2,1]

输出：1

示例 2 ：

1
2
3
输入：nums = [4,1,2,1,2]

输出：4

利用异或运算 a⊕a=0 的性质，可以用异或来「消除」所有出现了两次的元素，最后剩下的一定是只出现一次的元素

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for x in nums:
            ans ^= x
        return ans

关键性质：
$$
a \oplus a = 0 \qquad a\oplus0 =a
$$

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题

示例 1：

1
2
输入：nums = [3,2,3]
输出：3

示例 2：

1
2
输入：nums = [2,2,1,1,1,2,2]
输出：2

统计次数，再比大小

1
2
3
4
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        return max(cnt, key = cnt.get)

时间复杂度O(n)，空间复杂度O(n)

降低空间复杂度：

1
2
3
4
5
6
7
8
9
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans = hp = 0
        for x in nums:
            if hp == 0:
                ans, hp = x, 1
            else:
                hp += 1 if x == ans else -1
        return ans

相当于分为两类，非多数和多数

hp相当于累计值，多数肯定会>0

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题

示例 1：

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

1
2
输入：nums = [2,0,1]
输出：[0,1,2]

**进阶：**你能想出一个仅使用常数空间的一趟扫描算法吗？

荷兰旗问题

维护三路

  • left：下一个0放的位置
  • i：当前扫描的位置
  • right：下一个2放的位置

那么[0, left)为0；[left, i)为1；[i, right]为未处理部分；(right, n-1]为2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left, i, right = 0, 0, n - 1
        while i <= right:
            if nums[i] == 0:
                nums[left], nums[i] = num[i], nums[left]
                left += 1
                i += 1
            elif nums[i] == 1:
                i += 1
            else:
                nums[i], nums[right] = nums[right], num[i]
                right -= 1

第三路不移动i是因为不知道原来right的是什么值，需要再处理一次

下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2]
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列

给你一个整数数组 nums ，找出 nums 的下一个排列

必须原地修改，只允许使用额外常数空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = n-2
        # 从右向左，找第一个不满足递增的位置
        while i>=0 and nums[i] >=nums[i+1]:
            i -=1
        # 如果不是整个序列递增
        if i>=0:
            j = n-1
            # 找到第一个大于nums[i]的数
            while nums[j]<=nums[i]:
                j-=1
            nums[i], nums[j] = nums[j], nums[i]
            # 交换以后左边的数已经满足大于，右边要尽可能小
            # 刚刚过程中是从右到左递增，反转一下就是最小的大于数
        
        # 如果i<0刚好就是整个序列反转
        left, right = i+1, n-1
        while left<right:
            nums[left], nums[right] = nums[right], nums[left]
            left+=1
            right-=1

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

1
2
输入：nums = [1,3,4,2,2]
输出：2

示例 2：

1
2
输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

1
2
输入：nums = [3,3,3,3,3]
输出：3

如果不考虑空间

1
2
3
4
5
6
7
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)

考虑O(1)

因为数字都在 [1, n] 范围内

所以把数组看成“链表”，成为环形链表

因为只有重复元素对应的那个值，才会被“多个节点指向”，从而成为环的唯一入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0 # 0 一定不在环上，适合作为起点
        while True:
            slow = nums[slow] # 等价于 slow = slow.next
            fast = nums[nums[fast]]  # 等价于 fast = fast.next.next
            if fast == slow: # 快慢指针移动到同一个节点
                break

        head = 0 # 再用一个指针，从起点出发
        while slow != head:
            slow = nums[slow]
            head = nums[head]

        return slow # 入环口即重复元素

参考环形链表II