Algorithm practice notes
按官方 Hot100 分组整理题意摘要、解题分析、复杂度和 Python 3 代码。重点不是背答案，而是把每题归到可复用的算法模式。
Hot100 覆盖哈希、指针、窗口、链表、树、图、回溯、二分、栈、堆、贪心和 DP。每题都按“题目、样例、分析、解法、复杂度”组织，代码默认使用 LeetCode Python 3 环境。
先按主题刷题，遇到卡点时展开题目规格与题目分析；写完代码后对照复杂度和边界条件。题目规格基于官方题面改写，完整原题以每题“官方题目”链接为准。
当前显示 100 / 100 题
本组 3 题，围绕 哈希 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：给定一个整数数组和目标值，找出两个不同位置的数，使它们的和等于目标值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.twoSum(...)，输入参数为 nums（List[int]）、target（int）。
输出：返回 List[int]；返回值含义是：给定一个整数数组和目标值，找出两个不同位置的数，使它们的和等于目标值。
nums = [2,7,11,15], target = 9[0,1]说明：该输入按题意计算后得到上述输出。
nums = [3,2,4], target = 6[1,2]说明：该输入按题意计算后得到上述输出。
关键是把“找另一个数”变成哈希表查询。遍历到 x 时，只要 target - x 已经出现，就立即得到答案；否则记录 x 的下标。因为题目要求不同位置，必须先查再写入当前数。
维护 value -> index，当前元素只负责匹配之前出现过的补数。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
# 先查再存，避免同一个元素被用两次
seen[x] = i
return []复杂度：时间 O(n)，空间 O(n)。
官方题意（改写）：把一组字符串按字母异位词分组：字符种类和次数完全相同的字符串放在一起。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.groupAnagrams(...)，输入参数为 strs（List[str]）。
输出：返回 List[List[str]]；返回值含义是：把一组字符串按字母异位词分组：字符种类和次数完全相同的字符串放在一起。
strs = ["eat", "tea", "tan", "ate", "nat", "bat"][["bat"],["nat","tan"],["ate","eat","tea"]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
strs = [""][[""]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
异位词的顺序不同，但排序后的字符序列相同。也可以用 26 维计数元组作为 key，避免排序成本。这里使用计数元组，适合全小写字母。
每个字符串转成长度 26 的 tuple，tuple 可哈希，能唯一表示字母频次。
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord('a')] += 1
groups[tuple(cnt)].append(s)
return list(groups.values())复杂度：时间 O(nk)，空间 O(nk)。
官方题意（改写）：在未排序数组中，求最长连续整数序列的长度。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.longestConsecutive(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：在未排序数组中，求最长连续整数序列的长度。
nums = [100,4,200,1,3,2]4说明：该输入按题意计算后得到上述输出。
nums = [0,3,7,2,5,8,4,6,0,1]9说明：该输入按题意计算后得到上述输出。
不能排序后求解，否则是 O(n log n)。把所有数字放进 set，只从没有前驱 x-1 的数字开始扩展，这样每个连续段只被扫描一次。
x-1 不存在时，x 才是某段起点；从起点向右计数。
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
values = set(nums)
best = 0
for x in values:
if x - 1 in values:
continue
y = x
while y in values:
y += 1
best = max(best, y - x)
return best复杂度：时间 O(n)，空间 O(n)。
本组 4 题，围绕 双指针 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：把数组中的 0 移到末尾，同时保持非零元素的相对顺序。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.moveZeroes(...)，输入参数为 nums（List[int]）。
输出：函数原地修改输入对象，不需要返回新对象；修改后的数据应满足：把数组中的 0 移到末尾，同时保持非零元素的相对顺序。
nums = [0,1,0,3,12][1,3,12,0,0]说明：该输入按题意计算后得到上述输出。
nums = [0][0]说明：该输入按题意计算后得到上述输出。
用 slow 指向下一个应该放非零元素的位置。扫描到非零值就和 slow 交换，然后 slow 前进。交换写法能原地完成。
前半段始终维护为已处理的非零元素序列。
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
slow = 0
for fast, x in enumerate(nums):
if x != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：给定每个位置的高度，选择两条竖线和 x 轴组成容器，使盛水面积最大。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.maxArea(...)，输入参数为 height（List[int]）。
输出：返回 int；返回值含义是：给定每个位置的高度，选择两条竖线和 x 轴组成容器，使盛水面积最大。
[1,8,6,2,5,4,8,3,7]49说明：该输入按题意计算后得到上述输出。
height = [1,1]1说明：该输入按题意计算后得到上述输出。
面积由较短边决定。左右指针从两端开始，若移动较高边，宽度变小且短板不变或更差，不可能更优；因此每次移动较短边。
每轮计算面积，然后丢弃当前较短的边。
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
best = max(best, h * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1
return best复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：找出数组中所有不重复的三元组，使三数之和为 0。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.threeSum(...)，输入参数为 nums（List[int]）。
输出：返回 List[List[int]]；返回值含义是：找出数组中所有不重复的三元组，使三数之和为 0。
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
nums = [0,1,1][]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
先排序，固定第一个数后，剩余问题变成有序数组两数之和。去重发生在固定数和双指针移动时，否则会输出重复三元组。
固定 i，left/right 根据 sum 与 0 的关系移动。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
if nums[i] > 0:
break
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
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
elif s < 0:
left += 1
else:
right -= 1
return ans复杂度：时间 O(n^2)，空间 O(1) 不计输出。
官方题意（改写）：给定柱状高度，计算下雨后能接住的总水量。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.trap(...)，输入参数为 height（List[int]）。
输出：返回 int；返回值含义是：给定柱状高度，计算下雨后能接住的总水量。
height = [0,1,0,2,1,0,1,3,2,1,2,1]6说明：该输入按题意计算后得到上述输出。
height = [4,2,0,3,2,5]9说明：该输入按题意计算后得到上述输出。
某位置水量由左右最高柱的较小值决定。双指针维护 left_max/right_max，哪边最高上界更低，就能确定那边当前位置的水量。
较低一侧的水位已被另一侧保证，直接结算。
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water复杂度：时间 O(n)，空间 O(1)。
本组 2 题，围绕 滑动窗口 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：求字符串中不含重复字符的最长连续子串长度。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.lengthOfLongestSubstring(...)，输入参数为 s（str）。
输出：返回 int；返回值含义是：求字符串中不含重复字符的最长连续子串长度。
s = "abcabcbb"3说明：该输入按题意计算后得到上述输出。
s = "bbbbb"1说明：该输入按题意计算后得到上述输出。
滑动窗口维护当前无重复区间。记录字符上次出现位置，遇到重复且位置在窗口内，就把左边界移动到重复字符后一位。
left 永不回退，窗口始终无重复。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return best复杂度：时间 O(n)，空间 O(字符集大小)。
官方题意（改写）：在字符串 s 中找出所有与 p 互为字母异位词的子串起始下标。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.findAnagrams(...)，输入参数为 s（str）、p（str）。
输出：返回 List[int]；返回值含义是：在字符串 s 中找出所有与 p 互为字母异位词的子串起始下标。
s = "cbaebabacd", p = "abc"[0,6]说明：该输入按题意计算后得到上述输出。
s = "abab", p = "ab"[0,1,2]说明：该输入按题意计算后得到上述输出。
窗口长度固定为 len(p)。维护窗口字符计数和目标计数，每次右扩并在长度超出时左缩，计数相同即命中。
窗口大小固定后，只需比较字符频次。
from collections import Counter
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
need = Counter(p)
window = Counter()
ans = []
m = len(p)
for right, ch in enumerate(s):
window[ch] += 1
if right >= m:
left_ch = s[right - m]
window[left_ch] -= 1
if window[left_ch] == 0:
del window[left_ch]
if window == need:
ans.append(right - m + 1)
return ans复杂度：时间 O(n * 字符集)；小写字母可视为 O(n)，空间 O(字符集)。
本组 3 题，围绕 子串 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：统计和等于 k 的连续子数组数量。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.subarraySum(...)，输入参数为 nums（List[int]）、k（int）。
输出：返回 int；返回值含义是：统计和等于 k 的连续子数组数量。
nums = [1,1,1], k = 22说明：该输入按题意计算后得到上述输出。
nums = [1,2,3], k = 32说明：该输入按题意计算后得到上述输出。
令 prefix[i] 为前 i 个数之和。若 prefix[j] - prefix[i] = k，则 prefix[i] = prefix[j] - k。遍历右端点时，查询之前出现过多少个目标前缀和。
把连续区间和转化为两个前缀和之差。
from collections import defaultdict
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = defaultdict(int)
count[0] = 1
prefix = 0
ans = 0
for x in nums:
prefix += x
ans += count[prefix - k]
count[prefix] += 1
return ans复杂度：时间 O(n)，空间 O(n)。
官方题意（改写）：给定窗口大小 k，输出每个滑动窗口中的最大值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.maxSlidingWindow(...)，输入参数为 nums（List[int]）、k（int）。
输出：返回 List[int]；返回值含义是：给定窗口大小 k，输出每个滑动窗口中的最大值。
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]说明：该输入按题意计算后得到上述输出。
nums = [1], k = 1[1]说明：该输入按题意计算后得到上述输出。
单调队列存下标，队首始终是当前窗口最大值下标。新元素进入时，弹出队尾所有不大于它的元素，因为这些元素之后不可能再成为最大值。
队列按值递减、按下标递增，队首过期时弹出。
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq = deque()
ans = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
ans.append(nums[dq[0]])
return ans复杂度：时间 O(n)，空间 O(k)。
官方题意（改写）：在 s 中找出包含 t 所有字符及其次数的最短连续子串。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.minWindow(...)，输入参数为 s（str）、t（str）。
输出：返回 str；返回值含义是：在 s 中找出包含 t 所有字符及其次数的最短连续子串。
s = "ADOBECODEBANC", t = "ABC""BANC"说明：该输入按题意计算后得到上述输出。
s = "a", t = "a""a"说明：该输入按题意计算后得到上述输出。
右指针扩张直到窗口满足需求，再移动左指针尽量缩短。用 formed 记录已经满足频次的字符种类数，避免每次全量比较。
满足后立刻收缩，收缩到刚好不满足前的窗口就是候选答案。
from collections import Counter, defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
window = defaultdict(int)
required = len(need)
formed = 0
left = 0
best_len = float('inf')
best = (0, 0)
for right, ch in enumerate(s):
window[ch] += 1
if ch in need and window[ch] == need[ch]:
formed += 1
while formed == required:
if right - left + 1 < best_len:
best_len = right - left + 1
best = (left, right + 1)
out = s[left]
window[out] -= 1
if out in need and window[out] < need[out]:
formed -= 1
left += 1
return '' if best_len == float('inf') else s[best[0]:best[1]]复杂度：时间 O(|s| + |t|)，空间 O(字符集)。
本组 5 题，围绕 普通数组 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：求数组中和最大的连续子数组。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.maxSubArray(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：求数组中和最大的连续子数组。
nums = [-2,1,-3,4,-1,2,1,-5,4]6说明：该输入按题意计算后得到上述输出。
nums = [1]1说明：该输入按题意计算后得到上述输出。
Kadane 算法维护“以当前位置结尾的最大子数组和”。如果之前的和为负，就不如从当前元素重新开始。
local 表示必须以当前元素结尾的最优值，best 表示全局最优。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
local = best = nums[0]
for x in nums[1:]:
local = max(x, local + x)
best = max(best, local)
return best复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：合并所有重叠区间，返回互不重叠的区间集合。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.merge(...)，输入参数为 intervals（List[List[int]]）。
输出：返回 List[List[int]]；返回值含义是：合并所有重叠区间，返回互不重叠的区间集合。
intervals = [[1,3],[2,6],[8,10],[15,18]][[1,6],[8,10],[15,18]]说明：该输入按题意计算后得到上述输出。
intervals = [[1,4],[4,5]][[1,5]]说明：该输入按题意计算后得到上述输出。
先按左端点排序。当前区间与结果末尾区间重叠时更新右端点，否则开启新区间。
排序保证只需和最后一个已合并区间比较。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
ans = []
for start, end in intervals:
if not ans or start > ans[-1][1]:
ans.append([start, end])
else:
ans[-1][1] = max(ans[-1][1], end)
return ans复杂度：时间 O(n log n)，空间 O(n) 输出空间。
官方题意（改写）：将数组向右轮转 k 个位置，要求原地修改。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.rotate(...)，输入参数为 nums（List[int]）、k（int）。
输出：函数原地修改输入对象，不需要返回新对象；修改后的数据应满足：将数组向右轮转 k 个位置，要求原地修改。
nums = [1,2,3,4,5,6,7], k = 3[5,6,7,1,2,3,4]说明：该输入按题意计算后得到上述输出。
nums = [-1,-100,3,99], k = 2[3,99,-1,-100]说明：该输入按题意计算后得到上述输出。
右轮转可以拆成三次反转：整体反转后，前 k 个元素和后 n-k 个元素各自反转，就恢复各段内部顺序。
先让目标后缀来到前面，再修正两个分段内部顺序。
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k %= n
def reverse(l: int, r: int) -> None:
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：返回数组中每个位置除自身外所有元素的乘积，不能使用除法。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.productExceptSelf(...)，输入参数为 nums（List[int]）。
输出：返回 List[int]；返回值含义是：返回数组中每个位置除自身外所有元素的乘积，不能使用除法。
nums = [1,2,3,4][24,12,8,6]说明：该输入按题意计算后得到上述输出。
nums = [-1,1,0,-3,3][0,0,9,0,0]说明：该输入按题意计算后得到上述输出。
每个答案等于左侧乘积乘以右侧乘积。先把前缀乘积写入答案，再从右向左累乘后缀。
输出数组复用为前缀结果，后缀只需一个变量。
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n
prefix = 1
for i in range(n):
ans[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
ans[i] *= suffix
suffix *= nums[i]
return ans复杂度：时间 O(n)，空间 O(1) 不计输出。
官方题意（改写）：在未排序整数数组中找出最小缺失正整数，要求线性时间和常数额外空间。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.firstMissingPositive(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：在未排序整数数组中找出最小缺失正整数，要求线性时间和常数额外空间。
nums = [1,2,0]3说明：该输入按题意计算后得到上述输出。
nums = [3,4,-1,1]2说明：该输入按题意计算后得到上述输出。
答案一定在 1..n+1。把值 x 放到下标 x-1 的位置，最后第一个 nums[i] != i+1 的位置就是缺失值。
通过交换让每个合法正整数尽量回到自己的槽位。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i, x in enumerate(nums):
if x != i + 1:
return i + 1
return n + 1复杂度：时间 O(n)，空间 O(1)。
本组 4 题，围绕 矩阵 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：若矩阵某个元素为 0，则把它所在行和列都置为 0，要求原地完成。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.setZeroes(...)，输入参数为 matrix（List[List[int]]）。
输出：函数原地修改输入对象，不需要返回新对象；修改后的数据应满足：若矩阵某个元素为 0，则把它所在行和列都置为 0，要求原地完成。
matrix = [[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,0,1]]说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]][[0,0,0,0],[0,4,5,0],[0,3,1,0]]说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
用第一行和第一列作为标记数组。由于它们本身也可能需要清零，先额外记录第一列是否需要清零，第一行可通过 matrix[0][0] 表示。
先标记，再根据标记清内部，最后处理首行首列。
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 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复杂度：时间 O(mn)，空间 O(1)。
官方题意（改写）：按顺时针螺旋顺序返回矩阵中的所有元素。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.spiralOrder(...)，输入参数为 matrix（List[List[int]]）。
输出：返回 List[int]；返回值含义是：按顺时针螺旋顺序返回矩阵中的所有元素。
matrix = [[1,2,3],[4,5,6],[7,8,9]][1,2,3,6,9,8,7,4,5]说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]][1,2,3,4,8,12,11,10,9,5,6,7]说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
维护上、下、左、右四个边界，每走完一条边就收缩对应边界。每次收缩后都要检查边界是否仍合法。
按右、下、左、上的顺序逐层剥离矩阵。
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
ans = []
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
if top <= bottom:
for j in range(right, left - 1, -1):
ans.append(matrix[bottom][j])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1):
ans.append(matrix[i][left])
left += 1
return ans复杂度：时间 O(mn)，空间 O(1) 不计输出。
官方题意（改写）：将 n x n 矩阵顺时针旋转 90 度，要求原地修改。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.rotate(...)，输入参数为 matrix（List[List[int]]）。
输出：函数原地修改输入对象，不需要返回新对象；修改后的数据应满足：将 n x n 矩阵顺时针旋转 90 度，要求原地修改。
matrix = [[1,2,3],[4,5,6],[7,8,9]][[7,4,1],[8,5,2],[9,6,3]]说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]][[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
顺时针旋转可以分解为先沿主对角线转置，再反转每一行。这样每个元素移动到正确位置。
matrix[i][j] 与 matrix[j][i] 交换后，再水平镜像。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
row.reverse()复杂度：时间 O(n^2)，空间 O(1)。
官方题意（改写）：在每行每列都递增的矩阵中查找目标值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.searchMatrix(...)，输入参数为 matrix（List[List[int]]）、target（int）。
输出：返回 bool；返回值含义是：在每行每列都递增的矩阵中查找目标值。
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 = 5true说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
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 = 20false说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
从右上角开始：当前值大于目标时只能向左变小，小于目标时只能向下变大。每步排除一行或一列。
利用二维有序性，单步排除一个方向。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
x = matrix[row][col]
if x == target:
return True
if x > target:
col -= 1
else:
row += 1
return False复杂度：时间 O(m+n)，空间 O(1)。
本组 14 题，围绕 链表 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：找出两个单链表开始相交的节点；相交指的是节点对象相同，不是值相同。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.getIntersectionNode(...)，输入参数为 headA（ListNode）、headB（ListNode）。
输出：返回 Optional[ListNode]；返回值含义是：找出两个单链表开始相交的节点；相交指的是节点对象相同，不是值相同。
intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3Intersected at '8'说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1Intersected at '2'说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
两个指针分别从 A、B 出发，走到尾后切换到另一条链。若有交点，二者会在走过相同总长度后相遇；若无交点，都会走到 None。
A+B 与 B+A 总长度相同，自动抵消长度差。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p, q = headA, headB
while p is not q:
p = p.next if p else headB
q = q.next if q else headA
return p复杂度：时间 O(m+n)，空间 O(1)。
官方题意（改写）：反转单链表并返回新的头节点。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.reverseList(...)，输入参数为 head（Optional[ListNode]）。
输出：返回 Optional[ListNode]；返回值含义是：反转单链表并返回新的头节点。
head = [1,2,3,4,5][5,4,3,2,1]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [1,2][2,1]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
迭代写法维护 prev 和 cur，每次暂存 next 后把 cur.next 指回 prev。递归写法先反转后半段，再让当前节点接到后半段尾部。
prev 始终是已经反转好的前缀头。
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev复杂度：时间 O(n)，空间 O(1)。
递归返回新头，再把当前节点挂到后继节点之后。
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_head复杂度：时间 O(n)，空间 O(n) 递归栈。
官方题意（改写）：判断单链表的节点值是否构成回文序列。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.isPalindrome(...)，输入参数为 head（Optional[ListNode]）。
输出：返回 bool；返回值含义是：判断单链表的节点值是否构成回文序列。
head = [1,2,2,1]true说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [1,2]false说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
快慢指针找到中点，反转后半段，然后逐个比较前半段和后半段。若需要保持链表，可比较后再反转恢复。
把链表问题转成两段同步扫描。
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev, cur = None, slow
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：判断链表中是否存在环。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.hasCycle(...)，输入参数为 head（Optional[ListNode]）。
输出：返回 bool；返回值含义是：判断链表中是否存在环。
head = [3,2,0,-4], pos = 1true说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [1,2], pos = 0true说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
快慢指针同时走，slow 一次一步、fast 一次两步。如果有环，fast 会在环内追上 slow；如果无环，fast 会到达 None。
速度差为 1，在有限环内必然相遇。
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：若链表有环，返回环的入口节点；否则返回 None。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.detectCycle(...)，输入参数为 head（Optional[ListNode]）。
输出：返回 Optional[ListNode]；返回值含义是：若链表有环，返回环的入口节点；否则返回 None。
head = [3,2,0,-4], pos = 1返回索引为 1 的链表节点说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [1,2], pos = 0返回索引为 0 的链表节点说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
快慢指针相遇后，让一个指针回到头节点，两个指针都一次一步，它们再次相遇处就是入环点。这来自链表头到入口距离与相遇点到入口距离的模环长关系。
先判相遇，再用同速指针对齐入口。
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p = head
while p is not slow:
p = p.next
slow = slow.next
return p
return None复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：合并两个升序链表，返回合并后的升序链表。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.mergeTwoLists(...)，输入参数为 list1（Optional[ListNode]）、list2（Optional[ListNode]）。
输出：返回 Optional[ListNode]；返回值含义是：合并两个升序链表，返回合并后的升序链表。
l1 = [1,2,4], l2 = [1,3,4][1,1,2,3,4,4]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
l1 = [], l2 = [][]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
使用 dummy 节点简化头节点处理。每次取两个链表头部较小者接到结果尾部，最后接上剩余部分。
tail 始终指向结果链表最后一个节点。
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 or list2
return dummy.next复杂度：时间 O(m+n)，空间 O(1)。
官方题意（改写）：两个非空链表按逆序存储非负整数，返回它们相加后的逆序链表。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.addTwoNumbers(...)，输入参数为 l1（Optional[ListNode]）、l2（Optional[ListNode]）。
输出：返回 Optional[ListNode]；返回值含义是：两个非空链表按逆序存储非负整数，返回它们相加后的逆序链表。
l1 = [2,4,3], l2 = [5,6,4][7,0,8]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
l1 = [0], l2 = [0][0]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
从低位到高位同步相加，用 carry 保存进位。只要任一链表未结束或还有进位，就继续生成节点。
链表天然从最低位开始，正好模拟竖式加法。
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
carry = 0
while l1 or l2 or carry:
total = carry
if l1:
total += l1.val
l1 = l1.next
if l2:
total += l2.val
l2 = l2.next
carry, digit = divmod(total, 10)
tail.next = ListNode(digit)
tail = tail.next
return dummy.next复杂度：时间 O(max(m,n))，空间 O(max(m,n)) 输出空间。
官方题意（改写）：删除链表倒数第 n 个节点，并返回头节点。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.removeNthFromEnd(...)，输入参数为 head（Optional[ListNode]）、n（int）。
输出：返回 Optional[ListNode]；返回值含义是：删除链表倒数第 n 个节点，并返回头节点。
head = [1,2,3,4,5], n = 2[1,2,3,5]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [1], n = 1[]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
使用 dummy 处理删除头节点的情况。快指针先走 n+1 步，保持 fast 和 slow 间隔 n 个节点；fast 到尾时 slow.next 就是待删节点。
dummy 让“删除第一个节点”与普通删除统一。
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：两两交换链表中的相邻节点，不能只交换节点值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.swapPairs(...)，输入参数为 head（Optional[ListNode]）。
输出：返回 Optional[ListNode]；返回值含义是：两两交换链表中的相邻节点，不能只交换节点值。
head = [1,2,3,4][2,1,4,3]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [][]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
每轮处理 prev 后面的两个节点 a、b，把 prev -> a -> b -> next 改成 prev -> b -> a -> next，再让 prev 移到 a。
dummy + prev 让每组交换都使用同一套指针操作。
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
while prev.next and prev.next.next:
a = prev.next
b = a.next
a.next = b.next
b.next = a
prev.next = b
prev = a
return dummy.next复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：每 k 个节点一组反转链表，不足 k 个节点的尾部保持原样。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.reverseKGroup(...)，输入参数为 head（Optional[ListNode]）、k（int）。
输出：返回 Optional[ListNode]；返回值含义是：每 k 个节点一组反转链表，不足 k 个节点的尾部保持原样。
head = [1,2,3,4,5], k = 2[2,1,4,3,5]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [1,2,3,4,5], k = 3[3,2,1,4,5]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
先检查当前组是否有 k 个节点。若有，原地反转这 k 个节点，再把前一组尾部接到反转后的头，当前组原头变为新尾。
每组反转前先找到 kth，避免错误反转不足 k 的尾部。
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
group_prev = dummy
while True:
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next
group_next = kth.next
prev, cur = group_next, group_prev.next
while cur is not group_next:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
new_tail = group_prev.next
group_prev.next = kth
group_prev = new_tail复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：复制一个带 next 和 random 指针的链表，返回深拷贝后的头节点。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.copyRandomList(...)，输入参数为 head（'Optional[Node]'）。
输出：返回 'Optional[Node]'；返回值含义是：复制一个带 next 和 random 指针的链表，返回深拷贝后的头节点。
head = [[7,null],[13,0],[11,4],[10,2],[1,0]][[7,null],[13,0],[11,4],[10,2],[1,0]]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [[1,1],[2,1]][[1,1],[2,1]]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
哈希表可以记录原节点到新节点的映射。先创建所有节点，再第二遍连接 next/random。也可以原地穿插节点来做到 O(1) 额外空间。
random 指针可能指向任意节点，先建立完整映射最直接。
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
mp = {}
cur = head
while cur:
mp[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
mp[cur].next = mp.get(cur.next)
mp[cur].random = mp.get(cur.random)
cur = cur.next
return mp[head]复杂度：时间 O(n)，空间 O(n)。
官方题意（改写）：在 O(n log n) 时间内对链表进行排序。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.sortList(...)，输入参数为 head（Optional[ListNode]）。
输出：返回 Optional[ListNode]；返回值含义是：在 O(n log n) 时间内对链表进行排序。
head = [4,2,1,3][1,2,3,4]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
head = [-1,5,3,4,0][-1,0,3,4,5]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
链表适合归并排序。用快慢指针切成两半，递归排序后再按有序链表合并。
找中点断链，分别排序，再合并两个有序链表。
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[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 = self.sortList(head)
right = self.sortList(mid)
return self.merge(left, right)
def merge(self, a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
while a and b:
if a.val <= b.val:
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next
tail.next = a or b
return dummy.next复杂度：时间 O(n log n)，空间 O(log n) 递归栈。
官方题意（改写）：合并 k 个升序链表，返回一个升序链表。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.mergeKLists(...)，输入参数为 lists（List[Optional[ListNode]]）。
输出：返回 Optional[ListNode]；返回值含义是：合并 k 个升序链表，返回一个升序链表。
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
lists = [][]说明：链表用数组展示节点值，输出表示返回链表的序列化结果。
小根堆维护每条链表当前头节点。每次弹出最小节点接到结果后，把该节点的 next 放回堆。
堆中最多保留 k 个候选头节点，用序号打破值相同的比较。
import heapq
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
tail = dummy
while heap:
_, i, node = heapq.heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next复杂度：时间 O(N log k)，空间 O(k)。
官方题意（改写）：设计 LRU 缓存，支持 get 和 put，容量满时淘汰最近最少使用的键。 完整原题、样例和英文表述以本题官方链接为准。
输入：设计类 LRUCache，判题器会按照官方操作序列调用构造器和公开方法。
输出：每次查询方法返回题目要求的布尔值、整数或浮点数；更新类方法只改变对象内部状态。核心目标是：设计 LRU 缓存，支持 get 和 put，容量满时淘汰最近最少使用的键。
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]][null, null, null, 1, null, -1, null, -1, 3, 4]说明：按操作序列依次执行；构造器和无返回值操作在输出中记为 null。
Python 的 OrderedDict 可以同时维护 key 查找和访问顺序。每次 get/put 命中后把 key 移到末尾；容量超限时弹出开头的最旧项。
字典负责 O(1) 查找，双向链表顺序由 OrderedDict 内部维护。
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key: int) -> int:
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key: int, value: int) -> None:
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False)复杂度：时间 get/put 均摊 O(1)，空间 O(capacity)。
本组 15 题，围绕 二叉树 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：返回二叉树的中序遍历结果。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.inorderTraversal(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 List[int]；返回值含义是：返回二叉树的中序遍历结果。
root = [1,null,2,3][1,3,2]说明：二叉树按层序数组表示，null 表示空子节点。
root = [][]说明：二叉树按层序数组表示，null 表示空子节点。
中序遍历顺序是左、根、右。递归最简洁；迭代版用栈模拟递归路径。
一路压入左链，弹出节点访问后转向右子树。
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
ans.append(cur.val)
cur = cur.right
return ans复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：求二叉树的最大深度。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.maxDepth(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 int；返回值含义是：求二叉树的最大深度。
root = [3,9,20,null,null,15,7]3说明：二叉树按层序数组表示，null 表示空子节点。
root = [1,null,2]2说明：二叉树按层序数组表示，null 表示空子节点。
树的最大深度等于左右子树最大深度的较大值加 1。空节点深度为 0。
后序返回子树高度。
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：翻转二叉树，使每个节点的左右子树交换。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.invertTree(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 Optional[TreeNode]；返回值含义是：翻转二叉树，使每个节点的左右子树交换。
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]说明：二叉树按层序数组表示，null 表示空子节点。
root = [2,1,3][2,3,1]说明：二叉树按层序数组表示，null 表示空子节点。
对每个节点交换 left/right，然后递归处理新的左右子树。前序或后序都可以。
局部交换对每个节点独立成立。
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：判断二叉树是否关于中心轴镜像对称。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.isSymmetric(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 bool；返回值含义是：判断二叉树是否关于中心轴镜像对称。
root = [1,2,2,3,4,4,3]true说明：二叉树按层序数组表示，null 表示空子节点。
root = [1,2,2,null,3,null,3]false说明：二叉树按层序数组表示，null 表示空子节点。
对称不是左右子树相等，而是左子树的左节点对应右子树的右节点，左子树的右节点对应右子树的左节点。
比较两个节点是否互为镜像。
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def mirror(a, b):
if not a or not b:
return a is b
return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
return mirror(root.left, root.right) if root else True复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：求二叉树任意两个节点之间最长路径的边数。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.diameterOfBinaryTree(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 int；返回值含义是：求二叉树任意两个节点之间最长路径的边数。
root = [1,2,3,4,5]3说明：二叉树按层序数组表示，null 表示空子节点。
root = [1,2]1说明：二叉树按层序数组表示，null 表示空子节点。
经过某个节点的最长路径等于左子树高度加右子树高度。后序遍历返回高度，同时更新全局最大直径。
每个节点作为路径最高拐点被计算一次。
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
best = 0
def depth(node):
nonlocal best
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
best = max(best, left + right)
return 1 + max(left, right)
depth(root)
return best复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：按层从上到下返回二叉树节点值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.levelOrder(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 List[List[int]]；返回值含义是：按层从上到下返回二叉树节点值。
root = [3,9,20,null,null,15,7][[3],[9,20],[15,7]]说明：二叉树按层序数组表示，null 表示空子节点。
root = [1][[1]]说明：二叉树按层序数组表示，null 表示空子节点。
广度优先搜索天然按层访问。每轮固定当前队列长度，正好是一层的节点数。
用 level_size 把队列中的当前层与下一层分开。
from collections import deque
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
ans = []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(level)
return ans复杂度：时间 O(n)，空间 O(w)。
官方题意（改写）：把升序数组转换为高度平衡二叉搜索树。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.sortedArrayToBST(...)，输入参数为 nums（List[int]）。
输出：返回 Optional[TreeNode]；返回值含义是：把升序数组转换为高度平衡二叉搜索树。
nums = [-10,-3,0,5,9][0,-3,9,-10,null,5]说明：该输入按题意计算后得到上述输出。
nums = [1,3][3,1]说明：该输入按题意计算后得到上述输出。
平衡要求左右子树节点数尽量接近，因此每次取中点作为根，左右区间递归构造。
有序数组中点天然满足 BST 的左右大小关系。
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def build(l, r):
if l > r:
return None
mid = (l + r) // 2
root = TreeNode(nums[mid])
root.left = build(l, mid - 1)
root.right = build(mid + 1, r)
return root
return build(0, len(nums) - 1)复杂度：时间 O(n)，空间 O(log n)。
官方题意（改写）：判断一棵二叉树是否是合法二叉搜索树。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.isValidBST(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 bool；返回值含义是：判断一棵二叉树是否是合法二叉搜索树。
root = [2,1,3]true说明：二叉树按层序数组表示，null 表示空子节点。
root = [5,1,4,null,null,3,6]false说明：二叉树按层序数组表示，null 表示空子节点。
不能只比较父子节点；每个节点都必须落在祖先限定出的开区间内。递归传递 lower/upper 边界即可。
左子树上界是当前值，右子树下界是当前值。
class Solution:
def isValidBST(self, root: Optional[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'))复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：返回二叉搜索树中第 k 小的节点值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.kthSmallest(...)，输入参数为 root（Optional[TreeNode]）、k（int）。
输出：返回 int；返回值含义是：返回二叉搜索树中第 k 小的节点值。
root = [3,1,4,null,2], k = 11说明：二叉树按层序数组表示，null 表示空子节点。
root = [5,3,6,2,4,null,null,1], k = 33说明：二叉树按层序数组表示，null 表示空子节点。
BST 的中序遍历是升序序列。迭代中序遍历时，第 k 次弹出的节点就是答案。
不必遍历完整棵树，数到第 k 个即可返回。
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
k -= 1
if k == 0:
return cur.val
cur = cur.right复杂度：时间 O(h+k)，空间 O(h)。
官方题意（改写）：返回从右侧观察二叉树时每一层能看到的节点值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.rightSideView(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 List[int]；返回值含义是：返回从右侧观察二叉树时每一层能看到的节点值。
root = [1,2,3,null,5,null,4][1,3,4]说明：二叉树按层序数组表示，null 表示空子节点。
root = [1,2,3,4,null,null,null,5][1,3,4,5]说明：二叉树按层序数组表示，null 表示空子节点。
层序遍历时，每层最后一个节点就是右视图节点；也可以 DFS 优先访问右子树并记录每层第一个节点。
每层循环结束前最后弹出的节点代表该层最右侧。
from collections import deque
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
q = deque([root])
ans = []
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if i == size - 1:
ans.append(node.val)
return ans复杂度：时间 O(n)，空间 O(w)。
官方题意（改写）：把二叉树原地展开为先序遍历顺序的单链表，使用 right 指针连接。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.flatten(...)，输入参数为 root（Optional[TreeNode]）。
输出：函数原地修改输入对象，不需要返回新对象；修改后的数据应满足：把二叉树原地展开为先序遍历顺序的单链表，使用 right 指针连接。
root = [1,2,5,3,4,null,6][1,null,2,null,3,null,4,null,5,null,6]说明：二叉树按层序数组表示，null 表示空子节点。
root = [][]说明：二叉树按层序数组表示，null 表示空子节点。
后序递归先展开左右子树，再把左链插到右链前面。也可以用前序遍历栈模拟。
返回子树展开后的尾节点，便于父节点连接。
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
def dfs(node):
if not node:
return None
left_tail = dfs(node.left)
right_tail = dfs(node.right)
if left_tail:
left_tail.right = node.right
node.right = node.left
node.left = None
return right_tail or left_tail or node
dfs(root)复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：根据前序遍历和中序遍历构造二叉树。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.buildTree(...)，输入参数为 preorder（List[int]）、inorder（List[int]）。
输出：返回 Optional[TreeNode]；返回值含义是：根据前序遍历和中序遍历构造二叉树。
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7][3,9,20,null,null,15,7]说明：该输入按题意计算后得到上述输出。
preorder = [-1], inorder = [-1][-1]说明：该输入按题意计算后得到上述输出。
前序第一个值是根。根在中序中的位置把左右子树分开。用哈希表记录中序位置，递归时只传区间，避免切片。
pre_idx 按前序顺序消费根节点。
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
pos = {v: i for i, v in enumerate(inorder)}
pre_idx = 0
def build(l, r):
nonlocal pre_idx
if l > r:
return None
root_val = preorder[pre_idx]
pre_idx += 1
root = TreeNode(root_val)
mid = pos[root_val]
root.left = build(l, mid - 1)
root.right = build(mid + 1, r)
return root
return build(0, len(inorder) - 1)复杂度：时间 O(n)，空间 O(n)。
官方题意（改写）：统计二叉树中路径和等于 targetSum 的路径数量；路径必须向下，但不一定从根开始。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.pathSum(...)，输入参数为 root（Optional[TreeNode]）、targetSum（int）。
输出：返回 int；返回值含义是：统计二叉树中路径和等于 targetSum 的路径数量；路径必须向下，但不一定从根开始。
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 83说明：二叉树按层序数组表示，null 表示空子节点。
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 223说明：二叉树按层序数组表示，null 表示空子节点。
从根到当前节点的前缀和为 cur。若之前存在前缀和 cur-target，则中间这段路径和为 target。DFS 进入节点时加入当前前缀，回溯离开时撤销。
把任意向下路径和转化为两段根路径前缀和之差。
from collections import defaultdict
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
count = defaultdict(int)
count[0] = 1
ans = 0
def dfs(node, cur):
nonlocal ans
if not node:
return
cur += node.val
ans += count[cur - targetSum]
count[cur] += 1
dfs(node.left, cur)
dfs(node.right, cur)
count[cur] -= 1
dfs(root, 0)
return ans复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：在普通二叉树中寻找两个给定节点的最近公共祖先。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.lowestCommonAncestor(...)，输入参数为 root（'TreeNode'）、p（'TreeNode'）、q（'TreeNode'）。
输出：返回 'TreeNode'；返回值含义是：在普通二叉树中寻找两个给定节点的最近公共祖先。
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 13说明：二叉树按层序数组表示，null 表示空子节点。
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 45说明：二叉树按层序数组表示，null 表示空子节点。
递归搜索左右子树。如果当前节点是 p/q，返回当前节点；如果左右子树都找到目标，当前节点就是 LCA；否则返回非空的一侧。
左右两侧同时命中时，当前节点是最深汇合点。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root is p or root is q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right复杂度：时间 O(n)，空间 O(h)。
官方题意（改写）：求二叉树中任意非空路径的最大节点值之和，路径不必经过根。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.maxPathSum(...)，输入参数为 root（Optional[TreeNode]）。
输出：返回 int；返回值含义是：求二叉树中任意非空路径的最大节点值之和，路径不必经过根。
root = [1,2,3]6说明：二叉树按层序数组表示，null 表示空子节点。
root = [-10,9,20,null,null,15,7]42说明：二叉树按层序数组表示，null 表示空子节点。
对父节点可贡献的只能是一条向下单链，因此返回 max(0, node.val + max(left_gain, right_gain))。但以当前节点为拐点的答案可同时使用左右贡献。
返回给父节点的是单边最大增益，更新答案时可用双边。
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
best = float('-inf')
def gain(node):
nonlocal best
if not node:
return 0
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
best = max(best, node.val + left + right)
return node.val + max(left, right)
gain(root)
return best复杂度：时间 O(n)，空间 O(h)。
本组 4 题，围绕 图论 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：给定由 0/1 组成的网格，统计岛屿数量；上下左右相邻的陆地属于同一岛。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.numIslands(...)，输入参数为 grid（List[List[str]]）。
输出：返回 int；返回值含义是：给定由 0/1 组成的网格，统计岛屿数量；上下左右相邻的陆地属于同一岛。
grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ]1说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]3说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
扫描网格，遇到未访问陆地就启动 DFS/BFS，把整座岛标记为水或 visited，岛屿数加一。
一次搜索消去一个连通块。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '0'
dfs(i + 1, j); dfs(i - 1, j)
dfs(i, j + 1); dfs(i, j - 1)
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
ans += 1
dfs(i, j)
return ans复杂度：时间 O(mn)，空间 O(mn) 最坏递归栈。
官方题意（改写）：网格中腐烂橘子每分钟感染相邻新鲜橘子，求腐烂全部新鲜橘子的最短时间。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.orangesRotting(...)，输入参数为 grid（List[List[int]]）。
输出：返回 int；返回值含义是：网格中腐烂橘子每分钟感染相邻新鲜橘子，求腐烂全部新鲜橘子的最短时间。
grid = [[2,1,1],[1,1,0],[0,1,1]]4说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
grid = [[2,1,1],[0,1,1],[1,0,1]]-1说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
多源 BFS：所有初始腐烂橘子同时入队，每层代表一分钟。记录新鲜橘子数量，BFS 后若仍有新鲜则返回 -1。
一开始所有腐烂橘子都是同一时间层的源点。
from collections import deque
class Solution:
def orangesRotting(self, 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
dirs = [(1,0), (-1,0), (0,1), (0,-1)]
while q and fresh:
for _ in range(len(q)):
i, j = q.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 2
fresh -= 1
q.append((ni, nj))
minutes += 1
return minutes if fresh == 0 else -1复杂度：时间 O(mn)，空间 O(mn)。
官方题意（改写）：给定课程先修关系，判断是否能完成所有课程。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.canFinish(...)，输入参数为 numCourses（int）、prerequisites（List[List[int]]）。
输出：返回 bool；返回值含义是：给定课程先修关系，判断是否能完成所有课程。
numCourses = 2, prerequisites = [[1,0]]true说明：该输入按题意计算后得到上述输出。
numCourses = 2, prerequisites = [[1,0],[0,1]]false说明：该输入按题意计算后得到上述输出。
这是有向图判环。用入度表做拓扑排序，能弹出所有节点说明无环；若剩余节点无法入队，则存在循环依赖。
每学完一门入度为 0 的课，就减少它指向课程的入度。
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
indeg = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indeg[a] += 1
q = deque(i for i in range(numCourses) if indeg[i] == 0)
learned = 0
while q:
cur = q.popleft()
learned += 1
for nxt in graph[cur]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return learned == numCourses复杂度：时间 O(V+E)，空间 O(V+E)。
官方题意（改写）：实现前缀树，支持插入单词、查询完整单词和查询前缀。 完整原题、样例和英文表述以本题官方链接为准。
输入：设计类 TrieNode，判题器会按照官方操作序列调用构造器和公开方法。
输出：每次查询方法返回题目要求的布尔值、整数或浮点数；更新类方法只改变对象内部状态。核心目标是：实现前缀树，支持插入单词、查询完整单词和查询前缀。
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]][null, null, true, false, true, null, true]说明：按操作序列依次执行；构造器和无返回值操作在输出中记为 null。
Trie 的每条边代表一个字符。从根沿字符逐步创建或查找节点，终止标记用于区分完整单词和仅作为前缀出现的路径。
children 存后续字符，end 标记单词结束。
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.end = True
def search(self, word: str) -> bool:
node = self._find(word)
return bool(node and node.end)
def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not None
def _find(self, s: str):
node = self.root
for ch in s:
if ch not in node.children:
return None
node = node.children[ch]
return node复杂度：时间 每次操作 O(L)，空间 O(总字符数)。
本组 8 题，围绕 回溯 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：返回数组中所有元素的全排列。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.permute(...)，输入参数为 nums（List[int]）。
输出：返回 List[List[int]]；返回值含义是：返回数组中所有元素的全排列。
nums = [1,2,3][[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
nums = [0,1][[0,1],[1,0]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
回溯维护当前路径 path 和 used 标记。路径长度达到 n 时得到一个排列；递归退出时撤销选择。
每层选择一个还没放入 path 的数。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ans, path = [], []
used = [False] * len(nums)
def dfs():
if len(path) == len(nums):
ans.append(path[:])
return
for i, x in enumerate(nums):
if used[i]:
continue
used[i] = True
path.append(x)
dfs()
path.pop()
used[i] = False
dfs()
return ans复杂度：时间 O(n * n!)，空间 O(n)。
官方题意（改写）：返回数组所有可能子集。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.subsets(...)，输入参数为 nums（List[int]）。
输出：返回 List[List[int]]；返回值含义是：返回数组所有可能子集。
nums = [1,2,3][[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
nums = [0][[],[0]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
子集问题每个元素有选或不选两种状态。可以在每个递归节点记录当前 path，再继续选择后面的元素。
从 start 往后选择，天然避免重复顺序。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans, path = [], []
def dfs(start):
ans.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return ans复杂度：时间 O(n * 2^n)，空间 O(n)。
官方题意（改写）：给定数字字符串，返回它能映射出的所有字母组合。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.letterCombinations(...)，输入参数为 digits（str）。
输出：返回 List[str]；返回值含义是：给定数字字符串，返回它能映射出的所有字母组合。
digits = "23"["ad","ae","af","bd","be","bf","cd","ce","cf"]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
digits = "2"["a","b","c"]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
每一位数字对应一组选项。回溯按位置选择字符，位置走到末尾时得到一个组合。
第 idx 层只处理 digits[idx] 的候选字母。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
mp = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
ans, path = [], []
def dfs(idx):
if idx == len(digits):
ans.append(''.join(path))
return
for ch in mp[digits[idx]]:
path.append(ch)
dfs(idx + 1)
path.pop()
dfs(0)
return ans复杂度：时间 O(4^n)，空间 O(n)。
官方题意（改写）：从候选数中选择若干数使和等于 target，同一个数可以重复使用。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.combinationSum(...)，输入参数为 candidates（List[int]）、target（int）。
输出：返回 List[List[int]]；返回值含义是：从候选数中选择若干数使和等于 target，同一个数可以重复使用。
candidates = [2,3,6,7], target = 7[[2,2,3],[7]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
candidates = [2,3,5], target = 8[[2,2,2,2],[2,3,3],[3,5]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
排序后回溯。参数 start 保证组合按非降序生成，避免排列重复；选择 candidates[i] 后递归仍从 i 开始，因为可以重复使用。
剩余目标小于当前数时后面更大，可以停止循环。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
ans, path = [], []
def dfs(start, remain):
if remain == 0:
ans.append(path[:])
return
for i in range(start, len(candidates)):
x = candidates[i]
if x > remain:
break
path.append(x)
dfs(i, remain - x)
path.pop()
dfs(0, target)
return ans复杂度：时间 指数级，取决于 target 和候选数，空间 O(target/min(candidates))。
官方题意（改写）：生成所有由 n 对括号组成的合法括号序列。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.generateParenthesis(...)，输入参数为 n（int）。
输出：返回 List[str]；返回值含义是：生成所有由 n 对括号组成的合法括号序列。
n = 3["((()))","(()())","(())()","()(())","()()()"]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
n = 1["()"]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
任何前缀中右括号数量不能超过左括号。回溯维护已用 left/right 数量，左括号未满可放左括号，右括号少于左括号时可放右括号。
只生成始终可能合法的前缀。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans, path = [], []
def dfs(left, right):
if len(path) == 2 * n:
ans.append(''.join(path))
return
if left < n:
path.append('(')
dfs(left + 1, right)
path.pop()
if right < left:
path.append(')')
dfs(left, right + 1)
path.pop()
dfs(0, 0)
return ans复杂度：时间 O(C_n * n)，空间 O(n)。
官方题意（改写）：判断单词是否可以由网格中上下左右相邻的字符组成，同一格不能重复使用。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.exist(...)，输入参数为 board（List[List[str]]）、word（str）。
输出：返回 bool；返回值含义是：判断单词是否可以由网格中上下左右相邻的字符组成，同一格不能重复使用。
board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"true说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"true说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
从每个匹配首字母的格子开始 DFS。访问过的格子临时标记，递归结束后恢复，以支持其他路径使用。
idx 表示当前要匹配 word[idx]，访问标记防止重复用格子。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(i, j, idx):
if idx == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[idx]:
return False
tmp = board[i][j]
board[i][j] = '#'
ok = (dfs(i + 1, j, idx + 1) or dfs(i - 1, j, idx + 1) or
dfs(i, j + 1, idx + 1) or dfs(i, j - 1, idx + 1))
board[i][j] = tmp
return ok
return any(dfs(i, j, 0) for i in range(m) for j in range(n))复杂度：时间 O(mn * 3^L)，空间 O(L)。
官方题意（改写）：把字符串切分成若干子串，要求每个子串都是回文，返回所有切分方案。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.partition(...)，输入参数为 s（str）。
输出：返回 List[List[str]]；返回值含义是：把字符串切分成若干子串，要求每个子串都是回文，返回所有切分方案。
s = "aab"[["a","a","b"],["aa","b"]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
s = "a"[["a"]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
先预处理 is_pal[i][j] 表示 s[i:j+1] 是否回文，再回溯枚举每个切分终点。预处理能避免重复判断子串。
每层从 start 开始选择一个回文前缀。
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
is_pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
is_pal[i][j] = s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1])
ans, path = [], []
def dfs(start):
if start == n:
ans.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end + 1])
dfs(end + 1)
path.pop()
dfs(0)
return ans复杂度：时间 O(n^2 + n * 2^n)，空间 O(n^2)。
官方题意（改写）：在 n x n 棋盘放置 n 个皇后，使任意两个皇后都不能互相攻击。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.solveNQueens(...)，输入参数为 n（int）。
输出：返回 List[List[str]]；返回值含义是：在 n x n 棋盘放置 n 个皇后，使任意两个皇后都不能互相攻击。
n = 4[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
n = 1[["Q"]]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
按行放皇后。列、主对角线 r-c、副对角线 r+c 分别用集合记录占用，确保每次选择合法位置。
每行放一个皇后，冲突检查 O(1)。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
cols, diag1, diag2 = set(), set(), set()
board = [['.'] * n for _ in range(n)]
def dfs(r):
if r == n:
ans.append([''.join(row) for row in board])
return
for c in range(n):
if c in cols or r - c in diag1 or r + c in diag2:
continue
cols.add(c); diag1.add(r - c); diag2.add(r + c)
board[r][c] = 'Q'
dfs(r + 1)
board[r][c] = '.'
cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
dfs(0)
return ans复杂度：时间 O(n!) 量级，空间 O(n)。
本组 6 题，围绕 二分查找 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：在升序数组中查找目标值，若不存在则返回它应插入的位置。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.searchInsert(...)，输入参数为 nums（List[int]）、target（int）。
输出：返回 int；返回值含义是：在升序数组中查找目标值，若不存在则返回它应插入的位置。
nums = [1,3,5,6], target = 52说明：该输入按题意计算后得到上述输出。
nums = [1,3,5,6], target = 21说明：该输入按题意计算后得到上述输出。
这就是 lower_bound：找第一个大于等于 target 的下标。循环维护答案在 [left, right] 内，结束时 left 即插入点。
nums[mid] >= target 时答案不在 mid 右侧。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left复杂度：时间 O(log n)，空间 O(1)。
官方题意（改写）：在行内递增且每行首元素大于上一行尾元素的矩阵中查找目标值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.searchMatrix(...)，输入参数为 matrix（List[List[int]]）、target（int）。
输出：返回 bool；返回值含义是：在行内递增且每行首元素大于上一行尾元素的矩阵中查找目标值。
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3true说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13false说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
整个矩阵可以视为长度 m*n 的一维升序数组，下标 idx 映射到 matrix[idx//n][idx%n]。
不真正展开矩阵，只做下标映射。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = (left + right) // 2
x = matrix[mid // n][mid % n]
if x == target:
return True
if x < target:
left = mid + 1
else:
right = mid - 1
return False复杂度：时间 O(log(mn))，空间 O(1)。
官方题意（改写）：在升序数组中找到目标值出现的第一个和最后一个位置。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.searchRange(...)，输入参数为 nums（List[int]）、target（int）。
输出：返回 List[int]；返回值含义是：在升序数组中找到目标值出现的第一个和最后一个位置。
nums = [5,7,7,8,8,10], target = 8[3,4]说明：该输入按题意计算后得到上述输出。
nums = [5,7,7,8,8,10], target = 6[-1,-1]说明：该输入按题意计算后得到上述输出。
分别用 lower_bound 找第一个 >= target 的位置，以及第一个 >= target+1 的位置。右边界等于第二个位置减 1。
把闭区间终点转换为下一个值的左边界。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def lower_bound(x):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] >= x:
right = mid
else:
left = mid + 1
return left
left = lower_bound(target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = lower_bound(target + 1) - 1
return [left, right]复杂度：时间 O(log n)，空间 O(1)。
官方题意（改写）：在没有重复元素的旋转升序数组中查找目标值。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.search(...)，输入参数为 nums（List[int]）、target（int）。
输出：返回 int；返回值含义是：在没有重复元素的旋转升序数组中查找目标值。
nums = [4,5,6,7,0,1,2], target = 04说明：该输入按题意计算后得到上述输出。
nums = [4,5,6,7,0,1,2], target = 3-1说明：该输入按题意计算后得到上述输出。
每次二分至少有一半是有序的。先判断左半还是右半有序，再看 target 是否落在有序半区内，决定保留哪边。
旋转数组局部仍有一半保持单调。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1复杂度：时间 O(log n)，空间 O(1)。
官方题意（改写）：在无重复的旋转升序数组中找到最小元素。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.findMin(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：在无重复的旋转升序数组中找到最小元素。
nums = [3,4,5,1,2]1说明：该输入按题意计算后得到上述输出。
nums = [4,5,6,7,0,1,2]0说明：该输入按题意计算后得到上述输出。
右端点可作为参照。若 nums[mid] > nums[right]，最小值在 mid 右侧；否则最小值在 mid 或左侧。
持续缩小到最小值所在下标。
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]复杂度：时间 O(log n)，空间 O(1)。
官方题意（改写）：给定两个升序数组，求合并后的中位数，要求对数时间。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.findMedianSortedArrays(...)，输入参数为 nums1（List[int]）、nums2（List[int]）。
输出：返回 float；返回值含义是：给定两个升序数组，求合并后的中位数，要求对数时间。
nums1 = [1,3], nums2 = [2]2.00000说明：该输入按题意计算后得到上述输出。
nums1 = [1,2], nums2 = [3,4]2.50000说明：该输入按题意计算后得到上述输出。
在较短数组上二分切分位置，使左半部分总长度固定，且左半所有元素不大于右半所有元素。满足条件后由边界值计算中位数。
找切分 i/j，使 max(left) <= min(right)。
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2
left, right = 0, m
while left <= right:
i = (left + right) // 2
j = half - i
a_left = float('-inf') if i == 0 else nums1[i - 1]
a_right = float('inf') if i == m else nums1[i]
b_left = float('-inf') if j == 0 else nums2[j - 1]
b_right = float('inf') if j == n else nums2[j]
if a_left <= b_right and b_left <= a_right:
if (m + n) % 2:
return max(a_left, b_left)
return (max(a_left, b_left) + min(a_right, b_right)) / 2
if a_left > b_right:
right = i - 1
else:
left = i + 1复杂度：时间 O(log min(m,n))，空间 O(1)。
本组 5 题，围绕 栈 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：判断括号字符串是否有效：括号必须按正确顺序闭合。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.isValid(...)，输入参数为 s（str）。
输出：返回 bool；返回值含义是：判断括号字符串是否有效：括号必须按正确顺序闭合。
s = "()"true说明：该输入按题意计算后得到上述输出。
s = "()[]{}"true说明：该输入按题意计算后得到上述输出。
遇到左括号入栈，遇到右括号时栈顶必须是匹配的左括号。最后栈为空才有效。
最近打开的括号必须最先闭合。
class Solution:
def isValid(self, s: str) -> bool:
match = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in match.values():
stack.append(ch)
else:
if not stack or stack.pop() != match[ch]:
return False
return not stack复杂度：时间 O(n)，空间 O(n)。
官方题意（改写）：设计一个支持 push、pop、top 和 getMin 的栈，所有操作都要 O(1)。 完整原题、样例和英文表述以本题官方链接为准。
输入：设计类 MinStack，判题器会按照官方操作序列调用构造器和公开方法。
输出：每次查询方法返回题目要求的布尔值、整数或浮点数；更新类方法只改变对象内部状态。核心目标是：设计一个支持 push、pop、top 和 getMin 的栈，所有操作都要 O(1)。
["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]][null,null,null,null,-3,null,0,-2]说明：按操作序列依次执行；构造器和无返回值操作在输出中记为 null。
普通栈存值，辅助栈存当前最小值。每次 push 时把 min(x, 当前最小值) 同步压入辅助栈。
min_stack[i] 表示 data[0..i] 的最小值。
class MinStack:
def __init__(self):
self.data = []
self.mins = []
def push(self, val: int) -> None:
self.data.append(val)
self.mins.append(val if not self.mins else min(val, self.mins[-1]))
def pop(self) -> None:
self.data.pop()
self.mins.pop()
def top(self) -> int:
return self.data[-1]
def getMin(self) -> int:
return self.mins[-1]复杂度：时间 每次操作 O(1)，空间 O(n)。
官方题意（改写）：解码形如 k[encoded_string] 的字符串，嵌套结构需要展开。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.decodeString(...)，输入参数为 s（str）。
输出：返回 str；返回值含义是：解码形如 k[encoded_string] 的字符串，嵌套结构需要展开。
s = "3[a]2[bc]""aaabcbc"说明：该输入按题意计算后得到上述输出。
s = "3[a2[c]]""accaccacc"说明：该输入按题意计算后得到上述输出。
用栈保存进入 `[` 前的字符串和重复次数。遇到 `]` 时弹出上下文，把当前片段重复后拼接回上一层。
每个左括号开启一个新的局部字符串环境。
class Solution:
def decodeString(self, s: str) -> str:
stack = []
cur = []
num = 0
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == '[':
stack.append((''.join(cur), num))
cur = []
num = 0
elif ch == ']':
prev, repeat = stack.pop()
cur = [prev + ''.join(cur) * repeat]
else:
cur.append(ch)
return ''.join(cur)复杂度：时间 O(输出长度)，空间 O(嵌套深度 + 输出长度)。
官方题意（改写）：对每天温度，返回还要等多少天才会遇到更高温度；没有则为 0。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.dailyTemperatures(...)，输入参数为 temperatures（List[int]）。
输出：返回 List[int]；返回值含义是：对每天温度，返回还要等多少天才会遇到更高温度；没有则为 0。
temperatures = [73,74,75,71,69,72,76,73][1,1,4,2,1,1,0,0]说明：该输入按题意计算后得到上述输出。
temperatures = [30,40,50,60][1,1,1,0]说明：该输入按题意计算后得到上述输出。
单调递减栈存还没找到更高温的下标。当前温度更高时，不断弹栈并计算等待天数。
栈内下标对应温度从底到顶递减。
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
ans = [0] * len(temperatures)
stack = []
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ans复杂度：时间 O(n)，空间 O(n)。
官方题意（改写）：给定柱状图高度，求能组成的最大矩形面积。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.largestRectangleArea(...)，输入参数为 heights（List[int]）。
输出：返回 int；返回值含义是：给定柱状图高度，求能组成的最大矩形面积。
heights = [2,1,5,6,2,3]10说明：该输入按题意计算后得到上述输出。
heights = [2,4]4说明：该输入按题意计算后得到上述输出。
对每根柱子，若知道左右第一个比它矮的位置，就能确定以它为最低高度的最大宽度。单调递增栈在遇到更矮柱子时结算被弹出的柱子。
末尾加 0 强制清空栈，栈中下标对应高度递增。
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
best = 0
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
best = max(best, height * (i - left - 1))
stack.append(i)
return best复杂度：时间 O(n)，空间 O(n)。
本组 3 题，围绕 堆 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：找到数组中第 k 大的元素。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.findKthLargest(...)，输入参数为 nums（List[int]）、k（int）。
输出：返回 int；返回值含义是：找到数组中第 k 大的元素。
[3,2,1,5,6,4], k = 25说明：该输入按题意计算后得到上述输出。
[3,2,3,1,2,4,5,5,6], k = 44说明：该输入按题意计算后得到上述输出。
最直接可用大小为 k 的小根堆；也可以用 Quickselect 平均线性时间。堆写法稳定、易实现。
堆顶始终是当前前 k 大中的最小值。
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]复杂度：时间 O(n log k)，空间 O(k)。
官方题意（改写）：返回数组中出现频率最高的 k 个元素。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.topKFrequent(...)，输入参数为 nums（List[int]）、k（int）。
输出：返回 List[int]；返回值含义是：返回数组中出现频率最高的 k 个元素。
nums = [1,1,1,2,2,3], k = 2[1,2]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
nums = [1], k = 1[1]说明：输出顺序可能不唯一，样例展示一种符合题意的合法结果。
先统计频率，再用小根堆保留频率最高的 k 个元素。由于只关心 top k，堆大小不必超过 k。
堆元素为 (freq, value)，超出 k 时弹出最低频。
from collections import Counter
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
heap = []
for x, freq in Counter(nums).items():
heapq.heappush(heap, (freq, x))
if len(heap) > k:
heapq.heappop(heap)
return [x for _, x in heap]复杂度：时间 O(n log k)，空间 O(n)。
官方题意（改写）：设计数据结构，持续加入数字并能返回当前中位数。 完整原题、样例和英文表述以本题官方链接为准。
输入：设计类 MedianFinder，判题器会按照官方操作序列调用构造器和公开方法。
输出：每次查询方法返回题目要求的布尔值、整数或浮点数；更新类方法只改变对象内部状态。核心目标是：设计数据结构，持续加入数字并能返回当前中位数。
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []][null, null, null, 1.5, null, 2.0]说明：按操作序列依次执行；构造器和无返回值操作在输出中记为 null。
用两个堆维护较小一半和较大一半。左边用最大堆（取负数实现），右边用最小堆，并保持两堆大小差不超过 1。
small 存较小一半，large 存较大一半；奇数时 small 多一个。
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # 最大堆，存负数
self.large = [] # 最小堆
def addNum(self, num: int) -> None:
heapq.heappush(self.small, -num)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2复杂度：时间 addNum O(log n)，findMedian O(1)，空间 O(n)。
本组 4 题，围绕 贪心算法 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：给定每天股价，只允许买卖一次，求最大利润。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.maxProfit(...)，输入参数为 prices（List[int]）。
输出：返回 int；返回值含义是：给定每天股价，只允许买卖一次，求最大利润。
[7,1,5,3,6,4]5说明：该输入按题意计算后得到上述输出。
prices = [7,6,4,3,1]0说明：该输入按题意计算后得到上述输出。
卖出日确定时，最佳买入价是此前最低价。遍历价格时维护 min_price，并更新当前卖出的最大利润。
每一天只作为卖出日尝试一次。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf')
best = 0
for price in prices:
min_price = min(min_price, price)
best = max(best, price - min_price)
return best复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：判断从数组第一个位置出发，是否能跳到最后一个位置。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.canJump(...)，输入参数为 nums（List[int]）。
输出：返回 bool；返回值含义是：判断从数组第一个位置出发，是否能跳到最后一个位置。
nums = [2,3,1,1,4]true说明：该输入按题意计算后得到上述输出。
nums = [3,2,1,0,4]false说明：该输入按题意计算后得到上述输出。
贪心维护当前能到达的最远位置 farthest。若遍历到 i 时 i 已超过 farthest，说明这个位置不可达。
只要每个经过的位置都可达，就持续扩展边界。
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
if farthest >= len(nums) - 1:
return True
return True复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：求从第一个位置跳到最后一个位置的最少跳跃次数。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.jump(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：求从第一个位置跳到最后一个位置的最少跳跃次数。
nums = [2,3,1,1,4]2说明：该输入按题意计算后得到上述输出。
nums = [2,3,0,1,4]2说明：该输入按题意计算后得到上述输出。
把当前跳数能覆盖的范围看成一层 BFS。遍历当前层时维护下一层最远边界；到达当前层末尾就必须跳一次。
end 是当前跳数能到的最远位置，farthest 是下一跳能到的最远位置。
class Solution:
def jump(self, nums: List[int]) -> int:
steps = 0
end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == end:
steps += 1
end = farthest
return steps复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：把字符串划分为尽可能多的片段，使每个字母最多只出现在一个片段中。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.partitionLabels(...)，输入参数为 s（str）。
输出：返回 List[int]；返回值含义是：把字符串划分为尽可能多的片段，使每个字母最多只出现在一个片段中。
s = "ababcbacadefegdehijhklij"[9,7,8]说明：该输入按题意计算后得到上述输出。
s = "eccbbbbdec"[10]说明：该输入按题意计算后得到上述输出。
先记录每个字符最后出现位置。扫描时维护当前片段必须覆盖到的最远位置 end，当 i == end 时可以切分。
片段必须覆盖其中所有字符的最后位置。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {ch: i for i, ch in enumerate(s)}
ans = []
start = end = 0
for i, ch in enumerate(s):
end = max(end, last[ch])
if i == end:
ans.append(end - start + 1)
start = i + 1
return ans复杂度：时间 O(n)，空间 O(字符集)。
本组 10 题，围绕 动态规划 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：每次可以爬 1 或 2 阶，求到达第 n 阶的方法数。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.climbStairs(...)，输入参数为 n（int）。
输出：返回 int；返回值含义是：每次可以爬 1 或 2 阶，求到达第 n 阶的方法数。
n = 22说明：该输入按题意计算后得到上述输出。
n = 33说明：该输入按题意计算后得到上述输出。
到达第 i 阶的最后一步来自 i-1 或 i-2，因此 dp[i] = dp[i-1] + dp[i-2]。这就是 Fibonacci 结构。
只保留前两项即可。
class Solution:
def climbStairs(self, n: int) -> int:
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：生成杨辉三角前 numRows 行。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.generate(...)，输入参数为 numRows（int）。
输出：返回 List[List[int]]；返回值含义是：生成杨辉三角前 numRows 行。
numRows = 5[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]说明：该输入按题意计算后得到上述输出。
numRows = 1[[1]]说明：该输入按题意计算后得到上述输出。
每行首尾是 1，中间元素等于上一行相邻两个元素之和。逐行构造即可。
第 i 行只依赖第 i-1 行。
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = []
for i in range(numRows):
row = [1] * (i + 1)
for j in range(1, i):
row[j] = ans[i - 1][j - 1] + ans[i - 1][j]
ans.append(row)
return ans复杂度：时间 O(numRows^2)，空间 O(numRows^2) 输出空间。
官方题意（改写）：不能偷相邻房屋，求能偷到的最大金额。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.rob(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：不能偷相邻房屋，求能偷到的最大金额。
[1,2,3,1]4说明：该输入按题意计算后得到上述输出。
[2,7,9,3,1]12说明：该输入按题意计算后得到上述输出。
到第 i 间房的最优解要么不偷它，继承前一间最优；要么偷它，加上 i-2 的最优。
prev2 表示 i-2 最优，prev1 表示 i-1 最优。
class Solution:
def rob(self, nums: List[int]) -> int:
prev2 = prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：求组成 n 的完全平方数的最少数量。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.numSquares(...)，输入参数为 n（int）。
输出：返回 int；返回值含义是：求组成 n 的完全平方数的最少数量。
n = 123说明：该输入按题意计算后得到上述输出。
n = 132说明：该输入按题意计算后得到上述输出。
这是完全背包最少物品数。dp[i] 表示凑出 i 的最少平方数数量，枚举每个平方数更新。
每个平方数可以重复使用。
class Solution:
def numSquares(self, n: int) -> int:
dp = [0] + [float('inf')] * n
squares = [i * i for i in range(1, int(n ** 0.5) + 1)]
for i in range(1, n + 1):
for sq in squares:
if sq > i:
break
dp[i] = min(dp[i], dp[i - sq] + 1)
return dp[n]复杂度：时间 O(n sqrt n)，空间 O(n)。
官方题意（改写）：给定硬币面额和总金额，求凑出金额所需的最少硬币数，不能凑出返回 -1。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.coinChange(...)，输入参数为 coins（List[int]）、amount（int）。
输出：返回 int；返回值含义是：给定硬币面额和总金额，求凑出金额所需的最少硬币数，不能凑出返回 -1。
coins = [1, 2, 5], amount = 113说明：该输入按题意计算后得到上述输出。
coins = [2], amount = 3-1说明：该输入按题意计算后得到上述输出。
完全背包最小值。dp[x] 表示凑出金额 x 的最少硬币数，转移为 dp[x] = min(dp[x-coin] + 1)。
外层枚举金额，内层枚举最后一枚硬币。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [0] + [float('inf')] * amount
for x in range(1, amount + 1):
for coin in coins:
if x >= coin:
dp[x] = min(dp[x], dp[x - coin] + 1)
return -1 if dp[amount] == float('inf') else dp[amount]复杂度：时间 O(amount * len(coins))，空间 O(amount)。
官方题意（改写）：判断字符串是否可以被字典中的一个或多个单词拼接而成。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.wordBreak(...)，输入参数为 s（str）、wordDict（List[str]）。
输出：返回 bool；返回值含义是：判断字符串是否可以被字典中的一个或多个单词拼接而成。
s = "leetcode", wordDict = ["leet", "code"]true说明：该输入按题意计算后得到上述输出。
s = "applepenapple", wordDict = ["apple", "pen"]true说明：该输入按题意计算后得到上述输出。
dp[i] 表示 s[:i] 是否可拆分。若存在 j 每个切分点 j 把问题拆成已可达前缀和一个字典单词。 复杂度：时间 O(n^2)，空间 O(n)。
解法：前缀可达 DP
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[-1]复杂度分析
官方题意（改写）：求数组中最长严格递增子序列的长度。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.lengthOfLIS(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：求数组中最长严格递增子序列的长度。
nums = [10,9,2,5,3,7,101,18]4说明：该输入按题意计算后得到上述输出。
nums = [0,1,0,3,2,3]4说明：该输入按题意计算后得到上述输出。
tails[len-1] 表示长度为 len 的递增子序列可能拥有的最小结尾。对每个数用二分找到替换位置，保持 tails 尽量小。
更小结尾给后续元素留下更多扩展空间。
from bisect import bisect_left
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)复杂度：时间 O(n log n)，空间 O(n)。
官方题意（改写）：求数组中乘积最大的连续子数组。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.maxProduct(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：求数组中乘积最大的连续子数组。
nums = [2,3,-2,4]6说明：该输入按题意计算后得到上述输出。
nums = [-2,0,-1]0说明：该输入按题意计算后得到上述输出。
负数会让最大值和最小值互换。维护以当前位置结尾的最大乘积和最小乘积，遇到新数 x 时从三种候选中取值。
最小负乘积乘以负数可能变成最大正乘积。
class Solution:
def maxProduct(self, nums: List[int]) -> int:
cur_max = cur_min = best = nums[0]
for x in nums[1:]:
a, b = cur_max * x, cur_min * x
cur_max = max(x, a, b)
cur_min = min(x, a, b)
best = max(best, cur_max)
return best复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：判断数组是否能分成两个和相等的子集。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.canPartition(...)，输入参数为 nums（List[int]）。
输出：返回 bool；返回值含义是：判断数组是否能分成两个和相等的子集。
nums = [1,5,11,5]true说明：该输入按题意计算后得到上述输出。
nums = [1,2,3,5]false说明：该输入按题意计算后得到上述输出。
总和必须为偶数。问题转化为能否从数组中选出若干数使和为 total/2，这是 0/1 背包可达性问题。
倒序更新，保证每个数只使用一次。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for x in nums:
for s in range(target, x - 1, -1):
dp[s] = dp[s] or dp[s - x]
return dp[target]复杂度：时间 O(n * target)，空间 O(target)。
官方题意（改写）：求最长有效括号子串长度。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.longestValidParentheses(...)，输入参数为 s（str）。
输出：返回 int；返回值含义是：求最长有效括号子串长度。
s = "(()"2说明：该输入按题意计算后得到上述输出。
s = ")()())"4说明：该输入按题意计算后得到上述输出。
栈存还未匹配的下标，并用 -1 作为最近非法位置哨兵。遇到右括号匹配后，当前有效长度是 i - stack[-1]。
栈底记录当前有效区间左边界之前的位置。
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
best = max(best, i - stack[-1])
return best复杂度：时间 O(n)，空间 O(n)。
本组 5 题，围绕 多维动态规划 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：机器人只能向右或向下移动，求从左上到右下的不同路径数。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.uniquePaths(...)，输入参数为 m（int）、n（int）。
输出：返回 int；返回值含义是：机器人只能向右或向下移动，求从左上到右下的不同路径数。
m = 3, n = 728说明：该输入按题意计算后得到上述输出。
m = 3, n = 23说明：该输入按题意计算后得到上述输出。
到达每个格子的路径数等于上方和左方路径数之和。用一维 dp 按行滚动即可。
dp[j] 更新后表示当前行第 j 列路径数。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[-1]复杂度：时间 O(mn)，空间 O(n)。
官方题意（改写）：在非负网格中，只能向右或向下，求从左上到右下的最小路径和。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.minPathSum(...)，输入参数为 grid（List[List[int]]）。
输出：返回 int；返回值含义是：在非负网格中，只能向右或向下，求从左上到右下的最小路径和。
grid = [[1,3,1],[1,5,1],[4,2,1]]7说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
grid = [[1,2,3],[4,5,6]]12说明：矩阵或网格按二维数组展示，输出为该输入下的结果。
dp[j] 表示当前行第 j 列的最小路径和，转移来自上方 dp[j] 和左方 dp[j-1] 的较小值。
先初始化第一行，再逐行更新。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = grid[0][0]
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j]
for i in range(1, m):
dp[0] += grid[i][0]
for j in range(1, n):
dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
return dp[-1]复杂度：时间 O(mn)，空间 O(n)。
官方题意（改写）：求字符串中最长回文子串。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.longestPalindrome(...)，输入参数为 s（str）。
输出：返回 str；返回值含义是：求字符串中最长回文子串。
s = "babad""bab"说明：该输入按题意计算后得到上述输出。
s = "cbbd""bb"说明：该输入按题意计算后得到上述输出。
回文中心可以是一个字符或两个字符之间的间隙。枚举中心向两侧扩展，记录最长区间。
分别处理奇数长度和偶数长度回文。
class Solution:
def longestPalindrome(self, s: str) -> str:
best_l = best_r = 0
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return l + 1, r - 1
for i in range(len(s)):
for l, r in (expand(i, i), expand(i, i + 1)):
if r - l > best_r - best_l:
best_l, best_r = l, r
return s[best_l:best_r + 1]复杂度：时间 O(n^2)，空间 O(1)。
官方题意（改写）：求两个字符串的最长公共子序列长度，子序列不要求连续。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.longestCommonSubsequence(...)，输入参数为 text1（str）、text2（str）。
输出：返回 int；返回值含义是：求两个字符串的最长公共子序列长度，子序列不要求连续。
text1 = "abcde", text2 = "ace"3说明：该输入按题意计算后得到上述输出。
text1 = "abc", text2 = "abc"3说明：该输入按题意计算后得到上述输出。
dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度。若末字符相等，来自 dp[i-1][j-1]+1；否则取上方或左方最大值。
prev 保存上一行左上角值。
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n = len(text2)
dp = [0] * (n + 1)
for ch1 in text1:
prev = 0
for j, ch2 in enumerate(text2, 1):
tmp = dp[j]
if ch1 == ch2:
dp[j] = prev + 1
else:
dp[j] = max(dp[j], dp[j - 1])
prev = tmp
return dp[n]复杂度：时间 O(mn)，空间 O(n)。
官方题意（改写）：求把 word1 转换成 word2 所需的最少插入、删除、替换操作数。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.minDistance(...)，输入参数为 word1（str）、word2（str）。
输出：返回 int；返回值含义是：求把 word1 转换成 word2 所需的最少插入、删除、替换操作数。
word1 = "horse", word2 = "ros"3说明：该输入按题意计算后得到上述输出。
word1 = "intention", word2 = "execution"5说明：该输入按题意计算后得到上述输出。
dp[i][j] 表示 word1[:i] 到 word2[:j] 的编辑距离。末字符相同则继承左上；不同则从删除、插入、替换三种操作中取最小。
一维滚动时 prev 保存左上角旧值。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n = len(word2)
dp = list(range(n + 1))
for i, c1 in enumerate(word1, 1):
prev = dp[0]
dp[0] = i
for j, c2 in enumerate(word2, 1):
tmp = dp[j]
if c1 == c2:
dp[j] = prev
else:
dp[j] = 1 + min(dp[j], dp[j - 1], prev)
prev = tmp
return dp[n]复杂度：时间 O(mn)，空间 O(n)。
本组 5 题，围绕 技巧 的核心模式展开。先识别不变量，再选择哈希、指针、递归、队列、堆或 DP 状态。
官方题意（改写）：数组中除一个元素只出现一次外，其余每个元素都出现两次，找出只出现一次的元素。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.singleNumber(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：数组中除一个元素只出现一次外，其余每个元素都出现两次，找出只出现一次的元素。
nums = [2,2,1]1说明：该输入按题意计算后得到上述输出。
nums = [4,1,2,1,2]4说明：该输入按题意计算后得到上述输出。
异或满足 x^x=0、x^0=x，并且交换结合。把所有数异或起来，成对元素抵消，剩下唯一元素。
不需要额外空间，顺序无关。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for x in nums:
ans ^= x
return ans复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：找出数组中出现次数超过一半的多数元素。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.majorityElement(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：找出数组中出现次数超过一半的多数元素。
nums = [3,2,3]3说明：该输入按题意计算后得到上述输出。
nums = [2,2,1,1,1,2,2]2说明：该输入按题意计算后得到上述输出。
Boyer-Moore 投票：把多数元素和其他元素两两抵消，最后留下的候选一定是多数元素。
计数为 0 时更换候选，相同加一，不同减一。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = None
count = 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：原地排序只包含 0、1、2 的数组，使相同颜色相邻。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.sortColors(...)，输入参数为 nums（List[int]）。
输出：函数原地修改输入对象，不需要返回新对象；修改后的数据应满足：原地排序只包含 0、1、2 的数组，使相同颜色相邻。
nums = [2,0,2,1,1,0][0,0,1,1,2,2]说明：该输入按题意计算后得到上述输出。
nums = [2,0,1][0,1,2]说明：该输入按题意计算后得到上述输出。
荷兰国旗问题。left 左侧全是 0，right 右侧全是 2，i 扫描未知区间。遇 0 换到左侧，遇 2 换到右侧且 i 不前进。
维护 [0,left)、[left,i)、(right,n) 三个已知区域。
class Solution:
def sortColors(self, nums: List[int]) -> None:
left, i, right = 0, 0, len(nums) - 1
while i <= right:
if nums[i] == 0:
nums[left], nums[i] = nums[i], nums[left]
left += 1
i += 1
elif nums[i] == 2:
nums[i], nums[right] = nums[right], nums[i]
right -= 1
else:
i += 1复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：将数组原地变成字典序中的下一个排列；若已经最大，则变成最小排列。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.nextPermutation(...)，输入参数为 nums（List[int]）。
输出：函数原地修改输入对象，不需要返回新对象；修改后的数据应满足：将数组原地变成字典序中的下一个排列；若已经最大，则变成最小排列。
nums = [1,2,3][1,3,2]说明：该输入按题意计算后得到上述输出。
nums = [3,2,1][1,2,3]说明：该输入按题意计算后得到上述输出。
从右找第一个下降位置 i，使 nums[i] < nums[i+1]。再从右找第一个大于 nums[i] 的数交换，最后反转 i+1 后缀使其最小。
后缀原本是非递增，交换后反转即可得到最小后缀。
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1复杂度：时间 O(n)，空间 O(1)。
官方题意（改写）：长度为 n+1 的数组中每个数在 1..n 范围内，找出唯一重复的数，不能修改数组。 完整原题、样例和英文表述以本题官方链接为准。
输入：判题入口是 Solution.findDuplicate(...)，输入参数为 nums（List[int]）。
输出：返回 int；返回值含义是：长度为 n+1 的数组中每个数在 1..n 范围内，找出唯一重复的数，不能修改数组。
nums = [1,3,4,2,2]2说明：该输入按题意计算后得到上述输出。
nums = [3,1,3,4,2]3说明：该输入按题意计算后得到上述输出。
把 nums[i] 看成从 i 指向 nums[i] 的边，因为有重复值，函数图中存在环。重复数就是环入口，用 Floyd 算法寻找。
数组下标跳转构成链表，重复值对应入环点。
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow复杂度：时间 O(n)，空间 O(1)。
刷完一组后，回头复述每题的不变量：哈希表里存什么，指针为什么移动，递归返回什么，DP 状态表示什么。