LeetCode热题100【Python】

文章目录

• ACM模式
• 哈希
• • 1. 两数之和
  • 49. 字母异位词分组
  • 128. 最长连续序列
• 双指针
• • 两个升序数组合并
  • 283. 移动零
  • 11. 盛最多水的容器
  • 15. 三数之和
  • 42. 接雨水
• 滑动窗口
• • 3. 无重复字符的最长子串
  • 438. 找到字符串中所有的字母异位词
• 子串
• • 14. 最长公共前缀
  • 560. 和为K的子数组
  • 239. 滑动窗口最大值
  • 76. 最小覆盖字串
• 普通数组
• • 53. 最大子数组和
  • 56. 合并区间
  • 189. 轮转数组
  • 238. 除了自身之外数组的乘积
  • 41. 缺失的第一个正数
• 矩阵
• • 矩阵乘法
  • 73. 矩阵置零
  • 54. 螺旋矩阵
  • 48. 旋转图像
  • 240. 搜索二维矩阵 II
• 链表
• • 160. 相交链表
  • 206. 反转链表
  • 234. 回文链表
  • 141. 环形链表
  • 142. 环形链表 II
  • 21. 合并两个有序链表
  • 2. 两数相加
  • 19. 删除链表的倒数第N个结点
  • 24. 两两交换链表中的节点
  • 25. K个一组翻转链表
  • 138. 随机链表的复制
  • 148. 排序链表
  • 23. 合并K个升序链表
  • 146. LRU缓存
• 二叉树
• • 94. 二叉树的中序遍历
  • 104. 二叉树的最大深度
  • 226. 翻转二叉树
  • 101. 对称二叉树
  • 543. 二叉树的直径
  • 108. 将有序数组转换为二叉搜索树
• 图论
• • 200. 岛屿面积
• 回溯
• • 46. 全排列
  • 78. 子集
  • 17. 电话号码的字母组合
  • 39. 组合总和
  • 22. 括号生成
  • 79. 单词搜索
  • 131. 分割回文串
  • 51. N皇后
• 二分查找
• • 35. 搜索插入位置
  • 74. 搜索二维矩阵
  • 34. 在排序数组中查找元素的第一个和最后一个位置
  • 33. 搜索旋转排序数组
  • 153. 寻找旋转排序数组中的最小值
  • 4. 寻找两个正序数组的中位数
• 栈
• • 20. 有效的括号
  • 最长有效括号
  • 155. 最小栈
  • 394. 字符串解码
  • 739. 每日温度
  • 84. 柱状图中最大的矩形
• 堆
• • 215. 数组中的第K个最大元素
  • 347. 前K个高频元素
  • 295. 数据流的中位数
• 贪心算法
• • 121. 买卖股票的最佳时机
  • 55. 跳跃游戏
  • 45. 跳跃游戏 II
  • 763. 划分字母区间
• 动态规划
• • 70. 爬楼梯
  • 118. 杨辉三角
  • 198. 打家劫舍
  • 279. 完全平方数
  • 322. 零钱兑换
• 多维动态规划
• • 62. 不同路径
  • 64. 最小路径和
  • 5. 最长回文子串
  • 1143. 最长公共子序列
  • 72. 编辑距离
• 技巧
• • 136. 只出现一次的数字
  • 169. 多数元素
  • 75. 颜色分类
  • 31. 下一个排列
  • 287. 寻找重复数
• 非常规题
• • 热门激活函数
  • 热门损失函数
  • 各种组件
  • • CNN
    • Normalization
  • Transformer
  • • SelfAttention
    • MHA
    • TransformerEncoderBlock
    • Position Embedding
  • 大模型的代码
  • • 后训练
  • 数学公式推导
  • 经典算法
  • 强化学习代码
  • 小于n的最大整数
  • WER 计算

ACM模式

import sys

def solve():
data = sys.stdin.read().strip().split()
# 所有数据都在data列表中
# 根据题目要求解析…

# 例如：第一个数是n，后面跟着n个数
if data:
n = int(data[0])
nums = list(map(int, data[1:n+1]))
# 处理…

if __name__ == "__main__":
solve()

哈希

1. 两数之和

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 思路：遍历数组，用哈希表存储{数值: 下标}。对于当前数num，检查target – num是否已在哈希表中，如果在就直接返回两个下标，否则将当前数加入哈希表。时间复杂度O(n)。

def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target – num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []

49. 字母异位词分组

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]] 思路：异位词排序后会得到相同的字符串。遍历所有单词，将每个单词排序后作为key，存入哈希表（value是异位词列表）。最后返回哈希表的所有value即可。时间复杂度O(n·klogk)，k为单词最大长度。

