一、两数之和#

1. 题面#

1. 两数之和#

难度：简单

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

进阶： 你可以想出一个时间复杂度小于 O(n^2) 的算法吗？

2. 解法#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 梦开始的地方
# 如果强硬做需要n方二重循环，首先体现出哈希表空间换时间

# 打一个哈希表值:下标，每一次找哈希表中target-val的数字，如果找到了就返回下标列表，找不到就存入哈希表
def solution(nums,target)->list:
    dict = {}
    for i,val in enumerate(nums):
        if target-val in dict:
            return [i,dict[target-val]]
        else:
            dict[val] = i
    # 假设都对应答案不用考虑找不到

if __name__ == "__main__":
    # 我们让输入两行，一行为逗号隔开的数字，另一行target
    nums = list(map(int,input().strip().split(',')))
    target = int(input().strip())
    print(solution(nums,target))

3. 反思#

本题是基础哈希表空间换时间，第一次做的时候没有加else，虽然这题无所谓，但是别的题可能会有区别。
还有一个细节，我用了dict，实际上覆盖了内置的dict，还是用mp比较好

二、字母的同分异构词#

1. 题面#

49. 字母异位词分组#

难度：中等

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

示例 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 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

2. 解法1-{}#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 白痴做法是排序判断，python快排是onlogn
# 保持on可以用哈希表，这题的意思换句话就是将字母出现个数一样的放在一起
# 维持一个字母表:字符串列表

def solution(strs)->list[list[str]]:
    mp = {}
    for s in strs:
        ap = [0]*26
        for i in s:
            ap[ord(i)-ord('a')] += 1
        # 注意list不能当key
        key = tuple(ap)
        if key not in mp:
            mp[key]=[]
        mp[key].append(s)
    # 现在按照每个ap返回组成的字符串列表
    return list(mp.values())


if __name__ == "__main__":
    # 输入一串str
    strs = [s.strip().strip('"') for s in input().strip().split(',')]
    print(solution(strs))

3. 解法2-defaultdict#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

from collections import defaultdict

def solution(strs)->list[list[str]]:
    # defaultdict可以避免查空建表，遇到没见过的key默认开辟
    # defaultdict(list)就是默认传进来没见过的用list()先构造，也就是list()默认值空列表
    # 同理defaultdict(int)，int()的默认值是0
    # defaultdict(set)还可以叠去重
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord("a")] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())


if __name__ == "__main__":
    # 输入一串str
    strs = [s.strip().strip('"') for s in input().strip().split(',')]
    print(solution(strs))

4. 反思#

实际上做到这里的时候想到用这种方法，但是还是有点小梗塞。容易出错的点：list不能作为key，需要tuple；ord函数别忘了；mp.values()的用法，返回values的迭代器，用list转为答案数组
如果使用默认数组，不需要先判key空产生[]再append，直接用defaultdict(list)，等于设置了键值的值默认为list的默认值空列表；同理，这里设置为int就是默认值为0
注意输入处理，因为默认复制力扣的输入是有"的，而想去掉双引号，需要用单引号包裹来strip('"')。

三、最长连续序列#

1. 题面#

128. 最长连续序列#

难度：中等

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

2. 解法#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 需要on解决问题，只能遍历一遍，必须空间换时间
# 我们先遍历一遍，将数组放进集合，然后找下一个有可能的数字。虽然是循环套循环，但是终归是有限次查找，所以为on

def solution(nums)->int:
    num_set = set(nums)
    longest = 0
    current_length = 0
    for num in num_set:
        current = num
        current_length = 1
        # 循环找有限个后续
        while current + 1 in num_set:
            current += 1
            current_length += 1 
        longest = max(longest,current_length)
    return longest

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

3. 反思#

这题肯定也是第一时间想到空间换时间，但是没想到哈希存什么。主要是害怕for套for复杂度超过on，但是其实里面是有限次循环，还是on。
不用set的话问了题友，也是哈希打一遍标记，然后前后找。

四、移动零#

1. 题面#

283. 移动零#

难度：简单

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

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

示例 1:

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

示例 2:

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

提示 :

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

**进阶：**你能尽量减少完成的操作次数吗？

2. 解法#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 双指针搬运法，很简单
def solution(nums):
    i,j = 0, 1
    n = len(nums)
    if n<=1:
        return nums
    while j<n:
        if nums[j]!=0:
            nums[i]=nums[j]
            i+=1
        j+=1
    # 如果i没走完，则后面全部置零
    while i<n:
        nums[i]=0
        i+=1
    return nums

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

2. 反思#

没啥好说的，就是简单的移动插入，跟插入排序有点像，需要注意的是while循环下面别忘了移动变量，这个经常忘记。

五、盛水最多的容器#

1. 题面#

11. 盛最多水的容器#

难度：中等

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

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

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

说明： 你不能倾斜容器。

示例 1：

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

示例 2：

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

提示：

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这题其实是双指针，一前一后，每次贪心移动比较矮的柱子（因为木桶效应，矮柱子比较碍事）
def solution(heights):
    n = len(heights)
    i, j = 0, n-1
    max_pool = 0
    while i !=j:
        min_height = min(heights[i],heights[j])
        max_pool = max(max_pool,min_height*(j-i))
        if heights[i]<=heights[j]:
            i+=1
        else:
            j-=1
    return max_pool

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

3. 反思#

这题老是幻视成单调栈，但是实际上不是需求"第一个比xx大/小"的量，卡了半天不知道怎么写。
但是这题实际上是一个贪心，理论依据是"移动高的那边一定不可能得到更优解"，所以只能移动矮的那边去保留希望。这个解释还是让人感觉懵懵的。
询问码u，最好的解释是"移动小的那根不一定能让水更多，但是大的那根肯定会变少"，因为移动大的那根，小的那根被限制住了，无论如何都不会变大，反而使宽度减小。

六、三数之和#

1. 题面#

15. 三数之和#

难度：中等

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 第一个想法比较直白，二重循环来找第三个数，从而变成两数之和，但是这样就on方了
# 好吧只能on方，想什么呢。既然只有on方，那排序也是可以的了，然后用更优雅的方法：固定一个数+双指针移动
def solution(nums):
    nums.sort()
    ans = []
    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            # 以0为分界决定移动哪个指针
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                ans.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    return ans

if __name__=="__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

七、接雨水#

1. 题面#

42. 接雨水#

难度：困难

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

示例 1：

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

示例 2：

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

提示：

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 经典单调栈的题目，只要能识别为找到第一个比xxx大/小的题目都可以单调栈
# 本题要找左侧第一个比它高的，还要找右侧第一个比它高的，这样才能形成水洼。左侧最高可以用递减栈记录，右侧最高只能通过出栈的瞬间判断。不过不用担心有的栈不会被弹出，因为找不到右侧比它更高的，就行不成水洼；左侧同理，找left的时候要进行一次保护。
# 坐标语言，(right-left-1)*(左右那个比较矮的和当前的高度差)=累积的水泊
from collections import deque

def solution(height:list):
    # 存储 值:下标
    q = deque()
    pool = 0
    for i,h in enumerate(height):
        while q and q[-1][0]<h:
            curr_val,curr = q.pop()
            right = i
            rigth_val = h
            # 左边第一个比它高的是弹出后的栈顶。如果左边没了，形不成水洼
            if not q:
                break
            left_val,left = q[-1]
            # 加池子
            pool += (min(left_val,rigth_val)-curr_val)*(right-left-1)
        # 进栈
        q.append((h,i))
    return pool

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

3. 反思#

实际解题的思路已经写的很清楚了，重要的就是单调栈的思想。
注意这里不需要全部弹出，右侧可能没有更高的边界；需要注意的是左侧可能会没有水洼，所以要保护一下空栈。
这里right、right_val就是当前的i、h，更简的话可以不定义right相关变量

八、无重复字符的最长子串#

1. 题面#

3. 无重复字符的最长子串#

难度：中等

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 一眼滑动窗口，维持一个哈希表记录window里面的字母有没有重复。每次窗口有效时，记录window长度，更新最大值
def solution(s: str) -> int:
    window = {}
    left = 0
    max_length = 0
    for right, ch in enumerate(s):
        window[ch] = window.get(ch, 0) + 1
        # 这里写只要不合法，就移动左边
        while window[ch] > 1:
            window[s[left]] -= 1
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length


if __name__ == "__main__":
    s = input()
    print(solution(s))

3. 反思#

我其实感觉滑动窗口的思路比较简单，但是比较考验码力，特别是边界和条件判断的地方，特别容易绕晕。
我第一版有很多疏漏，现在是更新过的版本。易错点1：left移动的条件不对，应该写在while里面的是"不合法"的条件，移动left直到合法；易错点2：不能用len(window)，即使哈希值归0了，键值对还在。

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

1. 题面#

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

难度：中等

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

示例 1:

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

示例 2:

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

提示:

