本手册精选 35 道大厂面试最常考的手写算法题，按题型分类，每题提供：思路解析、Python 模板代码、手写易错点。建议配合刷题使用，面试前一周快速过一遍。
一、链表操作
链表题的核心：画图 + 虚拟头节点 + 快慢指针。面试中 90% 的链表题都能用这三个技巧解决。
1. 反转链表（LC 206）⭐ 最高频
思路：用三个指针 prev、curr、next_node 依次翻转每个节点的指向。
def reverseList(head):
prev = None
curr = head
while curr:
next_node = curr.next # 先存下一个节点
curr.next = prev # 翻转指针
prev = curr # prev 前进
curr = next_node # curr 前进
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
易错点：
- 必须先存
next_node = curr.next，否则链表断了就找不回来 - 循环结束时返回
prev，不是curr（此时 curr 是 None）
2. 环形链表（LC 141）
思路：快慢指针。慢指针每次走 1 步，快指针每次走 2 步。如果有环，快慢指针终会相遇。
def hasCycle(head):
slow = fast = head
while fast and fast.next: # 注意要判断 fast.next
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
进阶（LC 142）：找到环的入口节点
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# 从头开始走，与慢指针相遇处即入口
slow2 = head
while slow != slow2:
slow = slow.next
slow2 = slow2.next
return slow
return None
数学证明（面试加分项）：设头到入口距离 a，入口到相遇点 b，环长 c。相遇时慢指针走了 a+b，快指针走了 a+b+nc。因为快是慢的两倍：2(a+b) = a+b+nc，所以 a = nc-b = (n-1)c + (c-b)。即从头走 a 步 = 从相遇点走 c-b 步，两者在入口相遇。
3. 合并两个有序链表（LC 21）
思路：用虚拟头节点 dummy，依次比较两个链表的节点，接到结果链表后面。
def mergeTwoLists(l1, l2):
dummy = curr = ListNode(0)
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
易错点：l1 or l2 是 Python 的优雅写法，等同于"哪个不为 None 就接哪个"。
4. 两数相加（LC 2）
思路：模拟加法，注意进位。
def addTwoNumbers(l1, l2):
dummy = curr = ListNode(0)
carry = 0
while l1 or l2 or carry:
val = carry
if l1:
val += l1.val
l1 = l1.next
if l2:
val += l2.val
l2 = l2.next
carry, val = divmod(val, 10)
curr.next = ListNode(val)
curr = curr.next
return dummy.next
易错点：循环条件要包含 carry，否则最后进位会丢失（如 5+5=10，个位0进位1，需要新建节点）。
5. 删除链表倒数第 N 个节点（LC 19）
思路：快慢指针。让快指针先走 n+1 步，然后快慢一起走。快指针到尾时，慢指针正好在要删除节点的前一个。
def removeNthFromEnd(head, n):
dummy = ListNode(0, head) # 虚拟头节点，处理删除头节点的情况
fast = slow = dummy
for _ in range(n + 1): # 快指针先走 n+1 步
fast = fast.next
while fast: # 一起走
fast = fast.next
slow = slow.next
slow.next = slow.next.next # 删除 slow 的下一个节点
return dummy.next
易错点：
- 用虚拟头节点是为了处理"删除头节点"的边界情况
- 快指针先走
n+1步（不是 n 步），这样慢指针停在待删节点的前一个
6. 合并 K 个排序链表（LC 23）⭐
思路：用最小堆，把每条链表的头节点放入堆中，每次取出最小的，然后把它的 next 放入堆。
import heapq
def mergeKLists(lists):
dummy = curr = ListNode(0)
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) # i 用于打破相同时的比较
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
易错点：元组中加 i 是因为 ListNode 不支持比较，当 val 相同时会比较第二个元素 i（整数可以比较）。
复杂度：O(N log K)，N 是所有节点总数，K 是链表数。
二、二叉树
二叉树题的核心：递归思维 + 左右子树分别处理。80% 的树题都是后序遍历的变体。
7. 二叉树的层序遍历（LC 102）⭐
思路：BFS，用队列。每次处理一层的所有节点。
from collections import deque
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # 关键：先记录当前层节点数
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
易错点：必须在循环开头用 level_size = len(queue) 固定当前层的大小，不能在 for 循环中用 len(queue)（因为队列在变化）。
8. 二叉树的最大深度（LC 104）
思路：递归，左右子树深度的最大值 + 1。
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))
三行代码，但面试中可能要你写非递归版（BFS）：
def maxDepth(root):
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
9. 从前序与中序遍历序列构造二叉树（LC 105）⭐
思路：前序的第一个元素是根，在中序中找到它，左边是左子树，右边是右子树。递归构造。
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val) # 根在中序中的位置
root.left = buildTree(preorder[1:mid + 1], inorder[:mid])
root.right = buildTree(preorder[mid + 1:], inorder[mid + 1:])
return root
优化版（用哈希表加速查找，O(n) 时间）：
def buildTree(preorder, inorder):
index_map = {val: i for i, val in enumerate(inorder)}
def build(pre_left, pre_right, in_left, in_right):
if pre_left > pre_right:
return None
root_val = preorder[pre_left]
root = TreeNode(root_val)
mid = index_map[root_val]
left_size = mid - in_left
root.left = build(pre_left + 1, pre_left + left_size, in_left, mid - 1)
root.right = build(pre_left + left_size + 1, pre_right, mid + 1, in_right)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)
易错点：左子树大小 = mid - in_left（不是 mid），这个值决定了前序中左右子树的分界。
10. 翻转二叉树（LC 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
11. 对称二叉树（LC 101）
思路：递归比较左子树的左孩子与右子树的右孩子、左子树的右孩子与右子树的左孩子。
def isSymmetric(root):
def isMirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
isMirror(left.left, right.right) and
isMirror(left.right, right.left))
return isMirror(root.left, root.right) if root else True
12. 二叉树的最近公共祖先（LC 236）⭐
思路：后序遍历。如果当前节点是 p 或 q，返回当前节点。否则递归左右子树：
- 左右都返回非空 → 当前节点就是 LCA
- 只有一边返回非空 → LCA 在那一边
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right: # p 和 q 分别在两侧
return root
return left or right # 都在同一侧，返回非空的那个
为什么这个代码是对的？（面试要能解释）：后序遍历先处理子树再处理根。如果某个节点的左右子树分别找到了 p 和 q，说明它就是 LCA。如果只在一边找到，说明两个节点都在那一边，返回那一边的结果。
13. 二叉搜索树的第 K 小元素（LC 230）
思路：BST 的中序遍历是升序的，遍历到第 k 个就是答案。
def kthSmallest(root, k):
stack = []
curr = root
while stack or curr:
while curr: # 一路往左走到底
stack.append(curr)
curr = curr.left
curr = stack.pop()
k -= 1
if k == 0:
return curr.val
curr = curr.right
易错点：用迭代中序遍历，避免递归无法中途返回的问题。
三、二分查找
二分查找的核心：确定搜索区间 + 循环不变量。三种模板覆盖 95% 的二分题。
14. 二分查找（LC 704）
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right: # <= 保证 left == right 时也能检查
mid = left + (right - left) // 2 # 防溢出
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
易错点：
left <= right不是left < right（闭区间写法）mid = left + (right - left) // 2防溢出（虽然 Python 不需要，但面试时写上体现工程素养）
15. 搜索旋转排序数组（LC 33）⭐
思路：旋转数组的特点是，mid 的左边或右边至少有一半是有序的。判断哪半有序，再看 target 是否在那半范围内。
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# 左半有序
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]: # target 在左半
right = mid - 1
else:
left = mid + 1
# 右半有序
else:
if nums[mid] < target <= nums[right]: # target 在右半
left = mid + 1
else:
right = mid - 1
return -1
易错点：nums[left] <= nums[mid] 用的是 <=（不是 <），因为 left == mid 时也算"左半有序"（只有一个元素）。
16. 在排序数组中查找元素的第一个和最后一个位置（LC 34）
思路：用两次二分查找分别找左边界和右边界。
def searchRange(nums, target):
def findBound(is_left):
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
result = mid
if is_left:
right = mid - 1 # 继续往左找
else:
left = mid + 1 # 继续往右找
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
return [findBound(True), findBound(False)]
技巧：用 is_left 参数复用同一份二分代码，避免写两遍。
17. 寻找旋转排序数组中的最小值（LC 153）
def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]: # 最小值在右半
left = mid + 1
else: # 最小值在左半（含 mid）
right = mid
return nums[left]
注意：这里用 left < right（不是 <=），循环结束时 left == right，即指向最小值。
四、双指针与滑动窗口
18. 无重复字符的最长子串（LC 3）⭐
思路：滑动窗口 + 哈希集合。右指针扩展，遇到重复就收缩左指针。
def lengthOfLongestSubstring(s):
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set: # 遇到重复字符
char_set.remove(s[left]) # 收缩左边界
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
优化版（用字典记录字符位置，可以直接跳过）：
def lengthOfLongestSubstring(s):
char_index = {}
left = 0
max_len = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1 # 直接跳到重复字符的下一个位置
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
易错点：char_index[char] >= left 这个条件很关键——只有当重复字符在当前窗口内才需要移动左指针。
19. 盛最多水的容器（LC 11）
思路：左右双指针，每次移动较矮的那个（因为面积取决于短边，移动高的只会让面积更小或不变）。
def maxArea(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = (right - left) * min(height[left], height[right])
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
20. 三数之和（LC 15）⭐
思路：排序 + 固定一个数 + 双指针找另外两个。
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]: # 去重
continue
if nums[i] > 0: # 优化：第一个数 > 0 不可能三数和为 0
break
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.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 result
易错点：
- 去重是这道题的难点，三个地方都要去重（i 去重、left 去重、right 去重）
nums[i] > 0时直接 break 是重要优化
21. 接雨水（LC 42）⭐⭐ 超高频
思路一：双指针（最优解）
对于每个位置，能接的水量 = min(左边最高, 右边最高) - 当前高度。用左右指针从两端向中间推进。
def trap(height):
if not height:
return 0
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
if left_max < right_max:
water += left_max - height[left]
left += 1
else:
water += right_max - height[right]
right -= 1
return water
思路二：单调栈（面试常考变体）
def trap(height):
stack = [] # 存下标，对应高度递减
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = height[stack.pop()] # 凹底
if not stack:
break
width = i - stack[-1] - 1
water += width * (min(height[stack[-1]], h) - bottom)
stack.append(i)
return water
五、动态规划
DP 题核心三步：定义状态 → 写转移方程 → 确定初始值和遍历顺序。
22. 爬楼梯（LC 70）
def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
空间优化（只保留前两个状态）：
def climbStairs(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b
23. 最长递增子序列（LC 300）⭐
思路一：DP，O(n²)
dp[i] = 以 nums[i] 结尾的最长递增子序列长度。
def lengthOfLIS(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
思路二：贪心 + 二分，O(n log n)（面试加分）
维护一个数组 tails，tails[i] 表示长度为 i+1 的递增子序列的最小结尾元素。
import bisect
def lengthOfLIS(nums):
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
手动二分版本（面试不让用库函数时）：
def lengthOfLIS(nums):
tails = []
for num in nums:
left, right = 0, len(tails)
while left < right:
mid = left + (right - left) // 2
if tails[mid] < num:
left = mid + 1
else:
right = mid
if left == len(tails):
tails.append(num)
else:
tails[left] = num
return len(tails)
24. 零钱兑换（LC 322）
思路：完全背包问题。dp[i] = 凑成金额 i 所需的最少硬币数。
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
易错点：初始值用 float('inf') 而不是 0，因为要求最小值。最后要判断是否可达。
25. 最长公共子序列（LC 1143）
思路：经典二维 DP。
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
状态转移解释：
text1[i-1] == text2[j-1]：两个字符相同，LCS 长度 = 去掉这两个字符后的 LCS + 1- 否则：取"去掉 text1 的字符"和"去掉 text2 的字符"中的较大值
26. 编辑距离（LC 72）⭐
思路：与 LCS 类似的二维 DP，dp[i][j] = 将 word1[:i] 变为 word2[:j] 的最少操作数。
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始值：空串变到长度为 k 的串需要 k 步
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
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] = 1 + min(
dp[i - 1][j], # 删除
dp[i][j - 1], # 插入
dp[i - 1][j - 1] # 替换
)
return dp[m][n]
面试加分：能解释为什么删除对应 dp[i-1][j]、插入对应 dp[i][j-1]、替换对应 dp[i-1][j-1]。
27. 最长回文子串（LC 5）⭐
思路一：中心扩展（推荐，面试最好写）
def longestPalindrome(s):
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right] # 注意切片范围
result = ""
for i in range(len(s)):
# 奇数长度回文（以 i 为中心）
odd = expand(i, i)
# 偶数长度回文（以 i 和 i+1 为中心）
even = expand(i, i + 1)
result = max(result, odd, even, key=len)
return result
思路二：DP
def longestPalindrome(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
result = ""
for i in range(n - 1, -1, -1): # 从后往前遍历
for j in range(i, n):
dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i + 1][j - 1])
if dp[i][j] and j - i + 1 > len(result):
result = s[i:j + 1]
return result
六、回溯法
回溯模板：
def backtrack(path, choices):
if 满足结束条件:
result.append(path[:]) # 注意要拷贝！
return
for choice in choices:
path.append(choice) # 做选择
backtrack(path, choices)
path.pop() # 撤销选择
28. 全排列（LC 46）
def permute(nums):
result = []
def backtrack(path):
if len(path) == len(nums):
result.append(path[:]) # 必须拷贝！否则引用会被修改
return
for num in nums:
if num in path:
continue
path.append(num)
backtrack(path)
path.pop()
backtrack([])
return result
优化版（用 visited 数组避免 in 查找）：
def permute(nums):
result = []
visited = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if visited[i]:
continue
visited[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
visited[i] = False
backtrack([])
return result
29. 子集（LC 78）
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:]) # 每个子集都要收集（包括空集）
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path) # 从 i+1 开始，避免重复
path.pop()
backtrack(0, [])
return result
与全排列的区别：子集用 start 参数控制起点，排列用 visited 控制访问。
30. N 皇后（LC 51）⭐
思路：逐行放置皇后，用三个集合记录列、正对角线、反对角线的占用情况。
def solveNQueens(n):
result = []
cols = set()
diag1 = set() # 行 - 列 相同 → 同一正对角线
diag2 = set() # 行 + 列 相同 → 同一反对角线
def backtrack(row, path):
if row == n:
result.append(["." * c + "Q" + "." * (n - c - 1) for c in path])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
path.append(col)
backtrack(row + 1, path)
path.pop()
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0, [])
return result
关键技巧：用 row - col 和 row + col 标识对角线，这是面试中的高频考点。
七、BFS/DFS
31. 岛屿数量（LC 200）⭐
思路：遍历网格，遇到 ‘1’ 就计数，然后 DFS/BFS 把相连的 ‘1’ 都标记为 ‘0’。
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0' # 标记为已访问（沉岛）
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
BFS 版本（面试官可能要求避免递归深度问题）：
from collections import deque
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
grid[r][c] = '0'
queue = deque([(r, c)])
while queue:
cr, cc = queue.popleft()
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
grid[nr][nc] = '0'
queue.append((nr, nc))
return count
32. 单词接龙（LC 127）
思路：BFS 求最短路径。每次变换一个字母，看在单词表中是否存在。
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
while queue:
word, length = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i + 1:]
if new_word == endWord:
return length + 1
if new_word in word_set:
word_set.remove(new_word) # 标记已访问
queue.append((new_word, length + 1))
return 0
八、栈与队列
33. 有效的括号（LC 20）
def isValid(s):
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping: # 右括号
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else: # 左括号
stack.append(char)
return len(stack) == 0 # 栈必须为空
34. 用两个栈实现队列（LC 232 / 剑指 Offer 09）
思路：一个栈负责入队（stack_in），一个栈负责出队（stack_out）。出队时如果 stack_out 为空，就把 stack_in 的元素全部倒入。
class MyQueue:
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x):
self.stack_in.append(x)
def pop(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
def peek(self):
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out[-1]
def empty(self):
return not self.stack_in and not self.stack_out
核心：栈是 LIFO，倒一次就变成 FIFO 了。面试中要能解释"为什么均摊复杂度是 O(1)"。
九、设计题与杂项
35. LRU 缓存（LC 146）⭐⭐ 超高频
思路：哈希表 + 双向链表。哈希表实现 O(1) 查找，双向链表维护访问顺序。
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.cache = {}
# 虚拟头尾节点
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_front(node)
return node.val
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_to_front(node)
if len(self.cache) > self.cap:
# 删除尾部节点（最久未使用）
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key] # 这就是为什么 Node 要存 key！
面试必问细节：
- 为什么 Node 要同时存 key 和 val？因为淘汰尾部节点时需要用 key 去删哈希表中的记录
- get 和 put 的时间复杂度都是 O(1)
Python 偷懒版（面试一般不让用）：
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.cap = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False)
36. 多数元素（LC 169）
思路：摩尔投票法（Boyer-Moore Voting），O(n) 时间 O(1) 空间。
def majorityElement(nums):
candidate = nums[0]
count = 1
for i in range(1, len(nums)):
if count == 0:
candidate = nums[i]
if nums[i] == candidate:
count += 1
else:
count -= 1
return candidate
直觉：多数元素出现的次数比其他所有元素加起来还多，所以"互相抵消"后剩下的一定是多数元素。
37. 数组中的第 K 个最大元素（LC 215）⭐
思路：快速选择（QuickSelect），平均 O(n) 时间。
import random
def findKthLargest(nums, k):
"""找第 k 大，等价于找第 (n-k) 小"""
target = len(nums) - k
left, right = 0, len(nums) - 1
while left < right:
# 随机选基准
pivot_idx = random.randint(left, right)
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
# 分区
pivot = nums[right]
i = left - 1
for j in range(left, right):
if nums[j] < pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1], nums[right] = nums[right], nums[i + 1]
pivot_idx = i + 1
if pivot_idx == target:
return nums[target]
elif pivot_idx < target:
left = pivot_idx + 1
else:
right = pivot_idx - 1
return nums[left]
与快排的区别：快排递归两边，QuickSelect 只递归一边，所以平均复杂度从 O(n log n) 降到 O(n)。
面试追问：
- “最坏情况？” → O(n²)，但随机化后概率极低
- “能用堆做吗？” → 维护大小为 k 的最小堆，O(n log k)
十、面试前速查清单
| 序号 | 题目 | 核心技巧 | 频率 |
|---|---|---|---|
| 1 | 反转链表 | 三指针翻转 | ⭐⭐⭐ |
| 2 | 环形链表 | 快慢指针 | ⭐⭐⭐ |
| 3 | 合并有序链表 | 虚拟头节点 | ⭐⭐ |
| 4 | 两数相加 | 模拟进位 | ⭐⭐ |
| 5 | 删除倒数第N个 | 快慢指针间距 | ⭐⭐ |
| 6 | 合并K个链表 | 最小堆 | ⭐⭐⭐ |
| 7 | 层序遍历 | BFS + 队列 | ⭐⭐⭐ |
| 8 | 最大深度 | 递归 | ⭐⭐ |
| 9 | 构造二叉树 | 前中序递归 | ⭐⭐⭐ |
| 10 | 翻转二叉树 | 递归交换 | ⭐⭐ |
| 11 | 对称二叉树 | 镜像递归 | ⭐⭐ |
| 12 | 最近公共祖先 | 后序遍历 | ⭐⭐⭐ |
| 13 | BST第K小 | 中序遍历 | ⭐⭐ |
| 14 | 二分查找 | 闭区间模板 | ⭐⭐ |
| 15 | 搜索旋转数组 | 判断有序半 | ⭐⭐⭐ |
| 16 | 查找首尾位置 | 两次二分 | ⭐⭐ |
| 17 | 旋转数组最小值 | 二分 | ⭐⭐ |
| 18 | 无重复最长子串 | 滑动窗口 | ⭐⭐⭐ |
| 19 | 盛水容器 | 双指针移矮的 | ⭐⭐ |
| 20 | 三数之和 | 排序+双指针 | ⭐⭐⭐ |
| 21 | 接雨水 | 双指针/单调栈 | ⭐⭐⭐ |
| 22 | 爬楼梯 | 基础DP | ⭐⭐ |
| 23 | 最长递增子序列 | DP/贪心+二分 | ⭐⭐⭐ |
| 24 | 零钱兑换 | 完全背包 | ⭐⭐ |
| 25 | 最长公共子序列 | 二维DP | ⭐⭐ |
| 26 | 编辑距离 | 二维DP | ⭐⭐⭐ |
| 27 | 最长回文子串 | 中心扩展 | ⭐⭐⭐ |
| 28 | 全排列 | 回溯 | ⭐⭐ |
| 29 | 子集 | 回溯 | ⭐⭐ |
| 30 | N皇后 | 回溯+对角线 | ⭐⭐ |
| 31 | 岛屿数量 | DFS/BFS | ⭐⭐⭐ |
| 32 | 单词接龙 | BFS | ⭐⭐ |
| 33 | 有效括号 | 栈 | ⭐⭐ |
| 34 | 两栈实现队列 | 倒栈 | ⭐⭐ |
| 35 | LRU缓存 | 哈希+双向链表 | ⭐⭐⭐ |
| 36 | 多数元素 | 摩尔投票 | ⭐⭐ |
| 37 | 第K大元素 | QuickSelect | ⭐⭐⭐ |
面试前一天建议：把带 ⭐⭐⭐ 的 15 道题从头默写一遍，重点检查边界条件和去重逻辑。
评论区