def groupAnagrams(strs):
from collections import defaultdict
groups = defaultdict(list)

for s in strs:
# 将字符串排序后作为key
key = ''.join(sorted(s))
groups[key].append(s)

return list(groups.values())

def groupAnagrams(strs):
from collections import defaultdict
groups = defaultdict(list)

for s in strs:
# 用26个字母的计数作为key
count = [0] * 26
for c in s:
count[ord(c) – ord('a')] += 1
groups[tuple(count)].append(s)

return list(groups.values())

128. 最长连续序列

输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 思路：先用set去重。遍历每个数，只从序列的起点开始计算（即num-1不在set中时）。然后不断找num+1、num+2…统计当前连续序列的长度，更新最大值。这样每个数只会访问一次，时间复杂度O(n)。

def longestConsecutive(nums):
if not nums:
return 0

num_set = set(nums)
max_len = 0

for num in num_set:
# 只从序列的起点开始计算
if num – 1 not in num_set:
curr_num = num
curr_len = 1

while curr_num + 1 in num_set:
curr_num += 1
curr_len += 1

max_len = max(max_len, curr_len)

return max_len

双指针

两个升序数组合并

算法复杂度 时间复杂度：O (m + n) （只遍历一遍） 空间复杂度：O (m + n) （存储结果） 这是最优解法，没有比这更快的了。

def merge_two_sorted_arrays(nums1, nums2):
i = j = 0 # 双指针
res = [] # 结果数组

# 同时遍历两个数组，谁小取谁
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
res.append(nums1[i])
i += 1
else:
res.append(nums2[j])
j += 1

# 处理剩余元素（只会剩下一个数组）
res += nums1[i:]
res += nums2[j:]

return res

283. 移动零

输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 思路：快慢指针。j指向第一个0的位置（即下一个非零元素应该放的位置）。遍历数组，遇到非零元素就与j位置交换，然后j后移。这样所有非零元素都被移到前面，零自然被挤到后面。

def moveZeroes(nums):
# 双指针：j指向第一个0的位置
j = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[i], nums[j] = nums[j], nums[i]
j += 1
return nums

11. 盛最多水的容器

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。min(8,7)*(9-2)=7*7=49 思路：左右指针从两端向中间移动。面积由较短的边决定，所以每次移动较短的边才有可能找到更大的面积（因为宽度在减小，只有高度可能变大）。时间复杂度O(n)。

def maxArea(height):
left, right = 0, len(height) – 1
max_water = 0

while left < right:
# 计算当前面积
h = min(height[left], height[right])
w = right – left
max_water = max(max_water, h * w)

# 移动较短的边
if height[left] < height[right]:
left += 1
else:
right -= 1

return max_water

15. 三数之和

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。 思路：排序+双指针。固定第一个数nums[i]，然后用双指针在i+1到末尾之间找两数之和等于-nums[i]。关键点是去重：①第一个数去重 ②找到解后对左右指针去重。时间复杂度O(n²)。

def threeSum(nums):
nums.sort()
res = []
n = len(nums)

for i in range(n – 2):
# 去重：跳过相同的第一个数
if i > 0 and nums[i] == nums[i–1]:
continue

left, right = i + 1, n – 1
target = –nums[i]

while left < right:
curr_sum = nums[left] + nums[right]
if curr_sum == target:
res.append([nums[i], nums[left], nums[right]])

# 去重
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right – 1]:
right -= 1

left += 1
right -= 1
elif curr_sum < target:
left += 1
else:
right -= 1

return res

42. 接雨水

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 思路：双指针记录左右两边的最大高度。对于每个位置，能接的雨水量取决于它左右两边最大高度的较小值减去当前高度。通过比较height[left]和height[right]，可以确定哪边的最大高度是确定的，从而计算该位置的雨水量并移动指针。

def trap(height):
if not height:
return 0

left, right = 0, len(height) – 1
left_max = right_max = water = 0

while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max – height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max – height[right]
right -= 1

return water

滑动窗口

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

输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。 思路：滑动窗口+哈希表。用left指向窗口左边界，right遍历字符串。used哈希表记录每个字符最近出现的位置。当遇到重复字符且该字符在窗口内（即used[c] >= left）时，将left移动到重复字符的下一个位置。每次更新最长长度。时间复杂度O(n)。

def lengthOfLongestSubstring(s):
left = max_len = 0
used = {}

for right, c in enumerate(s):
if c in used and used[c] >= left:
left = used[c] + 1
used[c] = right
max_len = max(max_len, right – left + 1)