1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 依旧滑动窗口
# 换言之，我们需要将p的哈希表和s中滑动窗口的哈希表一样，我们可以用validation记录一样的键时值一样，即合法键值对个数，如果和p的哈希表一样长就对了（为什么不直接==两个哈希表呢？因为哈希表全等是逐元素判断，写上时间就爆了。
def solution(s: str, p: str) -> list[int]:
    need = {}
    window = {}
    # 填充需求哈希表
    for c in p:
        need[c] = need.get(c, 0) + 1
    left = 0
    right = 0
    # 满足条件的元素个数，后面和len(need)比较
    valid = 0
    ans = []

    while right < len(s):
        c = s[right]
        right += 1
        # 右侧扩张，并判断是否增加valid
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1
        # 我们当有效元素达到要求时，再来看长度，如果满足要求就加上答案，否则left移动
        while valid == len(need):
            if right - left == len(p):
                ans.append(left)

            # 这部分逻辑与right的对称
            d = s[left]
            left += 1

            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                # 无论怎么样移动后都要给这个window最后调整-1
                window[d] -= 1

    return ans

if __name__ == "__main__":
    s = input().strip()
    p = input().strip()
    print(solution(s,p))

3. 反思#

这题是非常值得反复练习的滑动窗口题目，我重写的时候又弄错了，将right - left == len(p)作为while条件，这样还要先移动right，非常复杂容易出错。正确的一体化思路，应当是将valid个数合格作为左边收缩的起点，收缩一直进行到valid不满足为止。
左右的操作实际上是对称的，取值、移动，右侧先动哈希再看valid，左侧先看valid再动哈希。其中的区别在于，left是看先满足再丢弃，right是先拿取再看是否满足。

十、和为k的子数组#

1. 题面#

560. 和为 K 的子数组#

难度：中等

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 因为必须连续，需要满足的东西顺序无关，所以依旧滑动窗口
def solution(nums:list,k:int)->int:
    total = 0
    left, right = 0, 0
    ans = 0
    n = len(nums)
    while right<n:
        c = nums[right]
        right += 1
        total += c
        while total > k:
            c = nums[left]
            left += 1
            total -= c
        # 现在窗口合法
        if total == k:
            ans +=1
    return ans

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    k = int(input())
    print(solution(nums,k))

3. 反思#

和前面相比算是比较简单的滑动窗口，不需要哈希表只需要维持一个total
但是这题意义在于，告诉我们滑动窗口是用来求"连续子部分的与顺序无关属性"时使用（有点废话因为顺序有关就直接遍历了）

十一、滑动窗口最大值#

1. 题面#

239. 滑动窗口最大值#

难度：困难

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

返回 滑动窗口中的最大值 。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

2. 解法1 - 单调队列#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 本地要求的是连续子数组（还固定长度）的与顺序无关的属性（最大值），但是与哈希表、总和不同的是，max不能回退。
# 实际上这一题做法是单调递减队列。单调队列的思想在于维持一个“有效期”，因为max不能回退，就要存储过去合法的max，队首是目前的max
from collections import deque

def solution(nums,k):
    q = deque()
    ans = []
    # 这里我们选择存下标，一般比存值更稳定，可以避免重复值
    for i,x in enumerate(nums):
        # 构造递减队列
        while q and nums[q[-1]]<=x:
            q.pop()
        q.append(i)
        # 检查左边有效期，下标已经不在窗口内，踢出队首
        if q[0]<= i-k:
            q.popleft()
        # 如果长度达到k了，就记录答案。由于前面if的约束，必定会-1，然后+1，所以这里一定是要求的长度
        if i>= k-1:
            ans.append(nums[q[0]])
    return ans

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    k = int(input())
    print(solution(nums,k))

3. 解法2 - 堆#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 我们依旧需要维持有序性，单调队列确实是最好的方法，但是思路有点绕
# 一个比较直白的方法，就是做一个最大堆，堆里存值和下标，堆顶下标超过了窗口范围，就弹出，然后下标达到k之后，不断进入、弹出……
import heapq

def solution(nums,k):
    ans,pq = [],[]
    for i,val in enumerate(nums):
        heapq.heappush_max(pq,(val,i))
        while pq and pq[0][1]<= i-k:
            heapq.heappop_max(pq)
        if i>=k-1:
            ans.append(pq[0][0])
    return ans

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    k = int(input())
    print(solution(nums,k))

4. 反思#

这题一开始想到的还是滑动窗口，但是不知道怎么维护max的回退，一开始想到用栈，但是栈没办法处理退出的就是最大值，第二个大值在哪这个问题。
这题的破局关键其中之一就是存储下标。对于可能有重复值的题目，存下标是最安全稳妥的方法。
这题的标准思路是单调队列，单调队列常被用来解决"有效性窗口"的问题，比如这题，就是维持了一系列候选有效的max值，left移动就看左边的第一个值有没有过期（也就是看最大值有没有过期）
同样可以用堆来解决，两者思路差不多，都是存储候选，left移动看看候选最大值有没有过期，过期让老二上。（但是复杂度跌到onlogn了）
特别注意，这里无论是队列长度还是堆长度，都跟窗口的长度无关。所以我们判断窗口是否合法，还是要用下标来判断。

十二、最小覆盖子串#

1. 题面#

76. 最小覆盖子串#

难度：困难

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

测试用例保证答案唯一。

示例 1：

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

示例 2：

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

示例 3:

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

提示：

m == s.length
n == t.length
1 <= m, n <= 10^5
s 和 t 由英文字母组成

进阶： 你能设计一个在 O(m + n) 时间内解决此问题的算法吗？

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 一眼滑动窗口，用t建立need，t的长度就是validation需要达到的量。validation达标的情况下left移动
def solution(s: str, t: str) -> str:
    need = {}
    window = {}
    # 记录need
    for c in t:
        need[c] = need.get(c, 0) + 1
    left = 0
    right = 0
    valid = 0
    start = 0
    min_len = float("inf")

    while right < len(s):
        c = s[right]
        right += 1
        # 如果在need中，再记录（不在need中的也不可能对valid产生影响，可以不管）
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1
        # 当valid满足了，left收缩
        while valid == len(need):
            if right - left < min_len:
                # 同时记录最短长度和起点
                start = left
                min_len = right - left
            # 执行对称收缩即可
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
    # 返回值进行一下inf保护
    return "" if min_len == float("inf") else s[start:start + min_len]


if __name__ == "__main__":
    s = input().strip()
    t = input().strip()
    m = len(s)
    n = len(t)
    print(solution(s,t,m,n))

3. 反思#

滑动窗口果然容易码错。虽然对称的left、right操作已经记熟了，但是仍然忘记先看need再哈希。
满足条件再收缩，收缩前就已经满足的，在收缩代码里拿答案；收缩后才合法的，在收缩完成后拿答案。两种情况取决于写的while，一定要注意分辨。

十三、最大子数组和#

1. 题面#

53. 最大子数组和#

难度：中等

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

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

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 数组里面有负数，来新元素进来不一定增大，丢弃也不一定变小
# 连续子数组，顺序无关要素（最大和），比较符合滑动窗口。
# 但这题其实的关键其实在数是不是负数。当前位置结束的最大子数组只有两种选择：重新开始只取x，或者接在前面子数组后面，变成pre+x。这其实就是动态规划的方法
# 这种求最大子数组和的问题，不用打表，可以称为Kadane 算法
def solution(nums)->int:
    cur = nums[0]
    ans = nums[0]

    for i in range(1,len(nums)):
        # 先加上这一个位置，看看是否会增大
        # 如果加上更小，不如另开（选nums[i]）
        cur = max(nums[i],cur+nums[i])
        # 维持一个最大值
        ans = max(ans,cur)
    return ans

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

3. 反思#

这题被叫做Kadane算法，他其实是一种动态规划的思想的优化简化，用于处理另起炉灶还是继续加入的选择哪个更好，然后维持一个全局的最优ans

十四、合并区间#

1. 题面#

56. 合并区间#

难度：中等

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这一题两个区间重合的条件是，new_left<=old_right且new_right>=old_left。我们可以用这个条件判断重合，如果重合，就更新左侧为min的，右侧为max的
# 用一个栈来存储，方便操作
# 但是要注意的是，要先按照左端点排序。这是最大坑点，可能传入的是以前的也能合并。左端点排完序之后new_right>=old_left就不需要了

from collections import deque

def solution(intervals:list[list[int]])->list[list[int]]:
    intervals.sort()
    ans = []
    for left,right in intervals:
        # 如果ans为空或者不用合并
        if not ans or left>ans[-1][1]:
            ans.append([left,right])
        else:
            # 否则需要合并，更新为比较大的右端点
            ans[-1][1] = max(ans[-1][1],right)
    return ans

if __name__ == "__main__":
    # 注意这里的输入，我们让每行输入两个，不定行
    intervals = []
    while True:
        try:
            interval = list(map(int,input().strip().split(',')))
            intervals.append(interval)
        except EOFError:
            break
    print(solution(intervals))

3. 反思#

这题重合需要注意可能传进去之前的，传入的左端点还不一定按时间排序，需要自己排序一下。
排序算法intervals.sort(key = lambda x0)可以简写成intervals.sort()。因为python的sort可以默认按照第一项排序。

十五、轮转数组#

1. 题面#

189. 轮转数组#

难度：中等

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

示例 1:

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

示例 2:

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

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

进阶：

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

2.题解1 - 切片#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这题直接考查python切片操作就行了
if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    k = int(input().strip())

    k = k%(len(nums))
    print(nums[-k:]+nums[:-k])

3.题解2 - 三次翻转#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 题目进阶要求是O(1)空间，那么我们需要做的其实是三次翻转
def reverse(left, right):
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    k = int(input().strip())
    
    n = len(nums)
    k = k % n
    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)
    print(nums)

