树
104. 二叉树的最大深度【简单】
核心思路在于递归，最终深度需要 +1。
class Solution(object):
def maxDepth(self, root):
if root is None:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1
94. 二叉树的中序遍历【简单】
递归实现，列表拼接比 append 更直观。
class Solution(object):
def inorderTraversal(self, root):
if root is None:
return []
# 中序：左 - 根 - 右
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
同理，前序和后序遍历如下：
# 前序：根 - 左 - 右
return [root.val] + self.inorderTraversal(root.left) + self.inorderTraversal(root.right)
# 后序：左 - 右 - 根
return self.inorderTraversal(root.left) + self.inorderTraversal(root.right) + [root.val]
98. 验证二叉搜索树【中等】
利用中序遍历特性，判断序列是否严格单调递增。
class Solution(object):
def isValidBST(self, root):
def solve(node):
if node is None:
return []
return solve(node.left) + [node.val] + solve(node.right)
tree_values = solve(root)
for i in range(len(tree_values) - 1):
if tree_values[i] >= tree_values[i + 1]:
return False
return True
543. 二叉树的直径【简单】
DFS 递归，计算经过当前节点的最长路径。
class Solution(object):
def diameterOfBinaryTree(self, root):
self.ans = 1
def solve(node):
if node is None:
return 0
left_depth = solve(node.left)
right_depth = solve(node.right)
self.ans = max(self.ans, left_depth + right_depth + 1)
return max(left_depth, right_depth) + 1
solve(root)
return self.ans - 1
617. 合并二叉树【简单】
DFS 递归，对应节点值相加。
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
merge_tree = TreeNode(val=root1.val + root2.val)
merge_tree.left = self.mergeTrees(root1.left, root2.left)
merge_tree.right = self.mergeTrees(root1.right, root2.right)
return merge_tree
102. 二叉树的层序遍历【中等】
BFS 模板，用队列存储每一层的节点。注意调试用的 print 语句在实际提交时需删除。
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
ans = []
queue = deque([root])
while queue:
n = len(queue)
cur_level = []
for _ in range(n):
node = queue.popleft()
cur_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(cur_level)
return ans
226. 翻转二叉树【简单】
递归交换左右子节点。
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
return root
236. 二叉树的最近公共祖先【中等】
DFS 递归，寻找包含 p 和 q 的子树。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left:
return right
if not right:
return left
return root
112. 路径总和【简单】
递归检查叶子节点是否满足剩余目标值。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return targetSum == root.val
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
208. 实现 Trie (前缀树)【中等】
标准前缀树模板，使用数组存储子节点指针。
class Trie:
def __init__(self):
self.children = [None] * 26
self.isEnd = False
def searchPrefix(self, prefix: str):
node = self
for c in prefix:
idx = ord(c) - ord('a')
if not node.children[idx]:
return None
node = node.children[idx]
return node
def insert(self, word: str) -> None:
node = self
for c in word:
idx = ord(c) - ord('a')
if not node.children[idx]:
node.children[idx] = Trie()
node = node.children[idx]
node.isEnd = True
def search(self, word: str) -> bool:
node = self.searchPrefix(word)
return node is not None and node.isEnd
def startsWith(self, prefix: str) -> bool:
return self.searchPrefix(prefix) is not None
100. 相同的树【简单】
递归比较两棵树结构及节点值。
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None or q is None:
return p is None and q is None
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
101. 对称二叉树【简单】
递归比较镜像对称的左右子树。
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def helper(p, q):
if not p or not q:
return not p and not q
return p.val == q.val and helper(p.left, q.right) and helper(p.right, q.left)
return helper(root.left, root.right)
199. 二叉树的右视图【中等】
广度优先搜索，取每层最右侧节点。
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue = deque([root])
ans = []
while queue:
n = len(queue)
ans.append(queue[-1].val)
for _ in range(n):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return ans
103. 二叉树的锯齿形层序遍历【中等】
层序遍历基础上增加层索引控制方向。
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = [root]
ans = []
layer_idx = 0
while queue:
n = len(queue)
cur_level = []
for _ in range(n):
node = queue.pop(0)
cur_level.append(node.val)
if layer_idx % 2 == 1:
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
else:
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
ans.append(cur_level)
layer_idx += 1
return ans
124. 二叉树中的最大路径和【困难】
递归计算以当前节点为起点的最大路径，同时更新全局最大值。
class Solution:
def __init__(self):
self.ans = -float('inf')
def maxPathSum(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0
left = max(dfs(node.left), 0)
right = max(dfs(node.right), 0)
cur_sum = node.val + left + right
self.ans = max(self.ans, cur_sum)
return node.val + max(left, right)
dfs(root)
return self.ans
108. 将有序数组转换为二叉搜索树【简单】
递归选取中间元素作为根节点。
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
n = len(nums) // 2
left = self.sortedArrayToBST(nums[:n])
right = self.sortedArrayToBST(nums[n+1:])
return TreeNode(nums[n], left, right)
字符串
20. 有效的括号【简单】
栈匹配，注意空栈判断语法。
class Solution(object):
def isValid(self, s):
if len(s) % 2 == 1:
return False
pairs_dict = {')': '(', '}': '{', ']': '['}
stack = []
for c in s:
if c in pairs_dict:
if not stack or stack[-1] != pairs_dict[c]:
return False
stack.pop()
else:
stack.append(c)
return not stack
32. 最长有效括号【困难】
栈存下标，计算长度差。
class Solution(object):
def longestValidParentheses(self, s):
stack = [-1]
ans = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if stack:
ans = max(ans, i - stack[-1])
else:
stack.append(i)
return ans
647. 回文子串【中等】
中心扩展法，分奇偶长度处理。
class Solution(object):
def countSubstrings(self, s):
n = len(s)
def solve(left, right):
cnt = 0
while 0 <= left < n and 0 <= right < n and s[left] == s[right]:
cnt += 1
left -= 1
right += 1
return cnt
ans = 0
for i in range(n):
ans += solve(i, i)
ans += solve(i, i + 1)
return ans
139. 单词拆分【中等】
动态规划，判断前缀是否可拆且后缀在字典中。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [True] + [False] * n
for i in range(n):
for j in range(i + 1, n + 1):
if dp[i] and s[i:j] in wordDict:
dp[j] = True
return dp[-1]
394. 字符串解码【中等】
双栈或单栈提取字母与数字。
class Solution:
def decodeString(self, s: str) -> str:
stack = []
for c in s:
if c != ']':
stack.append(c)
else:
chars = ''
while stack and stack[-1] != '[':
chars = stack[-1] + chars
stack.pop()
stack.pop() # pop '['
num = ''
while stack and stack[-1].isdigit():
num = stack[-1] + num
stack.pop()
stack.append(int(num) * chars)
return ''.join(stack)
72. 编辑距离【中等】
经典 DP，考虑增删改三种操作。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i
for i in range(n + 1): dp[0][i] = i
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
return dp[m][n]
168. Excel 表列名称【简单】
26 进制转换，注意从 1 开始编码。
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
ans = []
while columnNumber > 0:
columnNumber -= 1
ch = chr(columnNumber % 26 + ord('A'))
ans.append(ch)
columnNumber //= 26
return ''.join(ans[::-1])
415. 字符串相加【简单】
模拟竖式加法，从低位往高位进位。
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
ans = ""
carry = 0
i, j = len(num1) - 1, len(num2) - 1
while i >= 0 or j >= 0 or carry:
x = int(num1[i]) if i >= 0 else 0
y = int(num2[j]) if j >= 0 else 0
s = x + y + carry
ans = str(s % 10) + ans
carry = s // 10
i -= 1
j -= 1
return ans
搜索查找
448. 找到所有数组中消失的数字【简单】
辅助标记数组记录存在性。
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
n = len(nums)
flag = [0] * (n + 1)
for x in nums:
flag[x] = 1
return [i for i in range(1, n + 1) if flag[i] == 0]
136. 只出现一次的数字【简单】
集合去重后计算差值。
class Solution(object):
def singleNumber(self, nums):
nums_set = set(nums)
return sum(nums_set) * 2 - sum(nums)
704. 二分查找【简单】
标准二分模板。
class Solution(object):
def search(self, 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:
right = mid - 1
else:
left = mid + 1
return -1
121. 买卖股票的最佳时机【简单】
一次遍历记录最低点和最大收益。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
122. 买卖股票的最佳时机 II【中等】
贪心累加所有上涨趋势。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
for i in range(1, len(prices)):
ans += max(prices[i] - prices[i - 1], 0)
return ans
169. 多数元素【简单】
哈希统计数量。
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count_dict = {}
for num in nums:
count_dict[num] = count_dict.get(num, 0) + 1
return max(count_dict, key=count_dict.get)
739. 每日温度【中等】
单调栈，从右向左或从左向右均可。
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0] * n
stack = []
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ans
1. 两数之和【简单】
哈希表存储已遍历元素及其索引。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_table = {}
for i, num in enumerate(nums):
diff = target - num
if diff in hash_table:
return [hash_table[diff], i]
hash_table[num] = i
return []
167. 两数之和 II - 输入有序数组【中等】
双指针相向移动。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s < target:
left += 1
elif s > target:
right -= 1
else:
return [left + 1, right + 1]
return []
15. 三数之和【中等】
排序后固定一个元素，双指针找另外两个。
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
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s < 0:
left += 1
elif s > 0:
right -= 1
else:
ans.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
return ans
155. 最小栈【中等】
辅助栈同步存储最小值。
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [float('inf')]
def push(self, val: int) -> None:
self.stack.append(val)
self.min_stack.append(min(self.min_stack[-1], val))
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
347. 前 K 个高频元素【中等】
哈希统计后排序。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
hash_table = {}
for num in nums:
hash_table[num] = hash_table.get(num, 0) + 1
return sorted(hash_table, key=lambda x: hash_table[x], reverse=True)[:k]
287. 寻找重复数【中等】
哈希集检测重复。
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
return -1
42. 接雨水【困难】
双指针维护左右最高点。
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_left, max_right = 0, 0
ans = 0
while left < right:
max_left = max(max_left, height[left])
max_right = max(max_right, height[right])
if max_left < max_right:
ans += max_left - height[left]
left += 1
else:
ans += max_right - height[right]
right -= 1
return ans
11. 盛最多水的容器【中等】
双指针向中间收缩。
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
ans = 0
while left < right:
width = right - left
h = min(height[left], height[right])
ans = max(ans, width * h)
if height[left] < height[right]:
left += 1
else:
right -= 1
return ans
LCR 172. 统计目标成绩的出现次数【简单】
二分法搜索边界。
class Solution:
def countTarget(self, scores: List[int], target: int) -> int:
def helper(target_val):
left, right = 0, len(scores) - 1
while left <= right:
mid = (left + right) // 2
if scores[mid] < target_val:
left = mid + 1
else:
right = mid - 1
return left
return helper(target + 1) - helper(target)
34. 在排序数组中查找元素的第一个和最后一个位置【中等】
同上一题，二分查找边界。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def helper(target_val):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target_val:
left = mid + 1
else:
right = mid - 1
return left
l = helper(target)
r = helper(target + 1)
if r > l:
return [l, r - 1]
return [-1, -1]
1287. 有序数组中出现次数超过 25% 的元素【简单】
哈希计数。
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr)
thre = int(n * 0.25)
hash_table = {}
for a in arr:
hash_table[a] = hash_table.get(a, 0) + 1
if hash_table[a] > thre:
return a
return arr[0]
215. 数组中的第 K 个最大元素【中等】
快速选择算法思想。
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
import random
def quick_select(nums, k):
pivot = random.choice(nums)
big, equal, small = [], [], []
for x in nums:
if x > pivot: big.append(x)
elif x < pivot: small.append(x)
else: equal.append(x)
if len(big) >= k:
return quick_select(big, k)
if len(big) + len(equal) < k:
return quick_select(small, k - len(big) - len(equal))
return pivot
return quick_select(nums, k)
209. 长度最小的子数组【中等】
滑动窗口，枚举右端点收缩左端点。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
ans = n + 1
s = 0
left = 0
for right, x in enumerate(nums):
s += x
while s >= target:
ans = min(ans, right - left + 1)
s -= nums[left]
left += 1
return ans if ans <= n else 0
76. 最小覆盖子串【困难】
滑动窗口配合字符计数器。
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import Counter
cnt_win = Counter()
cnt_t = Counter(t)
ans_left, ans_right = -float('inf'), float('inf')
left = 0
for right, x in enumerate(s):
cnt_win[x] += 1
while cnt_win >= cnt_t:
if right - left < ans_right - ans_left:
ans_left, ans_right = left, right
cnt_win[s[left]] -= 1
left += 1
return s[ans_left:ans_right + 1] if ans_left >= 0 else ""
3. 无重复字符的最长子串【中等】
滑动窗口维护不重复集合。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
ans = 0
visited = set()
left = 0
for right, x in enumerate(s):
while x in visited:
visited.remove(s[left])
left += 1
visited.add(x)
ans = max(ans, right - left + 1)
return ans
排列
冒泡排序【排序模板】
O(n^2) 基础排序。
class Solution(object):
def sortArray(self, nums):
n = len(nums)
for i in range(1, n):
for j in range(0, n - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
快速排序【排序模板】
分治策略，随机基准点。
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
import random
def partition(arr, low, high):
r = random.randint(low, high)
arr[r], arr[high] = arr[high], arr[r]
pivot = arr[high]
slow = fast = low
while fast <= high:
if arr[fast] < pivot:
arr[fast], arr[slow] = arr[slow], arr[fast]
slow += 1
fast += 1
arr[high], arr[slow] = arr[slow], arr[high]
return slow
def quicksort(arr, low, high):
if low < high:
pivot_idx = partition(arr, low, high)
quicksort(arr, low, pivot_idx - 1)
quicksort(arr, pivot_idx + 1, high)
return arr
return quicksort(nums, 0, len(nums) - 1)
283. 移动零【简单】
双指针保持非零元素相对顺序。
class Solution(object):
def moveZeroes(self, nums):
left = 0
for right in range(len(nums)):
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
return nums
75. 颜色分类【中等】
三指针分区。
class Solution:
def sortColors(self, nums: List[int]) -> None:
n = len(nums)
p0, p2 = 0, n - 1
i = 0
while i <= p2:
if nums[i] == 2:
nums[i], nums[p2] = nums[p2], nums[i]
p2 -= 1
elif nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
p0 += 1
i += 1
else:
i += 1
406. 根据身高重建队列【中等】
先按身高降序、k 升序排序，再插入。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x: (-x[0], x[1]))
ans = []
for person in people:
ans.insert(person[1], person)
return ans
977. 有序数组的平方【简单】
双指针从两端向中间比较平方值。
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
left, right = 0, n - 1
ans = []
while left <= right:
if nums[left]**2 <= nums[right]**2:
ans.append(nums[right]**2)
right -= 1
else:
ans.append(nums[left]**2)
left += 1
return ans[::-1]
31. 下一个排列【中等】
从右向左找第一个较小元素，交换后反转右侧。
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
组合
49. 字母异位词分组【中等】
排序后作为 Key 分组。
class Solution(object):
def groupAnagrams(self, strs):
d = {}
for s in strs:
sorted_s = ''.join(sorted(s))
d[sorted_s] = d.get(sorted_s, []) + [s]
return list(d.values())
78. 子集【中等】
迭代构建子集。
class Solution(object):
def subsets(self, nums):
ans = [[]]
for num in nums:
tmp = []
for i in ans:
tmp.append([num] + i)
ans += tmp
return ans
46. 全排列【中等】
回溯法交换元素。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
def dfs(start):
if start == n:
ans.append(nums[:])
return
for i in range(start, n):
nums[i], nums[start] = nums[start], nums[i]
dfs(start + 1)
nums[i], nums[start] = nums[start], nums[i]
dfs(0)
return ans
47. 全排列 II【中等】
回溯法加剪枝去重。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
def dfs(start):
if start == n:
ans.append(nums[:])
return
dic = set()
for i in range(start, n):
if nums[i] in dic:
continue
dic.add(nums[i])
nums[i], nums[start] = nums[start], nums[i]
dfs(start + 1)
nums[i], nums[start] = nums[start], nums[i]
dfs(0)
return ans
LCR 157. 套餐内商品的排列顺序【中等】
字符串转列表回溯。
class Solution:
def goodsOrder(self, goods: str) -> List[str]:
n = len(goods)
lst = list(goods)
ans = []
def dfs(start):
if start == n:
ans.append(''.join(lst))
return
for i in range(start, n):
lst[i], lst[start] = lst[start], lst[i]
dfs(start + 1)
lst[i], lst[start] = lst[start], lst[i]
dfs(0)
return list(set(ans))
链表
206. 反转链表【简单】
双指针原地反转。
class Solution(object):
def reverseList(self, head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
92. 反转链表 II【中等】
加入哨兵节点定位区间。
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if not head:
return None
dummy = ListNode(next=head)
p0 = dummy
for _ in range(left - 1):
p0 = p0.next
cur, prev = p0.next, None
for _ in range(right - left + 1):
next_node = cur.next
cur.next = prev
prev = cur
cur = next_node
p0.next.next = cur
p0.next = prev
return dummy.next
234. 回文链表【简单】
转列表判断回文。
class Solution(object):
def isPalindrome(self, head):
l = []
while head:
l.append(head.val)
head = head.next
return l == l[::-1]
160. 相交链表【简单】
哈希存储一条链表的节点。
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
link_set = set()
cur = headA
while cur:
link_set.add(cur)
cur = cur.next
cur = headB
while cur:
if cur in link_set:
return cur
cur = cur.next
return None
141. 环形链表【简单】
快慢指针追及问题。
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head:
return False
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
142. 环形链表 II【中等】
快慢指针相遇后重置一指针找入口。
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None
tmp = head
while tmp != slow:
tmp = tmp.next
slow = slow.next
return slow
148. 排序链表【中等】
归并排序。
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)
ans = ListNode()
cur = ans
while left and right:
if left.val < right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
if left:
cur.next = left
elif right:
cur.next = right
return ans.next
237. 删除链表中的节点【中等】
直接复制后继节点值。
class Solution:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
19. 删除链表的倒数第 N 个节点【中等】
双指针保持距离。
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(next=head)
right = dummy
for _ in range(n):
right = right.next
left = dummy
while right.next:
left = left.next
right = right.next
left.next = left.next.next
return dummy.next
83. 删除排序链表中的重复元素【简单】
跳过相同值节点。
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
cur = head
while cur.next:
if cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
82. 删除排序链表中的重复元素 II【中等】
哨兵节点处理头节点删除。
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(next=head)
cur = dummy
while cur.next and cur.next.next:
if cur.next.next.val == cur.next.val:
val = cur.next.val
while cur.next and cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
203. 移除链表元素【简单】
哨兵节点迭代判断。
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if not head:
return None
dummy = ListNode(next=head)
cur = dummy
while cur and cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
2. 两数相加【中等】
参照字符串加法模板。
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
ans = ListNode(0)
cur = ans
carry = 0
while l1 or l2:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
s = x + y + carry
cur.next = ListNode(s % 10)
cur = cur.next
carry = s // 10
if l1: l1 = l1.next
if l2: l2 = l2.next
if carry:
cur.next = ListNode(carry)
return ans.next
21. 合并两个有序链表【简单】
双指针取小值。
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1 and not list2:
return None
ans = ListNode()
cur = ans
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
if list1:
cur.next = list1
elif list2:
cur.next = list2
return ans.next
23. 合并 K 个升序链表【困难】
分治两两合并。
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwoLists(l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1: cur.next = l1
elif l2: cur.next = l2
return dummy.next
if not lists:
return None
if len(lists) == 1:
return lists[0]
mid = len(lists) // 2
left = self.mergeKLists(lists[:mid])
right = self.mergeKLists(lists[mid:])
return mergeTwoLists(left, right)
位运算
461. 汉明距离【简单】
异或后统计 1 的个数。
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
xor = x ^ y
dist = 0
for i in range(32):
if (xor >> i) & 1:
dist += 1
return dist
338. 比特位计数【简单】
转二进制计数。
class Solution(object):
def countBits(self, n):
ans = []
for i in range(n + 1):
ans.append(bin(i).count('1'))
return ans
191. 位 1 的个数【简单】
逐位判断。
class Solution:
def hammingWeight(self, n: int) -> int:
one_bit = 0
for i in range(32):
if n & (1 << i):
one_bit += 1
return one_bit
231. 2 的幂【简单】
判断二进制中 1 的个数。
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n <= 0:
return False
return bin(n).count('1') == 1
数组计算
238. 除自身以外数组的乘积【中等】
前缀乘积与后缀乘积。
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
front_mul = [1] * n
behind_mul = [1] * n
for i in range(1, n):
front_mul[i] = front_mul[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
behind_mul[i] = behind_mul[i + 1] * nums[i + 1]
return [front_mul[i] * behind_mul[i] for i in range(n)]
152. 乘积最大子数组【中等】
同时维护最大和最小乘积。
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
cur_max = [0] * n
cur_min = [0] * n
ans = nums[0]
cur_max[0], cur_min[0] = nums[0], nums[0]
for i in range(1, n):
cur_max[i] = max(nums[i] * cur_min[i - 1], nums[i] * cur_max[i - 1], nums[i])
cur_min[i] = min(nums[i] * cur_min[i - 1], nums[i] * cur_max[i - 1], nums[i])
ans = max(ans, cur_max[i])
return ans
53. 最大子数组和【中等】
经典 DP 模板。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
dp[i] = max(nums[i], dp[i - 1] + nums[i])
return max(dp)
300. 最长递增子序列【中等】
DP 状态转移。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 1
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
128. 最长连续序列【中等】
哈希集合查找连续序列。
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
hash_set = set(nums)
ans = 0
for num in hash_set:
if num - 1 not in hash_set:
length_from_here = 1
cur_num = num
while cur_num + 1 in hash_set:
cur_num += 1
length_from_here += 1
ans = max(ans, length_from_here)
return ans
438. 找到字符串中所有字母异位词【中等】
滑动窗口字符统计。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
window_size = len(p)
n = len(s)
ans = []
window_cnt = [0] * 26
p_cnt = [0] * 26
for c in p:
p_cnt[ord(c) - ord('a')] += 1
for c in s[:window_size]:
window_cnt[ord(c) - ord('a')] += 1
if p_cnt == window_cnt:
ans.append(0)
for i in range(1, n - window_size + 1):
left_del_char, right_new_char = s[i - 1], s[i + window_size - 1]
window_cnt[ord(left_del_char) - ord('a')] -= 1
window_cnt[ord(right_new_char) - ord('a')] += 1
if p_cnt == window_cnt:
ans.append(i)
return ans
989. 数组形式的整数加法【简单】
逐位计算模板。
class Solution:
def addToArrayForm(self, num: List[int], k: int) -> List[int]:
n = len(num)
i = n - 1
carry = 0
ans = []
while i >= 0 or k != 0:
x = num[i] if i >= 0 else 0
y = k % 10 if k != 0 else 0
s = x + y + carry
ans.append(s % 10)
carry = s // 10
i -= 1
k //= 10
if carry:
ans.append(carry)
return ans[::-1]
119. 杨辉三角 II【简单】
递推每行值。
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
row_num = rowIndex + 1
T = [[1] * (i + 1) for i in range(row_num)]
for i in range(row_num):
for j in range(1, i):
T[i][j] = T[i - 1][j - 1] + T[i - 1][j]
return T[rowIndex]
198. 打家劫舍【中等】
DP 状态转移。
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
if n == 2:
return max(nums[0], nums[1])
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
213. 打家劫舍 II【中等】
分情况讨论首尾不可同时偷。
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
if n == 2:
return max(nums[0], nums[1])
dp1 = [0] * n
dp1[0] = nums[0]
dp1[1] = max(nums[0], nums[1])
for i in range(2, n - 1):
dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i])
ans1 = dp1[-2]
dp2 = [0] * n
dp2[1] = nums[1]
dp2[2] = max(nums[1], nums[2])
for i in range(3, n):
dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i])
ans2 = dp2[-1]
return max(ans1, ans2)
337. 打家劫舍 III【中等】
树形 DP。
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0, 0
left_rob, left_not_rob = dfs(node.left)
right_rob, right_not_rob = dfs(node.right)
cur_rob = node.val + left_not_rob + right_not_rob
cur_not_rob = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)
return cur_rob, cur_not_rob
return max(dfs(root))
239. 滑动窗口最大值【困难】
单调队列。
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
ans = []
q = deque()
for i, x in enumerate(nums):
while q and x >= nums[q[-1]]:
q.pop()
q.append(i)
if i - q[0] >= k:
q.popleft()
if i >= k - 1:
ans.append(nums[q[0]])
return ans
56. 合并区间【中等】
排序后合并重叠区间。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda p: p[0])
ans = []
for p in intervals:
if ans and p[0] <= ans[-1][1]:
ans[-1][1] = max(p[1], ans[-1][1])
else:
ans.append(p)
return ans
494. 目标和【中等】
0-1 背包问题转化。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
if (target + total) % 2 != 0 or abs(target) > total:
return 0
target = (total + target) // 2
@cache
def dfs(i, t):
if i < 0:
return 1 if t == 0 else 0
if nums[i] > t:
return dfs(i - 1, t)
return dfs(i - 1, t) + dfs(i - 1, t - nums[i])
return dfs(len(nums) - 1, target)
322. 零钱兑换【中等】
完全背包 DP。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
@cache
def dfs(i, t):
if i < 0:
return 0 if t == 0 else float('inf')
if coins[i] > t:
return dfs(i - 1, t)
return min(dfs(i - 1, t), dfs(i, t - coins[i]) + 1)
ans = dfs(len(coins) - 1, amount)
return ans if ans < float('inf') else -1
数据结构设计
380. O(1) 时间插入、删除和获取随机元素【中等】
哈希表记录索引，列表支持随机访问。
class RandomizedSet:
def __init__(self):
self.nums = []
self.hash = {}
def insert(self, val: int) -> bool:
if val not in self.hash:
self.nums.append(val)
self.hash[val] = len(self.nums) - 1
return True
return False
def remove(self, val: int) -> bool:
if val in self.hash:
index = self.hash[val]
last_val = self.nums[-1]
self.nums[index] = last_val
self.hash[last_val] = index
del self.hash[val]
self.nums.pop()
return True
return False
def getRandom(self) -> int:
import random
return random.choice(self.nums)
146. LRU 缓存【中等】
字典 + 双向链表（或使用 OrderedDict）。
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> value
self.order = [] # 记录访问顺序
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.order.remove(key)
self.order.append(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.order.remove(key)
self.cache[key] = value
self.order.append(key)
if len(self.cache) > self.capacity:
oldest = self.order.pop(0)
del self.cache[oldest]
矩阵
200. 岛屿数量【中等】
DFS 遍历连通区域。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(grid, r, c):
rows, cols = len(grid), len(grid[0])
if r < 0 or r > rows - 1 or c < 0 or c > cols - 1 or grid[r][c] != '1':
return
grid[r][c] = '2'
dfs(grid, r + 1, c)
dfs(grid, r - 1, c)
dfs(grid, r, c + 1)
dfs(grid, r, c - 1)
rows, cols = len(grid), len(grid[0])
ans = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(grid, r, c)
ans += 1
return ans
221. 最大正方形【中等】
DP 记录边长。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
rows, cols = len(matrix), len(matrix[0])
if rows == 0 or cols == 0:
return 0
dp = [[0] * cols for _ in range(rows)]
max_side = 0
for i in range(rows):
for j in range(cols):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
max_side = max(max_side, dp[i][j])
return max_side ** 2
73. 矩阵置零【中等】
两次遍历标记行列。
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
rows, cols = len(matrix), len(matrix[0])
row_flag, col_flag = [0] * rows, [0] * cols
for r in range(rows):
for c in range(cols):
if matrix[r][c] == 0:
row_flag[r] = 1
col_flag[c] = 1
for r in range(rows):
for c in range(cols):
if row_flag[r] or col_flag[c]:
matrix[r][c] = 0
48. 旋转图像【中等】
水平翻转 + 主对角线翻转。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
for i in range(n // 2):
for j in range(n):
matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
for i in range(n):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
867. 转置矩阵【简单】
行列交换。
class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
rows, cols = len(matrix), len(matrix[0])
ans = [[0] * rows for _ in range(cols)]
for i in range(rows):
for j in range(cols):
ans[j][i] = matrix[i][j]
return ans
数学计算
69. x 的平方根【简单】
二分法或牛顿迭代。
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
left, right = 1, x
ans = 1
while left <= right:
mid = (left + right) // 2
if mid * mid <= x:
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
343. 整数拆分【中等】
DP 分解乘积。
class Solution:
def integerBreak(self, n: int) -> int:
if n == 1:
return 1
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
return dp[n]
263. 丑数【简单】
循环除因子。
class Solution:
def isUgly(self, n: int) -> bool:
if n <= 0:
return False
for p in [2, 3, 5]:
while n % p == 0:
n //= p
return n == 1
264. 丑数 II【中等】
三指针生成丑数。
class Solution:
def nthUglyNumber(self, n: int) -> int:
a = [0] * (n + 1)
a[1] = 1
p2, p3, p5 = 1, 1, 1
for i in range(2, n + 1):
num2, num3, num5 = a[p2] * 2, a[p3] * 3, a[p5] * 5
a[i] = min(num2, num3, num5)
if a[i] == num2: p2 += 1
if a[i] == num3: p3 += 1
if a[i] == num5: p5 += 1
return a[n]
258. 各位相加【简单】
数根性质模 9。
class Solution:
def addDigits(self, num: int) -> int:
if num == 0:
return 0
return (num - 1) % 9 + 1
202. 快乐数【简单】
哈希检测环或快慢指针。
class Solution:
def isHappy(self, n: int) -> bool:
def compute_next(n):
total = 0
while n > 0:
digit = n % 10
total += digit ** 2
n //= 10
return total
slow, fast = n, compute_next(n)
while True:
if slow == fast:
return False
if fast == 1:
return True
slow = compute_next(slow)
fast = compute_next(compute_next(fast))
图
207. 课程表【中等】
DFS 判断是否有环。
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
for a, b in prerequisites:
graph[b].append(a)
states = [0] * numCourses
def dfs(x):
states[x] = 1
for node in graph[x]:
if states[node] == 1 or (states[node] == 0 and dfs(node)):
return True
states[x] = 2
return False
for i in range(numCourses):
if states[i] == 0 and dfs(i):
return False
return True
64. 最小路径和【中等】
DP 累加最小路径。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
for i in range(1, rows):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for j in range(1, cols):
dp[0][j] = dp[0][j - 1] + grid[0][j]
for i in range(1, rows):
for j in range(1, cols):
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
return dp[rows - 1][cols - 1]