return max_len

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

输入: s = “cbaebabacd”, p = “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。 思路：固定大小的滑动窗口+字符计数数组。用两个长度为26的数组分别统计p和窗口内字符出现次数。先初始化第一个窗口，然后每次移动窗口时：加入一个新字符，移除一个旧字符。比较两个计数数组是否相等，相等则记录起始下标。时间复杂度O(n)。

def findAnagrams(s, p):
if len(p) > len(s):
return []

p_count = [0] * 26
s_count = [0] * 26

# 初始化
for i in range(len(p)):
p_count[ord(p[i]) – ord('a')] += 1
s_count[ord(s[i]) – ord('a')] += 1

res = []
if s_count == p_count:
res.append(0)

for i in range(len(p), len(s)):
# 滑动窗口
s_count[ord(s[i]) – ord('a')] += 1
s_count[ord(s[i – len(p)]) – ord('a')] -= 1

if s_count == p_count:
res.append(i – len(p) + 1)

return res

思路：滑动窗口维护与p等长的子串，用Counter统计字符频率，当窗口计数与p计数相等时记录起始位置。

def findAnagrams(s, p):
from collections import Counter

len_p, len_s = len(p), len(s)
if len_p > len_s:
return []

# 统计p的字符频率
p_count = Counter(p)
window_count = Counter()
res = []

for i in range(len_s):
# 加入当前字符
window_count[s[i]] += 1

# 窗口大小超过p的长度时，移除左边字符
if i >= len_p:
if window_count[s[i – len_p]] == 1:
del window_count[s[i – len_p]]
else:
window_count[s[i – len_p]] -= 1

# 比较窗口和p的字符频率
if window_count == p_count:
res.append(i – len_p + 1)

return res

子串

14. 最长公共前缀

输入：strs = [“flower”,“flow”,“flight”] 输出：“fl”

def longestCommonPrefix(strs):
if not strs:
return ""

# 取第一个字符串作为基准
prefix = strs[0]

# 依次与每个字符串比较
for s in strs[1:]:
# 不断缩短prefix直到是s的前缀
while s.find(prefix) != 0:
prefix = prefix[:–1]
if not prefix:
return ""

return prefix

560. 和为K的子数组

输入：nums = [1,2,3], k = 3 输出：2 len([[1,2],[3]]) 思路：前缀和+哈希表。遍历数组计算前缀和curr_sum，用哈希表记录每个前缀和出现的次数。对于当前curr_sum，查找之前有多少个前缀和等于curr_sum – k，这些位置到当前索引的子数组和就是k。注意初始化{0:1}表示空前缀。

def subarraySum(nums, k):
# 前缀和 + 哈希表
prefix_sum = {0: 1} # 前缀和 -> 出现次数
curr_sum = count = 0

for num in nums:
curr_sum += num
# 查找是否存在前缀和 = curr_sum – k
if curr_sum – k in prefix_sum:
count += prefix_sum[curr_sum – k]
# 更新当前前缀和的出现次数
prefix_sum[curr_sum] = prefix_sum.get(curr_sum, 0) + 1

return count

239. 滑动窗口最大值

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 以 nums = [1,3,-1,-3,5,3,6,7], k = 3 为例：

本题难点： 如何在每次窗口滑动后，将 “获取窗口内最大值” 的时间复杂度从 O(k) 降低至 O(1) 。

为什么用双端队列？ 队尾：需要频繁弹出较小的元素（pop()） 队首：需要移除滑出窗口的元素（popleft()）

为什么存下标不存值？ 需要判断元素是否还在窗口内（通过下标差） 通过下标可以随时获取对应的值

思路：单调队列。维护一个双端队列，始终保持队首是当前窗口最大值的下标。遍历数组时：①从队尾移除所有比当前元素小的值 ②将当前元素下标入队 ③如果队首已滑出窗口则移除 ④当窗口形成后，队首就是最大值。

def maxSlidingWindow(nums, k):
dq = collections.deque()
res = []

for i, n in enumerate(nums):
while dq and nums[dq[–1]] < n:
dq.pop()
dq.append(i)
if dq[0] == i – k:
dq.popleft()
if i >= k – 1:
res.append(nums[dq[0]])

return res

76. 最小覆盖字串

输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。 思路：滑动窗口+计数。用need字典记录t中字符的需求量，missing表示还缺多少个字符。右指针扩展窗口直到包含所有t中字符，然后收缩左指针移除多余字符，记录最小窗口。之后左指针右移一位打破平衡，继续寻找下一个满足条件的窗口。

def minWindow(s, t):
from collections import Counter