4. 题解3 - 环状替换#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 最后一种方法，直接将数组想象成环来移动
# 环装替换的思路，是每个元素都会最终被放到(i+k) % n的位置，这样会形成若干个首尾相连的环，我们一直替换指导回到起点
# 需要注意的是，要维持count计算搬运了多少次，防止漏元素
def rotate(nums: list[int], k: int) -> None:
    n = len(nums)
    k %= n
    count = 0
    start = 0

    while count < n:
        current = start
        prev = nums[start]

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

            if current == start:
                break

        start += 1

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    k = int(input().strip())
    
    rotate(nums,k)
    print(nums)

5. 反思#

如果不限制空间，这题cpp也能直接建立队列做。python切片的复杂度是O(k)，会创建新列表
但是本题想考察的重点其实是你能不能写出O(1)的算法，也就是真的原地。
三次翻转是比较常规的方法，后面链表题也是这么写的。
环状替换比较绕，比较硬核，到时候有空再看看吧。

十六、除自身以外数组的乘积#

1. 题面#

238. 除了自身以外数组的乘积#

难度：中等

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

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

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

示例 1:

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

示例 2:

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

提示：

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
输入保证数组 answer[i] 在 32 位 整数范围内

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

2. 题解1 - 前缀后缀积O(n)#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 经典前缀积问题，不允许使用除法的话，那么就前缀积+后缀积就行了
def solution(nums):
    n = len(nums)
    prefix = [1]*(n+1)
    suffix = [1]*(n+1)
    ans = [0]*n
    # 构造前缀积
    for i in range(1,n+1):
        prefix[i] = nums[i-1]*prefix[i-1]
    # 构造后缀积
    for i in range(n-1,-1,-1):
        suffix[i] = nums[i]*suffix[i+1]
    # 我们构造答案，每个位置其实是i-1的前缀积乘以i+1的后缀积
    for i in range(n):
        ans[i] = prefix[i]*suffix[i+1]
    return ans

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

3. 题解2 - 空间O(1)#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 在前缀后缀的题目中，有时候并不需要使用这个数组本身，可以一遍做一边存答案，只用一个变量解决
# 本题可以用ans存前缀积，然后suffix直接算。不算答案数组可以O(1)的额外空间
def solution(nums):
    n = len(nums)
    ans = [1] * n

    # ans[i] 先保存左边乘积
    for i in range(1, n):
        ans[i] = ans[i - 1] * nums[i - 1]

    # suffix 保存右边乘积
    suffix = 1
    for i in range(n - 1, -1, -1):
        ans[i] *= suffix
        suffix *= nums[i]

    return ans


if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

4. 反思#

经典前缀后缀题，需要注意的是不常用的后缀怎么设置数组（边界问题）

十七、缺失的第一个正数#

1. 题面#

41. 缺失的第一个正数#

难度：困难

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 循环一遍建立集合，然后用最小正数往下跳就行了。但是要求常数级别的额外空间，这法子不行了。
# 这题的关键在于，“直接用下标当哈希表”。因为正整数一定是从1开始到n+1。我们只要不断交换，让数回到自己所在位置，即num应该去num-1的位置。然后再扫一遍，看每个位置对不对
def solution(nums) -> int:
    n = len(nums)

    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]

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

    return n + 1

if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print(solution(nums))

3. 反思#

这题不给你用额外的空间，但是要想到下标和数值本身是有关系的，直接用下标来对应就行了。

十八、矩阵置零#

1. 题面#

73. 矩阵置零#

难度：中等

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

示例 1：

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

示例 2：

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

提示：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

进阶：

一个直观的解决方案是使用 O(_m__n_) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(_m_ + _n_) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 我的想法是先遍历一遍，把0的行、列分别放进两个set中
# 然后再二重循环，如果i in set_i or j in set_j，就直接变0。但是这种方法不满足进阶要求，额外空间复杂度是O(m+n)。不过先把这个做出来吧
def solution(matrix:list[list[int]])->list:
    m = len(matrix)
    n = len(matrix[0])
    set_i = set()
    set_j = set()
    for i in range(m):
        for j in range(n):
            if matrix[i][j]==0:
                set_i.add(i)
                set_j.add(j)
    
    for i in range(m):
        for j in range(n):
            if i in set_i or j in set_j:
                matrix[i][j] = 0

if __name__ == "__main__":
    matrix = []
    while True:
        try:
            line = list(map(int,input().strip().split(',')))
            matrix.append(line)
        except EOFError:
            break
    solution(matrix)
    print(matrix)

3. 题解 - 常数空间#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 现在要实现常数空间做法
# 具体的做法是，拿矩阵的第一行和第一列当标记位。依旧是不用空间的话，就要利用用自身的下标。
def solution(matrix) -> None:
    m = len(matrix)
    n = len(matrix[0])

    first_row_zero = False
    first_col_zero = False

    # 判断第一行是否原本有 0
    for j in range(n):
        if matrix[0][j] == 0:
            first_row_zero = True
            break

    # 判断第一列是否原本有 0
    for i in range(m):
        if matrix[i][0] == 0:
            first_col_zero = True
            break

    # 用第一行和第一列做标记
    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

    # 最后处理第一行
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0

    # 最后处理第一列
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0


if __name__ == "__main__":
    matrix = []
    while True:
        try:
            line = list(map(int,input().strip().split(',')))
            matrix.append(line)
        except EOFError:
            break
    solution(matrix)
    print(matrix)

4. 反思#

也是限制空间，这时候一定要活用原本的结构。

十九、螺旋矩阵#

54. 螺旋矩阵#

难度：中等

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

示例 1：

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

示例 2：

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

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 螺旋路径使用经典四边界挤压
def solution(matrix):
    if not matrix or not matrix[0]:
        return []
    ans = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    # 这题最明晰的做法，就是一个大循环套四个小循环
    while top <= bottom and left <= right:
        # 左到右
        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
        # 右到左，这里要判断一下top和bottom的关系，然后才能回过头走
        if top <= bottom:
            for j in range(right, left - 1, -1):
                ans.append(matrix[bottom][j])
            bottom -= 1
        # 下到上，判断left和right的关系
        if left <= right:
            for i in range(bottom, top - 1, -1):
                ans.append(matrix[i][left])
            left += 1
    return ans

if __name__ == "__main__":
    matrix = []
    while True:
        try:
            line = list(map(int,input().strip().split(',')))
            matrix.append(line)
        except EOFError:
            break
    print(solution(matrix))

二十、旋转图像#

1. 题面#

48. 旋转图像#

难度：中等

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

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

示例 1：

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

示例 2：

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

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这一题的结论是，先沿主对角线翻转，然后再研轴翻转
def solution(matrix:list[list[int]])->None:
    # 先沿对角线翻转
    for i in range(len(matrix)):
        for j in range(i+1,len(matrix[0])):
            matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
    # 再沿中轴翻转
    for line in matrix:
        line.reverse()

if __name__ == "__main__":
    matrix = []
    while True:
        try:
            line = list(map(int,input().strip().split(',')))
            matrix.append(line)
        except EOFError:
            break
    solution(matrix)
    print(matrix)

二十一、搜索二维矩阵 II#

240. 搜索二维矩阵 II#

难度：中等

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

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

示例 1：

1
输入：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
2
输出：true

示例 2：

1
输入：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
2
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 基本做法是从右上角开始搜，如果大于target，肯定不在这一列，左移；如果小于target，直接往下搜索。
def solution(matrix, target) -> bool:
    m = len(matrix)
    n = len(matrix[0])
    i = 0
    j = n - 1

    while i < m and j >= 0:
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] > target:
            j -= 1
        else:
            i += 1

    return False


if __name__ == "__main__":
    lines= []
    while True:
        try:
            # 一次性读入
            lines.append(input().strip())
        except EOFError:
            break
    target = int(lines[-1])
    # 注意这里的提取前面行数的方法
    matrix = [list(map(int, line.split(','))) for line in lines[:-1]]
    print(solution(matrix,target))

3. 反思#

其实建议直接记住，另外注意输入的时候最后target的处理方式，即我们先拿到所有数据，然后再提取需要的量（用切片）

二十二、相交链表#

160. 相交链表#

难度：简单

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

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

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

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

自定义评测：

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

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

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

示例 1：

1
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
2
输出：Intersected at '8'
3
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
4
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
5
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
6
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

1
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
2
输出：Intersected at '2'
3
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
4
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
5
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

1
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
2
输出：No intersection
3
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
4
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
5
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶： 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这题解法倒是简单，作为第一道链表题，遍历完自己遍历别人就行，这样一定会和在相交点，如果不相交又一定会会和在None
# 主要是先熟悉一下ACM模式处理链表

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 将指针推至最后一个节点方便拼接
def get_tail(head):
    if not head:
        return None
    while head.next:
        head = head.next
    return head


def solution(headA: ListNode, headB: ListNode) -> ListNode:
    p = headA
    q = headB
    while p != q:
        p = p.next if p else headB
        q = q.next if q else headA
    return p


if __name__ == "__main__":
    # 第一行：A的独有部分
    # 第二行：B的独有部分
    # 第三行：公共尾部；如果不相交就输入空行
    partA = input().strip()
    partB = input().strip()
    common = input().strip()

    numsA = list(map(int, partA.split(','))) if partA else []
    numsB = list(map(int, partB.split(','))) if partB else []
    numsC = list(map(int, common.split(','))) if common else []

    headA = build_linked_list(numsA)
    headB = build_linked_list(numsB)
    headC = build_linked_list(numsC)

    if headC:
        tailA = get_tail(headA)
        tailB = get_tail(headB)

        if tailA:
            tailA.next = headC
        else:
            headA = headC

        if tailB:
            tailB.next = headC
        else:
            headB = headC

    ans = solution(headA, headB)
    print(ans.val if ans else 0)

3. 反思#

如果是正常做思路非常简单的，但是如果要用ACM模式做，就要熟练掌握怎么写这些额外函数、怎么建链表，貌似精力都放在这上面来了。这题没让输出链表，不然还要写一个print_linked_list函数。

二十三、反转链表#

1.题面#

206. 反转链表#

难度：简单

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

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

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 三指针法在python中非常优雅]

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(head:ListNode)->ListNode:
    prev = None
    curr = head
    # 多重赋值
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    # 三链表反转之后，prev是头结点
    return prev

if __name__ =="__main__":
    nums = list(map(int,input().strip().split(',')))
    head = build_linked_list(nums)
    head = solution(head)
    print_linked_list(head)

3. 反思#

这题多重赋值是Python最优雅的翻转链表方案，但是这一句要注意顺序问题。左边第一个目标是 curr.next，它会先把"旧 curr 的 next"改掉，然后再更新 prev 和 curr，这个顺序才是对的。

二十四、回文链表#

1. 题面#

234. 回文链表#

难度：简单

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

示例 1：

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

示例 2：

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

提示：

链表中节点数目在范围[1, 10^5] 内
0 <= Node.val <= 9

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

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 本题进阶要求O(n)时间复杂度和常数空间复杂度，思路其实很简单，就是快慢指针
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next


def solution(head:ListNode)->bool:
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 这是奇偶区分，如果是奇数（也就是fast不会走到None），那么slow要从后一个开始翻转
    if fast:
        slow = slow.next
    # 三指针翻转
    curr=slow
    prev=None
    while curr:
        curr.next,curr,prev=prev,curr.next,curr
    # 我们可以从头开始比较，如果翻转后链表跑完之前都和原链表相等，那么一定为回文
    while prev:
        if prev.val!=head.val:
            return False
        prev=prev.next
        head=head.next
    return True

if __name__ =="__main__":
    nums = list(map(int,input().strip().split(',')))
    head = build_linked_list(nums)
    print(solution(head))

3. 反思#

本题是找中点、翻转的合并。关键点在于根据fast的位置，可以判断出链表的奇偶，从而决定从什么位置开始翻转后半部分。

二十五、环形链表#

1. 题面#

141. 环形链表#

难度：简单

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

进阶： 你能用 O(1)（即，常量）内存解决此问题吗？

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 本题也是经典结论，fast走两步，slow走一步，最终如果相遇则有环
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 这里升级了一下，直接返回头指针+节点列表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    nodes = []
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
        nodes.append(cur)
    return dummy.next, nodes

def solution(head:ListNode)->bool:
    slow,fast = head,head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            return True
    return False

if __name__ == "__main__":
    nums_line = input().strip()
    pos = int(input().strip())

    # 注意这里有个判空逻辑
    nums = list(map(int, nums_line.split(','))) if nums_line else []
    head, nodes = build_linked_list(nums)

    if pos != -1 and nodes:
        nodes[-1].next = nodes[pos]

    print(solution(head))

3. 反思#

注意这题的ACM模式，在建链表的时候也建一个nodes数组，这样方便我们直接看pos的位置。

二十六、环形链表 II#

1. 题面#

142. 环形链表 II#

难度：中等

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

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

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目范围在范围 [0, 10^4] 内
-10^5 <= Node.val <= 10^5
pos 的值为 -1 或者链表中的一个有效索引

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

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 本题不仅要看有没有环，还要看环在哪
# 实际上跟上一题基本没有区别，就是相遇之后，还有拍一个新的小兵从起点出发，然后再和slow相遇，对应的节点就是返回的点。
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 这里升级了一下，直接返回头指针+节点列表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    nodes = []
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
        nodes.append(cur)
    return dummy.next, nodes

def solution(head:ListNode)->ListNode:
    slow,fast = head,head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            break
    # 派遣小兵
    start = head
    while slow !=start:
        slow = slow.next
        start = start.next
    return start

if __name__ == "__main__":
    nums_line = input().strip()
    pos = int(input().strip())

    # 注意这里有个判空逻辑
    nums = list(map(int, nums_line.split(','))) if nums_line else []
    head, nodes = build_linked_list(nums)

    if pos != -1 and nodes:
        nodes[-1].next = nodes[pos]

    print(solution(head).val)

3. 反思#

没啥好说的，记结论

二十七、合并两个有序链表#

1. 题面#

21. 合并两个有序链表#

难度：简单

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 非常经典的合并链表题，可以从穿针引线的角度考虑，用新dummy去合并

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(l1:ListNode,l2:ListNode)->ListNode:
    dummy = ListNode()
    p = dummy
    while l1 and l2:
        if l1.val>=l2.val:
            p.next = l2
            l2 =l2.next
        else:
            p.next = l1
            l1 = l1.next
        p = p.next
    if l1:
        p.next = l1
    if l2:
        p.next = l2
    return dummy.next

if __name__ == "__main__":
    nums_l1 = list(map(int,input().strip().split(',')))
    nums_l2 = list(map(int,input().strip().split(',')))
    l1 = build_linked_list(nums_l1)
    l2 = build_linked_list(nums_l2)
    head = solution(l1,l2)
    print_linked_list(head)

二十八、两数相加#

1. 题面#

2. 两数相加#

难度：中等

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这题就是竖式加法，还贴心给你逆序好了，这种板子属于必须背下来的地步

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(l1:ListNode,l2:ListNode)->ListNode:
    carry = 0
    dummy = ListNode()
    p = dummy
    while l1 or l2 or carry:
        a = l1.val if l1 else 0
        b = l2.val if l2 else 0
        total = a+b+carry
        carry = total//10
        p.next= ListNode(total%10)
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
        p = p.next
    return dummy.next

if __name__ == "__main__":
    nums_l1 = list(map(int,input().strip().split(',')))
    nums_l2 = list(map(int,input().strip().split(',')))
    l1 = build_linked_list(nums_l1)
    l2 = build_linked_list(nums_l2)
    head = solution(l1,l2)
    print_linked_list(head)

3. 反思#

依旧直接背板，一定要熟练。易错点两个，一个是l1不为空才能next，另一个是carry和total都是本轮算本轮的，千万别+=

二十九、删除链表的倒数第 N 个结点#

1.题面#

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

难度：中等

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

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

2.题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 双指针当尺子就行了
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(head:ListNode,n:int)->ListNode:
    # 有可能删除头结点，所以用dummy
    dummy = ListNode()
    dummy.next =head
    slow,fast = dummy,dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        slow = slow.next
        fast = fast.next
    # 现在slow在待删除元素前面
    slow.next= slow.next.next
    return dummy.next

if __name__ =="__main__":
    nums_line = input().strip()
    n = int(input().strip())

    # 注意这里有个判空逻辑
    nums = list(map(int, nums_line.split(','))) if nums_line else []
    head = build_linked_list(nums)
    head = solution(head,n)
    print_linked_list(head)

3. 反思#

注意点只有一个，就是删除节点要加dummy，因为头也可能被删

三十、两两交换列表中的节点#

1. 题面#

24. 两两交换链表中的节点#

难度：中等

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

2. 题解1 - 直接翻转#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这题有两种解法，一种是递归，另一种是每次记住翻转前的头结点作为tail，连上curr（curr会天然跑到下一个节点）
# 先来最直观的
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(head:ListNode)->ListNode:
    if not head or not head.next:
        return head
    dummy = ListNode()
    dummy.next = head
    list_pre = dummy
    curr = head
    while curr and curr.next:
        tail = curr
        prev = None
        # 翻转两次
        for _ in range(2):
            curr.next,curr,prev = prev,curr.next,curr
        # 接上翻转过的链表
        tail.next = curr
        list_pre.next = prev
        list_pre = tail
    return dummy.next

if __name__ =="__main__":
    nums = list(map(int,input().strip().split(',')))
    head = build_linked_list(nums)
    head = solution(head)
    print_linked_list(head)

3. 题解2 - 递归处理#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 递归的解法，我们需要假设solution函数返回的就是两两交换好的节点，所以我们只要排当前的两个，然后后面交给递归黑箱就行了
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(head:ListNode)->ListNode:
    # 同样小于两个节点的话不用找了
    if not head or not head.next:
        return head
    # 调转的时候指向黑箱递归
    new_head = head.next
    head.next = solution(new_head.next)
    new_head.next = head
    return new_head


if __name__ =="__main__":
    nums = list(map(int,input().strip().split(',')))
    head = build_linked_list(nums)
    head = solution(head)
    print_linked_list(head)

4. 反思#

这题第一种解法在解决k个翻转的时候也很给力，递归的解法最容易理解代码最简洁，都需要掌握

三十一、k个一组翻转链表#

1. 题面#

25. K 个一组翻转链表#

难度：困难

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

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

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

示例 1：

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

示例 2：

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