if not s or not t or len(s) < len(t):
return ""

need = Counter(t) # 需要凑齐的字符及数量
missing = len(t) # 还缺多少个字符
left = start = end = 0

for right, char in enumerate(s, 1):
# right从1开始，方便计算长度
# 如果当前字符是需要的，missing减少
if need[char] > 0:
missing -= 1
need[char] -= 1

# 当窗口包含所有需要的字符时
if missing == 0:
# 收缩左边界，移除多余的字符
while left < right and need[s[left]] < 0:
need[s[left]] += 1
left += 1

# 更新最小窗口
if end == 0 or right – left < end – start:
start, end = left, right

# 移动左边界，打破满足条件的状态，继续寻找下一个窗口
need[s[left]] += 1
missing += 1
left += 1

return s[start:end]

普通数组

53. 最大子数组和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 思路：遍历数组时，对于每个位置，计算以当前元素结尾的最大子数组和：

• curr_sum表示以当前元素结尾的子数组最大和
• 要么只取当前元素（重新开始），要么加上之前的连续子数组
• 状态转移方程：curr_sum = max(num, curr_sum + num)

用max_sum记录遍历过程中出现的最大值，最后返回即可。

def maxSubArray(nums):
# 动态规划，Kadane算法
curr_sum = max_sum = nums[0]

for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)

return max_sum

56. 合并区间

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 思路：排序+贪心。先按区间起点排序，然后遍历：如果当前区间起点 ≤ 上一个合并区间的终点，说明重叠，更新上一个区间的终点为两者最大值；否则不重叠，直接加入结果。

def merge(intervals):
if not intervals:
return []

# 按区间起点排序
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]

for interval in intervals[1:]:
# 如果有重叠，合并
if interval[0] <= merged[–1][1]:
merged[–1][1] = max(merged[–1][1], interval[1])
else:
merged.append(interval)

return merged

189. 轮转数组

输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 思路：三次翻转。先整体翻转，再翻转前k个，最后翻转剩余部分。例如[1,2,3,4,5,6,7], k=3：整体→[7,6,5,4,3,2,1]，前3个→[5,6,7,4,3,2,1]，剩余→[5,6,7,1,2,3,4]。时间复杂度O(n)，空间O(1)。

def rotate(nums, k):
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k %= n # 处理k大于n的情况

# 方法1：三次翻转（最优）
def reverse(start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1

reverse(0, n – 1) # 整体翻转
reverse(0, k – 1) # 翻转前k个
reverse(k, n – 1) # 翻转剩余部分

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

输入: nums = [1,2,3,4] 输出: [24,12,8,6] 思路：左右乘积列表。第一遍遍历计算每个位置左边所有数的乘积存入result；第二遍从右向左遍历，用right_product记录右边乘积，乘到result对应位置。这样每个位置的result就是左边乘积×右边乘积，且不使用除法。

def productExceptSelf(nums):
n = len(nums)
result = [1] * n

# 计算左边乘积
left_product = 1
for i in range(n):
result[i] = left_product
left_product *= nums[i]

# 乘上右边乘积
right_product = 1
for i in range(n – 1, –1, –1):
result[i] *= right_product
right_product *= nums[i]

return result

41. 缺失的第一个正数

输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。 思路：原地哈希（索引标记）。长度为n的数组，答案一定在[1, n+1]范围内。第一遍将所有不在[1,n]的数标记为n+1；第二遍遍历，将出现过的正数对应的索引位置的值标记为负数；第三遍找到第一个正数索引，其索引+1就是答案。利用数组本身作为哈希表，空间O(1)。

这个算法的精妙之处在于利用数组本身作为哈希表，通过正负号来标记某个数字是否出现过，既节省了空间，又保持了O(n)的时间复杂度。

让我们一步步分析： 初始状态 nums = [3, 4, -1, 1], n = 4 第一步：预处理 将所有不在 [1, 4] 范围内的数标记为 n+1 = 5 nums = [3, 4, 5, 1] 第二步：标记出现过的数 遍历数组，用绝对值作为索引，将对应位置标记为负数 i=0: val = |3| = 3，3 在 [1,4] 范围内，索引 3-1 = 2 的值是 5 > 0，将 nums[2] 变成 -5，nums = [3, 4, -5, 1] i=1: val = |4| = 4，4 在 [1,4] 范围内，索引 4-1 = 3 的值是 1 > 0，将 nums[3] 变成 -1，nums = [3, 4, -5, -1] i=2: val = |-5| = 5，5 不在 [1,4] 范围内，跳过 i=3: val = |-1| = 1，1 在 [1,4] 范围内，索引 1-1 = 0 的值是 3 > 0，将 nums[0] 变成 -3，nums = [-3, 4, -5, -1] 第三步：查找第一个正数 遍历数组找第一个 > 0 的数： 索引0: -3 < 0 索引1: 4 > 0 ✅ 找到第一个正数 第一个正数的索引是 1，所以返回 1 + 1 = 2

最终结果：缺失的最小正数是 2

def firstMissingPositive(nums):
n = len(nums)

# 将不在[1, n]范围内的数标记为n+1
for i in range(n):
if nums[i] <= 0 or nums[i] > n:
nums[i] = n + 1

# 将出现的正数对应的索引位置标记为负数
for i in range(n):
val = abs(nums[i])
if 1 <= val <= n:
if nums[val – 1] > 0:
nums[val – 1] = –nums[val – 1]

# 第一个正数的索引+1就是缺失的最小正数
for i in range(n):
if nums[i] > 0:
return i + 1

return n + 1

矩阵

矩阵乘法

def matrix_mult(a, b):
# 获取矩阵行列数
m = len(a) # a 的行数
n = len(b) # b 的行数 = a 的列数
p = len(b[0]) # b 的列数

# 初始化结果矩阵（全 0）
result = [[0 for _ in range(p)] for _ in range(m)]

# 三重循环计算
for i in range(m):
for j in range(p):
for k in range(n):
result[i][j] += a[i][k] * b[k][j]
return result

73. 矩阵置零

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]] 思路：用第一行和第一列作为标记位。先遍历矩阵，若某个元素为0，则将其所在行首和列首置0，并用两个布尔变量记录第一行/列本身是否含0。然后根据标记将对应行列置零，最后处理第一行/列。