提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

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

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 我们先按照两个一组的解法改一下，直接做成k个一组。不同点在于我们可能需要先遍历一下，数数节点个数，这样才知道我们需要进行多少次k翻转
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(head:ListNode,k:int)->ListNode:
    dummy = ListNode()
    dummy.next = head
    ct = head
    count = 0
    while ct:
        ct = ct.next
        count += 1
    times = count//k
    # 开始times次翻转
    curr = head
    list_pre = dummy
    for _ in range(times):
        # k翻转准备工作，标记tail
        tail = curr
        prev = None
        # k翻转本题
        for _ in range(k):
            curr.next,curr,prev = prev,curr.next,curr
        # 接上节点
        list_pre.next = prev
        tail.next = curr
        # 准备下次k翻转
        list_pre = tail
    return dummy.next



if __name__ =="__main__":
    nums = list(map(int,input().strip().split(',')))
    k = int(input().strip())
    head = build_linked_list(nums)
    head = solution(head,k)
    print_linked_list(head)

3. 题解2 - 递归#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 跟上题一样，递归思路自然是最简单。先检查够不够k，不够就返回。然后进行k个翻转，将下一个连接到黑箱就行。
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(head: ListNode, k: int) -> ListNode:
    cur = head
    for _ in range(k):
        if not cur:
            return head
        cur = cur.next

    prev = None
    curr = head
    for _ in range(k):
        curr.next, curr, prev = prev, curr.next, curr

    head.next = solution(curr, k)
    return prev


if __name__ =="__main__":
    nums = list(map(int,input().strip().split(',')))
    k = int(input().strip())
    head = build_linked_list(nums)
    head = solution(head,k)
    print_linked_list(head)

4. 反思#

和上提一样，一个直接做，一个递归。直接做有助于思考三指针翻转后的指针都在哪，递归则是容易理解好做的思路。

三十二、随机链表的复制#

1. 题面#

138. 随机链表的复制#

难度：中等

给你一个长度为 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
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
2
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

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

示例 3：

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

提示：

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random 为 null 或指向链表中的节点。

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 随机链表的复制，要求还原原链表的所有指针。其实所有数据结构的复制都是一样的，先复制节点内容，再复制关系。用哈希表做一个旧对新的存储即可。
import ast


class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random


def build_random_list(data):
    if not data:
        return None

    nodes = [Node(val) for val, _ in data]

    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]

    for i, (_, random_idx) in enumerate(data):
        if random_idx is not None:
            nodes[i].random = nodes[random_idx]

    return nodes[0]


def print_random_list(head):
    nodes = []
    node_to_idx = {}
    p = head
    idx = 0
    while p:
        nodes.append(p)
        node_to_idx[p] = idx
        p = p.next
        idx += 1

    ans = []
    for node in nodes:
        random_idx = node_to_idx[node.random] if node.random else None
        ans.append([node.val, random_idx])
    print(ans)


def solution(head: Node) -> Node:
    # 不用deepcopy外挂的话，记住数据结构复制就一个哈希表+两次遍历：第一次遍历专门克隆节点，借助哈希表把原始节点和克隆节点的映射存储起来；第二次专门组装节点，照着原数据结构的样子，把克隆节点的指针组装起来
    originToClone = {}
    # 第一遍遍历，克隆节点
    p = head
    while p:
        if p not in originToClone:
            originToClone[p] = Node(p.val)
        p = p.next
    # 第二次遍历，组装节点
    p = head
    while p:
        # 克隆之孩子等于孩子之克隆
        if p.next:
            originToClone[p].next = originToClone[p.next]
        if p.random:
            originToClone[p].random = originToClone[p.random]
        p = p.next
    return originToClone.get(head)


if __name__ == "__main__":
    line = input().strip()
    data = ast.literal_eval(line.replace("null", "None")) if line else []
    head = build_random_list(data)
    head = solution(head)
    print_random_list(head)

3. 反思#

重点看solution部分，但是也可以看一下python的厉害。先用replace换成可以解析的字面量，然后用ast.literal_eval(…)，可以直接解析，将字符串形式的嵌套列表，转化为真列表。

三十三、排序链表#

1. 题面#

148. 排序链表#

难度：中等

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5

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

2. 题解1 - 数组复制#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 进阶要求是，在nlogn时间范围内完成，也就是快排。最简单能想到的是，建一个数组，排序数组，然后按数组重建链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表 + 数组
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    nodes = []
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
        nodes.append(cur.val)
    return dummy.next, nodes

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)


if __name__ =="__main__":
    nums = list(map(int,input().strip().split(',')))
    head, nodes = build_linked_list(nums)
    nodes.sort()
    head ,nodes = build_linked_list(nodes)
    print_linked_list(head)

3. 题解2 - 归并排序#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 但是，这一题可以更简化到Onlogn+logn额外栈空间，也是力扣真的想考的方法，归并排序。
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 尾插法建立链表
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)

def solution(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head

    # 快慢指针找中点，并断开链表
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None

    left = solution(head)
    right = solution(mid)

    # 合并两个有序链表
    dummy = ListNode()
    p = dummy
    while left and right:
        if left.val < right.val:
            p.next = left
            left = left.next
        else:
            p.next = right
            right = right.next
        p = p.next

    p.next = left if left else right
    return dummy.next


if __name__ =="__main__":
    nums = list(map(int,input().strip().split(',')))
    head = build_linked_list(nums)
    head = solution(head)
    print_linked_list(head)

3. 反思#

这一题想看的是解法二，解法一纯钻空子。注意这里有三步，首先设置递归出口，然后快慢指针寻找中点（注意这里的fast设置在head.next的起点，就可以自然让slow停在mid前面，不用借助dummy），最后递归排序两边。后面是标准的排序两个有序链表的过程。
然后就是力扣里面函数本身带self，记得递归的时候self.func

三十四、合并 K 个升序链表#

1. 题面#

23. 合并 K 个升序链表#

难度：困难

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

2. 题解1 - 堆排序#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 合并k个升序链表，我们可以用堆来做。将值和节点对入堆，然后每次拿出最小的让p指向。
# 还需要放一个idx，这是因为堆比完第一个相同自动比第二个。这是万万不行的，需要在二位弄一个idx保护。
import ast
import heapq
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 这里升级了一下，直接返回头指针
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)


def solution(lists: list[ListNode]) -> ListNode:
    heap = []
    dummy = ListNode()
    p = dummy

    # 建堆
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    # 弹堆，每次弹之后将弹出的节点下一个节点入堆
    while heap:
        _, i, node = heapq.heappop(heap)
        p.next = node
        p = p.next

        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next


if __name__ == "__main__":
    # 输入二维数组
    line = input().strip()
    data = ast.literal_eval(line)
    headlist = []
    for nums in data:
        headlist.append(build_linked_list(nums))
    print_linked_list(solution(headlist))

3. 题解2 - 分治#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 合并k个升序链表，我们可以用堆来做。将值和节点对入堆，然后每次拿出最小的让p指向。
# 还需要放一个idx，这是因为堆比完第一个相同自动比第二个。这是万万不行的，需要在二位弄一个idx保护。
import ast
import heapq
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 这里升级了一下，直接返回头指针
def build_linked_list(nums):
    dummy = ListNode()
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

# 打印链表
def print_linked_list(head):
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)


def merge2Lists(l1,l2):
    # 穿针引线
    dummy = ListNode(-1)
    p = dummy
    p1, p2 =l1, l2
    while p1 and p2:
        if p1.val<=p2.val:
            p.next = p1
            p1 = p1.next
        else:
            p.next = p2
            p2 = p2.next
        p = p.next

    # 看看有没有合并完毕
    p.next = p1 if p1 else p2
    return dummy.next

# 辅助函数，让List[start,end)也合并成有序链表
def mergeLists(lists,start,end):
    # 就一个表
    if start == end:
        return lists[start]
    if start > end:
        return None
    # 折半合并
    mid = (start + end) //2
    # 合并左右半边
    # 这里left包含一下mid
    left = mergeLists(lists,start,mid)
    right = mergeLists(lists,mid+1,end)
    return merge2Lists(left,right)



def mergeKLists(lists:list[ListNode]) -> ListNode:
    # 不借助优先队列，可以采用分治思想
    # 从中间切开将两边变得有序，然后再合并
    if len(lists) == 0:
        return None
    left = 0
    right = len(lists)-1
    return mergeLists(lists,left,right)


if __name__ == "__main__":
    # 输入二维数组
    line = input().strip()
    data = ast.literal_eval(line)
    headlist = []
    for nums in data:
        headlist.append(build_linked_list(nums))
    print_linked_list(mergeKLists(headlist))

4. 反思#

第一种方案是用堆自动排序，体现了堆可以存很多种不同的结果；第二种则是分治算法的体现，理解稍微复杂，实际上就是分成两边做让递归数尽可能矮。本质上也是先分两边不断递归排完left、right，然后进行两个有序链表合并的归并。

三十五、LRU缓存#

1. 题面#

146. 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
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
3
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
4
输出
5
[null, null, null, 1, null, -1, null, -1, 3, 4]
6

7
解释
8
LRUCache lRUCache = new LRUCache(2);
9
lRUCache.put(1, 1); // 缓存是 {1=1}
10
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
11
lRUCache.get(1);    // 返回 1
12
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
13
lRUCache.get(2);    // 返回 -1 (未找到)
14
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
15
lRUCache.get(1);    // 返回 -1 (未找到)
16
lRUCache.get(3);    // 返回 3
17
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
最多调用 2 * 10^5 次 get 和 put

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这题非常非常典型，实现方法是双链表+哈希表。哈希表负责快查，双向链表维持最近使用顺序。双向链表的顺序是，头部为最新使用，尾部为最久没使用。如果get就将元素移动到头部，put直接放在头部，容量超出了，就删除尾部。
# 现在，请背板
import ast


class Node:
    # 初始化双链表节点
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    # 在此基础上初始化容量、cache哈希表、头尾节点
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}

        self.dummy_head = Node()
        self.dummy_tail = Node()
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head

    def remove(self, node):
        # 双链表删除
        node.prev.next = node.next
        node.next.prev = node.prev

    # 加入最前面
    def push_front(self, node):
        node.next = self.dummy_head.next
        node.prev = self.dummy_head
        self.dummy_head.next.prev = node
        self.dummy_head.next = node

    # 访问后移动到前面
    def move_to_front(self, node):
        self.remove(node)
        self.push_front(node)

    def pop_tail(self):
        node = self.dummy_tail.prev
        self.remove(node)
        return node

    def get(self, key: int) -> int:
        # 有返回值没有返回-1
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        # 如果有，更新值
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self.move_to_front(node)
            return
        # 没有的话新建
        node = Node(key, value)
        self.cache[key] = node
        self.push_front(node)

        if len(self.cache) > self.capacity:
            removed = self.pop_tail()
            del self.cache[removed.key]


if __name__ == "__main__":
    ops = ast.literal_eval(input().strip().replace("null", "None"))
    args = ast.literal_eval(input().strip().replace("null", "None"))

    ans = []
    lru = None

    for op, arg in zip(ops, args):
        if op == "LRUCache":
            lru = LRUCache(arg[0])
            ans.append(None)
        elif op == "put":
            lru.put(arg[0], arg[1])
            ans.append(None)
        elif op == "get":
            ans.append(lru.get(arg[0]))

    print(str(ans).replace("None", "null"))

3. 反思#

这题代码看似复杂，实际上就是打一个双链表板子。

三十六、二叉树的中序遍历#

1. 题面#

94. 二叉树的中序遍历#

难度：简单

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

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

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 中序遍历的递归很简单，关键是要建立树
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root:TreeNode)->list:
    ans = []
    def inorder(node):
        if not node:
            return None
        inorder(node.left)
        ans.append(node.val)
        inorder(node.right)
    inorder(root)
    return ans

if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

3. 反思#

中序遍历不难，主要是ACM模式读取和建树。ast读取列表，replace把null换成None。
板子的易错点：层序建树要时刻用i监督是否超过data长度，打印层序的时候别忘了先判空再入队，然后就是空树的各种边界保护。

三十七、二叉树的最大深度#

1. 题面#

104. 二叉树的最大深度#

难度：简单

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

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

示例 1：

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

示例 2：

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

提示：

树中节点的数量在 [0, 10^4] 区间内。
-100 <= Node.val <= 100

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 两种方法，要么直接带着深度参数dfs，要么nonlocal一个depth不传参数，这样记得递归完成后回退-1
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root


def solution(root:TreeNode)->int:
    max_depth = 0
    def dfs(node,depth):
        nonlocal max_depth
        if not node:
            return
        max_depth = max(max_depth,depth)
        dfs(node.left,depth+1)
        dfs(node.right,depth+1)
    dfs(root,1)
    return max_depth


if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

三十八、翻转二叉树#

1. 题面#

226. 翻转二叉树#

难度：简单

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 其实可以建树的时候就先右后左。不过我们默认模版是不动的。于是我们可以dfs一下，然后有左右孩子的换一下
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root:TreeNode)->TreeNode:
    def dfs(node:TreeNode):
        if not node:
            return None
        node.left,node.right = node.right,node.left
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return root

if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    solution(root)
    print_tree(root)

3. 反思#

有时候会担心翻转之后dfs会不会乱了，或者需要调整成先right后left。其实不用，dfs只是为了遍历，即使左右换了，还是可以遍历，只不过遍历顺序变了。

三十九、对称二叉树#

1. 题面#

101. 对称二叉树#

难度：简单

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

示例 1：

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

示例 2：

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

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

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

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 因为树是递归结构，所以大多数题可以递归解。这题的解法，就是左右孩子，一个往左一个往右，一个往右一个往左，两种情况同时递归，取个and。
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root:TreeNode)->bool:
    if not root:
        return True
    # 递归用check函数，看两边
    def check(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        return check(left.left, right.right) and check(left.right, right.left)
    return check(root.left, root.right)

   

if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

3. 反思#

第一次写懵逼，第二次写想看左侧左根右和右侧右根左是否一样，样例虽然能过，但是忽略了其实一个顺序是确定不了树的。

四十、二叉树的直径#

1. 题面#

543. 二叉树的直径#

难度：简单

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

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

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

示例 1：

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

示例 2：

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

提示：

树中节点数目在范围 [1, 10^4] 内
-100 <= Node.val <= 100

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这一题递归对每个节点算左右字数深度，然后维持一个全局最大量和左右深度和对比。
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root: TreeNode) -> int:
    ans = 0

    def dfs(node: TreeNode) -> int:
        nonlocal ans
        if not node:
            return 0

        left_depth = dfs(node.left)
        right_depth = dfs(node.right)

        ans = max(ans, left_depth + right_depth)

        # 递归完返回的时候依次取比较深的一边+1
        return max(left_depth, right_depth) + 1

    dfs(root)
    return ans


if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

3. 反思#

这题有一个dfs直接计算最大深度，可以仔细看一下写法。
中间比较更新一个nonlocal量是常用的递归更新全局量。

四十一、二叉树的层序遍历#

1. 题面#

102. 二叉树的层序遍历#

难度：中等

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

2. 题解1 - 队列法#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 层序遍历非常基础，有很多种写法，我们先实现最基础的队列法
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root: TreeNode) -> int:
    ans = []
    if not root:
        return None
    q = deque([root])
    while q:
        sz = len(q)
        level = []
        for _ in range(sz):
            curr = q.popleft()
            level.append(curr.val)
            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)
        # 本层遍历结束
        ans.append(level)
    return ans

if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

3. 题解2 - dfs+depth#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 层序遍历的第二种方法，记录深度的dfs
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root: TreeNode) -> list[list[int]]:
    ans = []
    def dfs(node, depth):
        if not node:
            return
        # ans记录层数，如果depth与其相等，说明为新层（depth从0）
        if depth == len(ans):
            ans.append([])
        ans[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return ans


if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

4. 题解3 - IDDFS#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 想兼顾 DFS 省空间 和 BFS 按层扩展特性的时候，可以用IDDFS（迭代加深搜索）。思路是每次加深能搜的最深深度，然后循环DFS。
# 常用在状态搜索、博弈搜索等情况
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root: TreeNode) -> list[list[int]]:
    if not root:
        return []

    ans = []
    # 带有目标层数限制的dfs，每次取一次level
    def collect(node, depth, target, level) -> None:
        if not node:
            return
        if depth == target:
            level.append(node.val)
            return
        collect(node.left, depth + 1, target, level)
        collect(node.right, depth + 1, target, level)

    target = 0
    while True:
        level = []
        collect(root, 0, target, level)
        # 循环到没东西的时候停止
        if not level:
            break
        ans.append(level)
        target += 1

    return ans



if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

5. 反思#

这题我记得面试考过一次，不用队列BFS，所以就总结一下所有广搜的方法。

四十二、将有序数组转换为二叉搜索树#

1. 题面#

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

难度：简单

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按 严格递增 顺序排列

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这题不需要自己去构造ACL树，因为已经给了有序数组，用分治一半一半递归构造，天然就是平衡的
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 升级打印树，我们加入一个弹出None的同时也将None加入答案。然后，把尾巴多余的None弹出，得到结果。
def print_tree(root: TreeNode):
    if not root:
        print([])
        return

    ans = []
    q = deque([root])

    while q:
        node = q.popleft()
        if node is None:
            ans.append(None)
            continue
        ans.append(node.val)
        # 现在允许加入None
        q.append(node.left)
        q.append(node.right)

    while ans and ans[-1] is None:
        ans.pop()

    print(str(ans).replace("None", "null"))


# 我们给solution的定义是，返回平衡二叉树的根
def solution(nums:list)->TreeNode:
    if not nums:
        return None
    mid = len(nums)//2
    val = nums[mid]
    root = TreeNode(val)
    root.left = solution(nums[:mid])
    root.right = solution(nums[mid+1:])
    return root


if __name__ == "__main__":
    nums = list(map(int,input().strip().split(',')))
    print_tree(solution(nums))

3. 反思#

一开始以为要写ACL树，吓死我了。这一题主要注意两点，一个是两半递归的时候，切片的位置要避开root，然后mid从长度或者从长度-1开始切都是对的，正好得到的就是示例两种答案（偏左和偏右）。
另一点是这题需要打印空，升级了一下print，具体写法是不在入队前检查None，在加ans时检查None。

四十三、验证二叉搜索树#

1. 题面#

98. 验证二叉搜索树#

难度：中等

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

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

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

示例 1：

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

示例 2：

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

提示：