def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
first_row = first_col = False

# 标记
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
if i == 0: first_row = True
if j == 0: first_col = True
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:
for j in range(n):
matrix[0][j] = 0

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

54. 螺旋矩阵

输入：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] 思路：模拟上下左右四个边界。初始化top、bottom、left、right，按右→下→左→上顺序遍历，每走完一条边就收缩对应边界。注意在向左和向上前要检查边界是否合法。

def spiralOrder(matrix):
if not matrix or not matrix[0]:
return []

result = []
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):
result.append(matrix[top][j])
top += 1

# 从上到下
for i in range(top, bottom + 1):
result.append(matrix[i][right])
right -= 1

# 从右到左（需要检查是否还有行）
if top <= bottom:
for j in range(right, left – 1, –1):
result.append(matrix[bottom][j])
bottom -= 1

# 从下到上（需要检查是否还有列）
if left <= right:
for i in range(bottom, top – 1, –1):
result.append(matrix[i][left])
left += 1

return result

48. 旋转图像

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]] 思路：两种方法。①转置+每行反转：先沿主对角线转置，再水平翻转每一行。②直接旋转四个点：按层处理，每层循环交换四个对应位置的元素。

def rotate(matrix):
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)

# 方法1：转置 + 每行反转
# 转置
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 i in range(n):
matrix[i].reverse()

方法2：直接旋转四个点：

def rotate(matrix):
n = len(matrix)