树中节点数目范围在[1, 10^4] 内
-2^31 <= Node.val <= 2^31 - 1

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 最标准的递归是上下界解法，因为BST要求的约束不仅在能看到的层，但看局部约束不行来递归是不行的。
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root:TreeNode)->bool:
    def dfs(node,low,high):
        if not node:
            return True
        if not (low<node.val<high):
            return False
        # 更新约束
        return dfs(node.left,low,node.val) and dfs(node.right,node.val,high)
    return dfs(root,float('-inf'),float('inf'))

if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

3. 反思#

这题易错点是容易只考虑当前父子直接递归，BST的约束是跨越整个树的，这样会漏掉跨层约束。
真正的做法是一直维持上下界，往左走要更新上界（因为左边都要小），往右走更新上界，遍历一遍全部判断。

四十四、二叉搜索树中第 K 小的元素#

1. 题面#

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

难度：中等

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

示例 1：

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

示例 2：

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

提示：

树中的节点数为 n 。
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

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

2. 题解1#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 还记得链表第k小的元素么，这里是二叉搜索树，中序就是有序排列。可以中序出数组，直接访问，这是最容易想到的。

import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root:TreeNode,k:int)->int:
    ans = []
    def dfs(node):
        if not node:
            return None
        dfs(node.left)
        ans.append(node.val)
        dfs(node.right)
    dfs(root)
    return ans[k-1]

if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    k = int(input().strip())
    root = build_tree(data)
    print(solution(root,k))

3. 题解2 - 进阶#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 进阶操作：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
# 这个要求我们就不能打出表了，因为二叉树时刻变动，重复打表很麻烦。
# 这题的标准做法是添加一个属性

import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root: TreeNode, k: int) -> int:
    # 给节点动态加属性
    # 递归方式，给每个节点加一个维持子树大小属性
    def build_size(node: TreeNode) -> int:
        if not node:
            return 0
        left_size = build_size(node.left)
        right_size = build_size(node.right)
        node.size = left_size + right_size + 1
        return node.size

    # 有了子树大小这个属性，就可以一直看左边的size来遍历，如果左边找k-1
    # 注意切换到右边寻找的时候，要给左侧全部剪掉（因为左侧都比右侧小），去找k-left_size-1
    def kth(node: TreeNode, k: int) -> int:
        left_size = node.left.size if node.left else 0

        if k == left_size + 1:
            return node.val
        if k <= left_size:
            return kth(node.left, k)
        return kth(node.right, k - left_size - 1)

    build_size(root)
    return kth(root, k)


if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    k = int(input().strip())
    root = build_tree(data)
    print(solution(root,k))

4. 反思#

进阶方法运用了python动态绑定属性的方法，很巧妙。

四十五、二叉树的右视图#

1. 题面#

199. 二叉树的右视图#

难度：中等

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

示例 1：

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

输出： [1,3,4]

解释：

示例 2：

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

输出：[1,3,4,5]

解释：

示例 3：

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

输出： [1,3]

示例 4：

**输入：**root = []

输出： []

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 最容易想到的就是层序遍历，然后每次让找到当前层的最右侧
import ast
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印树
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        ans.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(ans)


def solution(root:TreeNode)->list:
    ans = []
    if not root:
        return []
    q = deque([root])
    while q:
        sz = len(q)
        ans.append(q[-1].val)
        for _ in range(sz):
            curr = q.popleft()
            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)
    return ans

if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

四十六、二叉树展开为链表#

1. 题面#

114. 二叉树展开为链表#

难度：中等

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

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

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 先来一般解法，直接按结构新建链表
import ast
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印加强
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        if not node:
            ans.append(None)
            continue
        ans.append(node.val)
        q.append(node.left)
        q.append(node.right)
        
    while ans and ans[-1] is None:
        ans.pop()

    print(str(ans).replace("None", "null"))


def solution(root:TreeNode)->TreeNode:
    if not root:
        return None
    dummy = TreeNode()
    dummy.right = root
    p = dummy
    def dfs(node):
        nonlocal p
        if not node:
            return None
        # 先序穿针
        p.right = TreeNode(node.val)
        p = p.right
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return dummy.right
    


if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print_tree(solution(root))

3. 题解 - 进阶#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 进阶要求是O(1)就地展开，做法就是将每个节点的左子树都接到右边。
# 具体来说，如果节点有左子树，先找左子树最右节点，然后把原右子树接到这个最右节点后面，最后左子树整体移动到右边，左边清空。可以脑内模拟一下这个过程。
import ast
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印加强
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        if not node:
            ans.append(None)
            continue
        ans.append(node.val)
        q.append(node.left)
        q.append(node.right)
        
    while ans and ans[-1] is None:
        ans.pop()

    print(str(ans).replace("None", "null"))


def solution(root: TreeNode) -> TreeNode:
    p = root
    while p:
        if p.left:
            # 找到左子树最右边的节点
            pre = p.left
            while pre.right:
                pre = pre.right

            # 原来的右子树接到左子树最右节点后面
            pre.right = p.right

            # 左子树挪到右边
            p.right = p.left
            p.left = None
        # 然后一直沿着right走
        p = p.right

    return root

    


if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print_tree(solution(root))

4. 反思#

第二种原地结果比较难想，多看看板子。

四十七、从前序与中序遍历序列构造二叉树#

1. 题面#

105. 从前序与中序遍历序列构造二叉树#

难度：中等

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

示例 1:

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

示例 2:

1
输入: preorder = [-1], inorder = [-1]
2
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 从前序和中序构建二叉树，用手来做比较简单，写代码容易绕进去。
# 方法是将preorder作为根的列表，切分成left和right，然后递归下去，传进去新的两半数组和根。

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 打印升级
def print_tree(root:TreeNode):
    # 也就是层序遍历
    ans = []
    if not root:
        print([])
        return
    q = deque([root])
    while q:
        node = q.popleft()
        if not node:
            ans.append(None)
            continue
        ans.append(node.val)
        q.append(node.left)
        q.append(node.right)

    while ans[-1] == None:
        ans.pop()

    result = str(ans).replace("None","null")

    print(result)


def solution(preorder:list,inorder:list) -> TreeNode:
    if not preorder or not inorder:
        return None
    # 1. 定位根节点
    root_val = preorder[0]
    root = TreeNode(root_val)
    # 2. 定位分界线
    mid_idx = inorder.index(root_val)
    # 3. 切片挂子树
    # 注意计算一下左右子树的长度
    root.left = solution(
        preorder[1:1+mid_idx],
        inorder[:mid_idx]
    )
    root.right = solution(
        preorder[1+mid_idx:],
        inorder[mid_idx+1:]
    )
    return root

if __name__ == "__main__":
    preorder = list(map(int,input().strip().split(',')))
    inorder = list(map(int,input().strip().split(',')))
    print_tree(solution(preorder,inorder))

3. 反思#

这题的难点在切片的位置判断，需要多练习。

四十八、路径总和 III#

1. 题面#

437. 路径总和 III#

难度：中等

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

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

示例 1：

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

示例 2：

1
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
2
输出：3

提示:

二叉树的节点个数的范围是 [0,1000]
-10^9 <= Node.val <= 10^9
-1000 <= targetSum <= 1000

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 直接朴素递归，一句话，每个节点都试一遍
# 直接朴素递归，一句话，每个节点都试一遍

import ast

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root


def solution(root: TreeNode, targetSum: int) -> int:
    # 统计从当前节点出发的合法路径数
    def count_from(node: TreeNode, target: int) -> int:
        if not node:
            return 0

        # 只包含节点自己
        count = 1 if node.val == target else 0
        # 当前节点 + 左边继续往下
        count += count_from(node.left, target - node.val)
        # 当前节点 + 右边继续往下
        count += count_from(node.right, target - node.val)
        return count

    if not root:
        return 0

    # solution是统计整棵树的，等于当前根出发的+左右子树的
    return (
        count_from(root, targetSum)
        + solution(root.left, targetSum)
        + solution(root.right, targetSum)
    )



if __name__ == "__main__":
    data = input().strip().replace("null","None")
    targetSum = int(input().strip())
    nums = ast.literal_eval(data)
    root = build_tree(nums)
    print(solution(root,targetSum))

3. 反思#

这题好难，得用两个递归。首先是找从这个节点开始，递归找有没有路径。然后递归每个节点加上当前和左右的路径和。能自己写出这题的递归已经对树的递归非常熟练了。

四十九、二叉树的最近公共祖先#

1. 题面#

236. 二叉树的最近公共祖先#

难度：中等

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

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

示例 1：

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

示例 2：

1
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
2
输出：5
3
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

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

提示：

树中节点数目在范围 [2, 10^5] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

2. 题解 - parent属性#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 我们给节点添加parent属性，然后让标记的p、q同时往上，找到空之后再从头开始。按照相交链表的结论，最后一定会在交点（共同祖先）相遇，如果没有共同祖先，也会在None相遇。
import ast

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root


def solution(root: TreeNode, p: int, q: int) -> TreeNode:
    # 指针思维
    node_p = None
    node_q = None
    def build_parent(node: TreeNode, parent: TreeNode):
        nonlocal node_p, node_q
        if not node:
            return
        node.parent = parent
        # 顺便找到p、q
        if node.val == p:
            node_p = node
        if node.val == q:
            node_q = node
        build_parent(node.left, node)
        build_parent(node.right, node)
    build_parent(root, None)
    a, b = node_p, node_q
    while a != b:
        a = a.parent if a else node_q
        b = b.parent if b else node_p
    return a

    
if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    p = int(input().strip())
    q = int(input().strip())
    root = build_tree(data)
    ans = solution(root, p, q)
    print(ans.val)

3. 题解2 - 递归#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 如果用树的思维来做，就要先想到从递归写。这题的做法是经典的LCA算法，请熟练掌握这个。
import ast

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root

# 我们用solution(root,p,q)表示以root为根的这颗子树中，p、q的最近公共祖先
def solution(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    # 找到目标节点或者找到空了先往上交
    if not root or root == p or root == q:
        return root
    # 递归左右子树
    left = solution(root.left, p, q)
    right = solution(root.right, p, q)
    # 如果左右都返回了非空值，也就是都找到了，那root就是第一次汇合的地方
    if left and right:
        return root
    # 如果只有一边非空，则将自己上交，继续往上找祖先
    return left if left else right


    
if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    p = int(input().strip())
    q = int(input().strip())
    root = build_tree(data)
    ans = solution(root, p, q)
    print(ans.val)

3. 反思#

这题第二种LCA算法是最优雅的解法，请记住板子。

五十、二叉树中的最大路径和#

1. 题面#

124. 二叉树中的最大路径和#

难度：困难

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

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

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

示例 1：

1
输入：root = [1,2,3]
2
输出：6
3
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

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

提示：

树中节点数目范围是 [1, 3 * 10^4]
-1000 <= Node.val <= 1000

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这题根二叉树直径的题有点像，不确定起点，不确定是否经过根。
import ast

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 从列表创建树
def build_tree(data:list):
    # 空返回
    if not data or data[0] is None:
        return None
    
    root = TreeNode(data[0])
    q = deque([root])
    # 除去根，从1开始
    i = 1

    # 正常的列表其实是层序遍历顺序给出，所有用层序来建树即可，维持一个i随时监控有没有超过长度。
    while q and i<len(data):
        node = q.popleft()

        if i <len(data) and data[i] is not None:
            node.left = TreeNode(data[i])
            q.append(node.left)
        i += 1

        if i<len(data) and data[i] is not None:
            node.right = TreeNode(data[i])
            q.append(node.right)
        i += 1
    return root


def solution(root: TreeNode) -> int:
    ans = float("-inf")
    # dfs记录当前节点往下走的一条最大贡献路径
    # ans记录当前节点作为拐点时的最大路径和
    def dfs(node: TreeNode) -> int:
        nonlocal ans
        if not node:
            return 0

        # 依旧变形递归，
        left_gain = max(dfs(node.left), 0)
        right_gain = max(dfs(node.right), 0)

        # 最大路径和可能正好在当前节点这里左右连起来
        ans = max(ans, node.val + left_gain + right_gain)
        return node.val + max(left_gain, right_gain)

    dfs(root)
    return ans

  
if __name__ == "__main__":
    data = ast.literal_eval(input().strip().replace("null", "None"))
    root = build_tree(data)
    print(solution(root))

3. 反思#

我草，好难，暂时不看，回头理解背板

五十一、岛屿数量#

1. 题面#

200. 岛屿数量#

难度：中等

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

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

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

示例 1：

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

示例 2：

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

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 虽然是图论的第一题，但是和建图没关系，可以直接用输入的矩阵当图本身。
# dfs本身可以用来找连通图的个数，只要用外面循环调用dfs就行。这题思路很简单。
import ast


def solution(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    ans = 0

    def dfs(i: int, j: int) -> None:
        # 走到水里或越界
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != "1":
            return

        # dfs各种走四个方向
        grid[i][j] = "0"
        dfs(i - 1, j)
        dfs(i + 1, j)
        dfs(i, j - 1)
        dfs(i, j + 1)

    # 找到一块陆地，就dfs把附近的路都水淹掉（标记为0）
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "1":
                ans += 1
                dfs(i, j)

    return ans


if __name__ == "__main__":
    grid = ast.literal_eval(input().strip())
    print(solution(grid))

3. 反思#

dfs在图里的经典用法

五十二、腐烂的橘子#

1. 题面#

994. 腐烂的橘子#

难度：1433

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

1
输入：grid = [[0,2]]
2
输出：0
3
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 用手画出来这个过程倒是很简单，二重遍历+更新time编，就是有点担心会不会太慢了
import ast
from collections import deque

def solution(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    q = deque()
    fresh = 0

    # 先把所有腐烂橘子入队，同时统计新鲜橘子数量
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                q.append((i, j))
            elif grid[i][j] == 1:
                fresh += 1

    minutes = 0
    # 预定义四个方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while q and fresh > 0:
        for _ in range(len(q)):
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # python判断坐标合法的方法
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    fresh -= 1
                    q.append((nx, ny))
        minutes += 1

    return minutes if fresh == 0 else -1


    
if __name__ == "__main__":
    grid = ast.literal_eval(input().strip())
    print(solution(grid))

3. 反思#

这种题看起来思路简单，但是比较考验你的写法和边界条件，建议平时多敲练习。

五十三、课程表#

1. 题面#

207. 课程表#

难度：中等

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

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# 这一题是经典的有向图判环，我们用队列实现拓扑排序
import ast
from collections import deque

def solution(numCourses: int, prerequisites: list[list[int]]) -> bool:
    # 简历邻接表
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses

    # 建图：b -> a，表示学a之前要先学b
    for a, b in prerequisites:
        graph[b].append(a)
        # 维持一个入度，给后面拓扑排序用
        indegree[a] += 1

    # 开始拓扑排序，先将入度为0加入，然后一层一层剥
    q = deque()
    for i in range(numCourses):
        if indegree[i] == 0:
            q.append(i)

    count = 0
    while q:
        course = q.popleft()
        count += 1

        # 如果去掉孩子的入度全减1，如果变成入度0就入队
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    # 如果所有数都出去了，说明无环
    return count == numCourses

if __name__ == "__main__":
    numCourses = int(input().strip())
    prerequisites = ast.literal_eval(input().strip())
    print(solution(numCourses,prerequisites))

3. 反思#

拓扑排序给有向图判环是经典算法。

五十四、实现 Trie (前缀树)#

1. 题面#

208. 实现 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
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
3
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
4
输出
5
[null, null, true, false, true, null, true]
6

7
解释
8
Trie trie = new Trie();
9
trie.insert("apple");
10
trie.search("apple");   // 返回 True
11
trie.search("app");     // 返回 False
12
trie.startsWith("app"); // 返回 True
13
trie.insert("app");
14
trie.search("app");     // 返回 True

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * 10^4 次

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码

# Trie树是一种空间换时间极致的结构
import ast


class Trie:
    # 内部类：定义 Trie 树的每一个最小单元（节点）
    class TrieNode:
        def __init__(self):
            # 因为题目说只有小写英文字母，所以固定开 26 个分叉的数组即可。
            # 下标 0 代表 'a'，下标 25 代表 'z'
            self.children = [None] * 26
            # 核心灵魂：标记从根节点一路顺着树枝走到这里，是不是构成了一个完整的单词
            self.is_end = False

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

    def insert(self, word: str) -> None:
        # 指针 p 从树根出发，准备顺着树干往下爬
        p = self.root
        for char in word:
            # 计算当前字母应该进 26 个分叉里的哪一个通道
            idx = ord(char) - ord('a')
            # 如果通往这个字母的“通道（树枝）”还不存在，就现搭一根树枝（新建节点）
            if not p.children[idx]:
                p.children[idx] = self.TrieNode()
            # 顺着这条刚搭好、或者早就有的树枝，大步往下走一层！
            p = p.children[idx]
        
        # 单词全部走完了（此时 p 停在这个单词的最后一个字母上）
        # 插上一面旗子：宣告这里是一个合法单词的终点！
        p.is_end = True

    def search(self, word: str) -> bool:
        p = self.root
        for char in word:
            idx = ord(char) - ord('a')
            # 如果走着走着发现没路了（通道是 None），说明字典里压根没存过这串字母，果断返回 False
            if not p.children[idx]:
                return False
            p = p.children[idx]
            
        # 走到底了，路是通的。但它到底是用我的这串字母结尾的单词，还是只是一部分前缀？
        # 全靠我们当时插下的那面旗帜 `is_end` 说了算！
        return p.is_end

    def startsWith(self, prefix: str) -> bool:
        p = self.root
        for char in prefix:
            idx = ord(char) - ord('a')
            # 同样，走不通说明连前缀都没有
            if not p.children[idx]:
                return False
            p = p.children[idx]
            
        # 前缀和 search 唯一的区别：只要路能通，不管走到最后有没有插红旗，前缀都是存在的！
        return True


if __name__ == "__main__":
    ops = ast.literal_eval(input().strip().replace("null", "None"))
    args = ast.literal_eval(input().strip().replace("null", "None"))

    ans = []
    trie = None

    for op, arg in zip(ops, args):
        if op == "Trie":
            trie = Trie()
            ans.append(None)
        elif op == "insert":
            trie.insert(arg[0])
            ans.append(None)
        elif op == "search":
            ans.append(trie.search(arg[0]))
        elif op == "startsWith":
            ans.append(trie.startsWith(arg[0]))

    print(str(ans).replace("None", "null").replace("True", "true").replace("False", "false"))

3. 反思#

记住思路了背板很简单

五十五、全排列#

1. 题面#

46. 全排列#

难度：中等

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

2. 题解#

Frozen Editor 默认折叠，点击展开查看完整代码

展开代码