for i in range(n // 2):
for j in range(i, n – i – 1):
# 保存左上角
temp = matrix[i][j]

# 左下 -> 左上
matrix[i][j] = matrix[n – 1 – j][i]
# 右下 -> 左下
matrix[n – 1 – j][i] = matrix[n – 1 – i][n – 1 – j]
# 右上 -> 右下
matrix[n – 1 – i][n – 1 – j] = matrix[j][n – 1 – i]
# 左上 -> 右上
matrix[j][n – 1 – i] = temp

240. 搜索二维矩阵 II

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

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

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true 思路：从右上角开始搜索。若当前值大于target，列左移（这一列下方都更大）；若小于target，行下移（这一行左边都更小）。利用矩阵行列分别递增的特性，每次排除一行或一列。

def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False

m, n = len(matrix), len(matrix[0])
# 从右上角开始
i, j = 0, 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

链表

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

链表问题通用技巧：

使用虚拟头节点(dummy)简化边界处理

快慢指针解决环、中点、倒数第N个等问题

160. 相交链表

def getIntersectionNode(headA, headB):
if not headA or not headB:
return None

pa, pb = headA, headB
while pa != pb:
pa = pa.next if pa else headB
pb = pb.next if pb else headA

return pa

206. 反转链表

def reverseList(head):
prev = None
curr = head

while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp

return prev

递归版：

def reverseList(head):
if not head or not head.next:
return head

new_head = reverseList(head.next)
head.next.next = head
head.next = None

return new_head

234. 回文链表

def isPalindrome(head):
if not head or not head.next:
return True

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

# 反转后半部分
prev = None
while slow:
next_temp = slow.next
slow.next = prev
prev = slow
slow = next_temp

# 比较前后半部分
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next

return True

141. 环形链表

def hasCycle(head):
if not head or not head.next:
return False

slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True

return False

142. 环形链表 II

def detectCycle(head):
if not head or not head.next:
return None

# 判断是否有环
slow = fast = head
has_cycle = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
has_cycle = True
break

if not has_cycle:
return None

# 找环的入口
slow = head
while slow != fast:
slow = slow.next
fast = fast.next

return slow

21. 合并两个有序链表

def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy

while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next

curr.next = l1 or l2
return dummy.next

递归版：

def mergeTwoLists(l1, l2):
if not l1 or not l2:
return l1 or l2

if l1.val <= l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2

2. 两数相加

def addTwoNumbers(l1, l2):
dummy = ListNode(0)
curr = dummy
carry = 0

while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0

total = val1 + val2 + carry
carry = total // 10
curr.next = ListNode(total % 10)
curr = curr.next

if l1: l1 = l1.next
if l2: l2 = l2.next

return dummy.next

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

def removeNthFromEnd(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy

# fast先走n+1步
for i in range(n + 1):
fast = fast.next

# 同时移动，fast到结尾时slow指向待删节点的前一个
while fast:
fast = fast.next
slow = slow.next

slow.next = slow.next.next
return dummy.next

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

def swapPairs(head):
dummy = ListNode(0)
dummy.next = head
prev = dummy

while prev.next and prev.next.next:
# 获取要交换的两个节点
first = prev.next
second = first.next

# 交换
first.next = second.next
second.next = first
prev.next = second

# 移动prev
prev = first

return dummy.next

递归版：

def swapPairs(head):
if not head or not head.next:
return head

new_head = head.next
head.next = swapPairs(new_head.next)
new_head.next = head

return new_head

25. K个一组翻转链表

def reverseKGroup(head, k):
dummy = ListNode(0)
dummy.next = head
prev = dummy

while True:
# 检查剩余节点是否够k个
tail = prev
for i in range(k):
tail = tail.next
if not tail:
return dummy.next

# 记录下一组的起始点
next_group = tail.next

# 翻转当前k个节点
curr = prev.next
prev_next = prev.next
while curr != next_group:
temp = curr.next
curr.next = prev.next
prev.next = curr
curr = temp

prev_next.next = next_group
prev = prev_next

138. 随机链表的复制

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

# 第一步：在每个节点后面复制一个新节点
curr = head
while curr:
new_node = Node(curr.val)
new_node.next = curr.next
curr.next = new_node
curr = new_node.next

# 第二步：复制random指针
curr = head
while curr:
if curr.random:
curr.next.random = curr.random.next
curr = curr.next.next

# 第三步：分离两个链表
dummy = Node(0)
curr_new = dummy
curr = head
while curr:
curr_new.next = curr.next
curr.next = curr.next.next
curr_new = curr_new.next
curr = curr.next

return dummy.next

哈希表法：

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

# 创建原节点到新节点的映射
node_map = {}
curr = head
while curr:
node_map[curr] = Node(curr.val)
curr = curr.next

# 连接next和random指针
curr = head
while curr:
if curr.next:
node_map[curr].next = node_map[curr.next]
if curr.random:
node_map[curr].random = node_map[curr.random]
curr = curr.next

return node_map[head]

148. 排序链表

def sortList(head):
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 = sortList(head)
right = sortList(mid)

# 合并
return merge(left, right)

def merge(l1, l2):
dummy = ListNode(0)
curr = dummy

while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next

curr.next = l1 or l2
return dummy.next

23. 合并K个升序链表

def mergeKLists(lists):
if not lists:
return None

import heapq

# 使用最小堆
dummy = ListNode(0)
curr = dummy
heap = []

# 将每个链表的头节点加入堆
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))

while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next

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

return dummy.next

146. LRU缓存

class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {} # key -> node
self.head = Node(0, 0) # 虚拟头节点
self.tail = Node(0, 0) # 虚拟尾节点
self.head.next = self.tail
self.tail.prev = self.head

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

def put(self, key, value):
if key in self.cache:
self._remove(self.cache[key])

node = Node(key, value)
self.cache[key] = node
self._add(node)

if len(self.cache) > self.capacity:
lru = self.head.next
self._remove(lru)
del self.cache[lru.key]

def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev

def _add(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node

class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None

二叉树

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

94. 二叉树的中序遍历

# 递归
def inorderTraversal(root):
def inorder(node):
if not node:
return
inorder(node.left)
res.append(node.val)
inorder(node.right)

res = []
inorder(root)
return res

# 迭代（栈）
def inorderTraversal(root):
res, stack = [], []
curr = root

while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
res.append(curr.val)
curr = curr.right

return res

104. 二叉树的最大深度

# 递归
def maxDepth(root):
if not root:
return 0
return max(maxDepth(root.left), maxDepth(root.right)) + 1

# 迭代（BFS）
def maxDepth(root):
if not root:
return 0

depth = 0
queue = [root]
while queue:
depth += 1
level_size = len(queue)
for _ in range(level_size):
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth

226. 翻转二叉树

# 递归
def invertTree(root):
if not root:
return None

# 交换左右子树
root.left, root.right = root.right, root.left

# 递归翻转
invertTree(root.left)
invertTree(root.right)

return root

# 迭代
def invertTree(root):
if not root:
return None

queue = [root]
while queue:
node = queue.pop(0)
# 交换
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

return root

101. 对称二叉树

def isSymmetric(root):
if not root:
return True

def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))

return is_mirror(root.left, root.right)

# 迭代
def isSymmetric(root):
if not root:
return True

queue = [(root.left, root.right)]
while queue:
left, right = queue.pop(0)
if not left and not right:
continue
if not left or not right:
return False
if left.val != right.val:
return False

queue.append((left.left, right.right))
queue.append((left.right, right.left))

return True

543. 二叉树的直径

def diameterOfBinaryTree(root):
def depth(node):
nonlocal diameter
if not node:
return 0

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

# 更新直径（经过当前节点的最长路径）
diameter = max(diameter, left_depth + right_depth)

return max(left_depth, right_depth) + 1

diameter = 0
depth(root)
return diameter

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

def sortedArrayToBST(nums):
def build(left, right):
if left > right:
return None

# 选择中间元素作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])

# 递归构建左右子树
root.left = build(left, mid – 1)
root.right = build(mid + 1, right)

return root

return build(0, len(nums) – 1)

图论

200. 岛屿面积

遍历网格中的每个格子，遇到’1’（陆地）时：岛屿计数+1 DFS实现：递归地向上下左右四个方向探索，遇到边界或水就返回，将访问过的陆地置’0’避免重复计数 时间复杂度：O(m×n)，每个格子最多访问一次

def numIslands(grid):
if not grid:
return 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)

m, n = len(grid), len(grid[0])
count = 0

for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)

return count

回溯

46. 全排列

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 思路：交换法回溯。固定第first位，将后面每个元素交换到first位置，递归排列剩余部分，回溯时换回。无需额外空间。

# 交换法（空间优化）
def permute(nums):
def backtrack(first):
# 当 first 指向最后一个位置时，说明得到一个完整排列
if first == len(nums):
res.append(nums[:]) # nums[:] 是当前排列的副本
return

# 将 first 到末尾的每个元素轮流放到 first 位置
for i in range(first, len(nums)):
# 1. 做选择：将 nums[i] 交换到 first 位置
nums[first], nums[i] = nums[i], nums[first]

# 2. 递归：固定 first 位置，排列剩余元素
backtrack(first + 1)

# 3. 撤销选择：恢复原状，以便尝试下一个元素
nums[first], nums[i] = nums[i], nums[first]

res = []
backtrack(0)
return res

78. 子集

输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 思路：回溯遍历所有组合。每个元素有选或不选两种可能，用start控制只能向后选避免重复。迭代法更巧妙：每遇到新元素，就将其加入已有所有子集中。

def subsets(nums):
def backtrack(start, path):
res.append(path[:])

for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()

res = []
backtrack(0, [])
return res

# 迭代法
def subsets(nums):
res = [[]]
for num in nums:
res += [curr + [num] for curr in res]
return res

17. 电话号码的字母组合

输入：digits = “23” 输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 思路：多叉树回溯。按顺序处理每个数字，枚举其对应字母，递归拼接下一数字的字母，长度达标时记录结果。

def letterCombinations(digits):
if not digits:
return []

phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}

def backtrack(index, path):
if index == len(digits):
res.append(''.join(path))
return

for char in phone[digits[index]]:
path.append(char)
backtrack(index + 1, path)
path.pop()

res = []
backtrack(0, [])
return res

39. 组合总和

输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。 思路：排序+回溯剪枝。从start开始选数避免重复组合，因为可重复使用同一元素，所以递归时传i而非i+1，剩余值小于0时剪枝。

def combinationSum(candidates, target):
def backtrack(start, path, remaining):
if remaining == 0:
res.append(path[:])
return
if remaining < 0:
return

for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, remaining – candidates[i])
# 可以重复使用，所以传i
path.pop()

res = []
candidates.sort() # 可选，用于剪枝
backtrack(0, [], target)
return res

22. 括号生成

输入：n = 3 输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 思路：约束条件回溯。维护已用左括号left和右括号right数量，保证right ≤ left ≤ n，左右都用完时记录结果。

def generateParenthesis(n):
def backtrack(left, right, path):
if left == n and right == n:
res.append(''.join(path))
return

if left < n:
path.append('(')
backtrack(left + 1, right, path)
path.pop()

if right < left:
path.append(')')
backtrack(left, right + 1, path)
path.pop()

res = []
backtrack(0, 0, [])
return res

79. 单词搜索

输入：board = [[‘A’,‘B’,‘C’,‘E’],[‘S’,‘F’,‘C’,‘S’],[‘A’,‘D’,‘E’,‘E’]], word = “ABCCED” 输出：true 思路：DFS回溯+原地标记。从每个格子出发尝试匹配单词，匹配成功则向四个方向递归。用临时字符#标记已访问路径，回溯时恢复。

# 优化版（不使用额外visited数组）
def exist(board, word):
def dfs(i, j, index):
if index == len(word):
return True

if (i < 0 or i >= m or j < 0 or j >= n or
board[i][j] != word[index]):
return False

# 临时标记
temp = board[i][j]
board[i][j] = '#'

found = (dfs(i+1, j, index+1) or
dfs(i–1, j, index+1) or
dfs(i, j+1, index+1) or
dfs(i, j–1, index+1))

board[i][j] = temp
return found

m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False

131. 分割回文串

请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 输入：s = “aab” 输出：[[“a”,“a”,“b”],[“aa”,“b”]] 思路：分割点回溯。从start开始尝试不同长度的子串，若是回文则加入路径并递归剩余部分，回溯时移除。

def partition(s):
def is_palindrome(sub):
return sub == sub[::–1]

def backtrack(start, path):
if start == len(s):
res.append(path[:])
return

for end in range(start, len(s)):
if is_palindrome(s[start:end+1]):
path.append(s[start:end+1])
backtrack(end + 1, path)
path.pop()

res = []
backtrack(0, [])
return res

51. N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 输入：n = 4 输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]] 思路：逐行放置+列/对角线约束。用三个数组记录已占用的列、主对角线（row-col恒定）、副对角线（row+col恒定），每行尝试所有列，满足条件则递归下一行。

# 简洁版（用列表代替集合）
def solveNQueens(n):
def backtrack(row):
if row == n:
board = []
for r in range(n):
line = ['.'] * n
line[queens[r]] = 'Q'
board.append(''.join(line))
res.append(board)
return

for col in range(n):
if (col not in cols and
row – col not in diag1 and
row + col not in diag2):

queens[row] = col
cols.append(col)
diag1.append(row – col)
diag2.append(row + col)

backtrack(row + 1)

cols.pop()
diag1.pop()
diag2.pop()

res = []
queens = [–1] * n
cols, diag1, diag2 = [], [], []
backtrack(0)
return res

二分查找

def binary_search(nums, target):
left, right = 0, len(nums) – 1 # 定义target在左闭右闭的区间里

while left <= right: # 当 left == right时，区间[left, right]依然有效
mid = left + (right – left) // 2 # 防止溢出，等同于 (left + right) // 2

if nums[mid] == target:
return mid # 找到目标值，返回下标
elif nums[mid] < target:
left = mid + 1 # target在右半部分，缩小区间为[mid + 1, right]
else:
right = mid – 1 # target在左半部分，缩小区间为[left, mid – 1]

return –1 # 未找到目标值

# 示例
nums = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(nums, target)
print(f"目标值 {target} 的索引是: {index}") # 输出: 目标值 7 的索引是: 3

35. 搜索插入位置

输入: nums = [1,3,5,6], target = 5 输出: 2 输入: nums = [1,3,5,6], target = 2 输出: 1 思路：标准二分查找。找到目标值返回索引，没找到时返回left，此时left指向第一个大于等于target的位置，即插入位置。

def searchInsert(nums, target):
left, right = 0, len(nums) – 1

while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid – 1

return left # 插入位置

74. 搜索二维矩阵

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true 思路：将二维矩阵展开为一维数组进行二分查找。通过mid // n和mid % n将一维索引映射回二维坐标。

def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False

m, n = len(matrix), len(matrix[0])
left, right = 0, m * n – 1

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