
Hello,我是小兔大白糖。 面试手写常卡在「会做但写不快」——这篇按题型收高频题:核心思路、可跑代码、复杂度,并配结构示意图。
目录
1. 链表
1.1 反转链表
核心:三个指针 prev / cur / nxt 逐个翻转 next 指向。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head: ListNode) -> ListNode:
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev- Time: O(n)
- Space: O(1)
1.2 合并两个有序链表
核心:虚拟头节点 dummy,逐节点比较拼接。
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = cur = ListNode()
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
cur.next = l1 or l2
return dummy.next- Time: O(n + m)
- Space: O(1)
1.3 检测链表是否有环(Floyd)
核心:快慢指针,fast 每次走 2 步,slow 走 1 步,相遇则有环。
def has_cycle(head: 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- Time: O(n)
- Space: O(1)
1.4 找到环的入口节点
核心:相遇后,slow 回到头,快慢同速走,再次相遇即为入口。
def detect_cycle(head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None- Time: O(n)
- Space: O(1)
1.5 链表中点(快慢指针)
核心:fast 走到尾时,slow 正好在中点。
def middle_node(head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow- Time: O(n)
- Space: O(1)
1.6 删除链表的倒数第 N 个节点
核心:fast 先走 N 步,然后同步走,fast 到尾时 slow 在目标前驱。
def remove_nth_from_end(head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next- Time: O(n)
- Space: O(1)
2. 数组与字符串
2.1 两数之和
核心:哈希表存 target - num,一次遍历。
def two_sum(nums: list[int], target: int) -> list[int]:
seen = {}
for i, v in enumerate(nums):
if target - v in seen:
return [seen[target - v], i]
seen[v] = i
return []- Time: O(n)
- Space: O(n)
2.2 三数之和
核心:排序 + 双指针去重。固定一个数,left/right 向中间夹逼。
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
res = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, n - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
return res- Time: O(n²)
- Space: O(1)(不算输出)
2.3 无重复字符的最长子串
核心:滑动窗口 + 哈希集合,right 扩展,left 收缩至无重复。
def length_of_longest_substring(s: str) -> int:
seen = set()
left = 0
ans = 0
for right, ch in enumerate(s):
while ch in seen:
seen.remove(s[left])
left += 1
seen.add(ch)
ans = max(ans, right - left + 1)
return ans- Time: O(n)
- Space: O(min(n, |Σ|))
2.4 最长回文子串(中心扩展)
核心:枚举每个中心,向两边扩展,处理奇偶长度。
def longest_palindrome(s: str) -> str:
def expand(l: int, r: int) -> str:
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return s[l + 1:r]
ans = ""
for i in range(len(s)):
odd = expand(i, i)
even = expand(i, i + 1)
ans = max(ans, odd, even, key=len)
return ans- Time: O(n²)
- Space: O(1)
2.5 字符串转整数(atoi)
核心:跳过前导空格,判断符号,逐位累加,越界处理。
def my_atoi(s: str) -> int:
i, n = 0, len(s)
while i < n and s[i] == ' ':
i += 1
sign = 1
if i < n and s[i] in ('-', '+'):
sign = -1 if s[i] == '-' else 1
i += 1
ans = 0
INT_MAX, INT_MIN = 2 ** 31 - 1, -(2 ** 31)
while i < n and s[i].isdigit():
digit = int(s[i])
# 越界检查:ans > (INT_MAX - digit) // 10 即会溢出
if ans > (INT_MAX - digit) // 10:
return INT_MAX if sign == 1 else INT_MIN
ans = ans * 10 + digit
i += 1
return sign * ans- Time: O(n)
- Space: O(1)
3. 树
3.1 二叉树前序遍历(迭代)
核心:栈模拟递归,根入栈,先右后左。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder(root: TreeNode) -> list[int]:
if not root:
return []
res, stack = [], [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res- Time: O(n)
- Space: O(h)
3.2 二叉树中序遍历(迭代)
核心:一路向左压栈,到底后弹出访问,再处理右子树。
def inorder(root: TreeNode) -> list[int]:
res, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res- Time: O(n)
- Space: O(h)
3.3 二叉树层序遍历
核心:队列,逐层出队入队。
from collections import deque
def level_order(root: TreeNode) -> list[list[int]]:
if not root:
return []
res = []
q = deque([root])
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)
res.append(level)
return res- Time: O(n)
- Space: O(w),w 为最大宽度
3.4 二叉树最大深度
核心:递归 max(left, right) + 1。
def max_depth(root: TreeNode) -> int:
if not root:
return 0
return max(max_depth(root.left), max_depth(root.right)) + 1- Time: O(n)
- Space: O(h)
3.5 验证二叉搜索树
核心:中序遍历应递增,或递归传 (min, max) 边界。
def is_valid_bst(root: TreeNode) -> bool:
def helper(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return helper(node.left, low, node.val) and helper(node.right, node.val, high)
return helper(root, float('-inf'), float('inf'))- Time: O(n)
- Space: O(h)
3.6 二叉树的最近公共祖先(LCA)
核心:递归,若当前节点等于 p/q 则返回;左右子树都非空则当前为 LCA。
def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root is p or root is q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left or right- Time: O(n)
- Space: O(h)
4. 栈与队列
4.1 有效的括号
核心:左括号入栈,右括号匹配栈顶。
def is_valid(s: str) -> bool:
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack- Time: O(n)
- Space: O(n)
4.2 最小栈(O(1) 取最小值)
核心:辅助栈同步存当前最小值。
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int):
self.stack.append(val)
self.min_stack.append(val if not self.min_stack else min(val, self.min_stack[-1]))
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def get_min(self) -> int:
return self.min_stack[-1]- 所有操作 Time: O(1)
- Space: O(n)
4.3 用栈实现队列
核心:两个栈,in_stack 入队,out_stack 出队(空时一次性倒腾)。
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x: int):
self.in_stack.append(x)
def pop(self) -> int:
self.peek()
return self.out_stack.pop()
def peek(self) -> int:
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack[-1]
def empty(self) -> bool:
return not self.in_stack and not self.out_stack- 均摊 Time: O(1)
- Space: O(n)
4.4 用队列实现栈
核心:一个队列,每次入队后把前面所有元素重新出队入队,使新元素到队首。
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x: int):
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft()
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return not self.q- Time: push O(n),其他 O(1)
- Space: O(n)
5. 排序
5.1 快速排序
核心:选 pivot,原地 partition,递归左右。
def quick_sort(nums: list[int]) -> list[int]:
def partition(lo, hi):
pivot = nums[hi]
i = lo
for j in range(lo, hi):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[hi] = nums[hi], nums[i]
return i
def sort(lo, hi):
if lo < hi:
p = partition(lo, hi)
sort(lo, p - 1)
sort(p + 1, hi)
sort(0, len(nums) - 1)
return nums- Time: O(n log n) avg, O(n²) worst
- Space: O(log n)
5.2 归并排序
核心:分治,递归到长度为 1,然后合并两个有序数组。
def merge_sort(nums: list[int]) -> list[int]:
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left: list[int], right: list[int]) -> list[int]:
res = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res.extend(left[i:])
res.extend(right[j:])
return res- Time: O(n log n)
- Space: O(n)
5.3 Top K 问题(快排 partition 变形)
核心:利用 partition 找到第 K 大/小,只递归一边。
def find_kth_largest(nums: list[int], k: int) -> int:
def partition(lo, hi):
pivot = nums[hi]
i = lo
for j in range(lo, hi):
if nums[j] > pivot: # 找第 K 大,降序排列
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[hi] = nums[hi], nums[i]
return i
def select(lo, hi):
if lo == hi:
return nums[lo]
p = partition(lo, hi)
if p == k - 1:
return nums[p]
elif p < k - 1:
return select(p + 1, hi)
else:
return select(lo, p - 1)
return select(0, len(nums) - 1)- Time: O(n) avg
- Space: O(log n)
6. 动态规划
6.1 爬楼梯
核心:dp[i] = dp[i-1] + dp[i-2],空间压缩到 O(1)。
def climb_stairs(n: int) -> int:
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b- Time: O(n)
- Space: O(1)
6.2 最长递增子序列(LIS)
核心:dp[i] 表示以 nums[i] 结尾的 LIS 长度,或二分 tails 数组优化到 O(n log n)。
import bisect
def length_of_lis(nums: list[int]) -> int:
tails = []
for num in nums:
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
tails.append(num)
else:
tails[idx] = num
return len(tails)- Time: O(n log n)
- Space: O(n)
6.3 最长公共子序列(LCS)
核心:dp[i][j] 表示 text1[0:i] 与 text2[0:j] 的 LCS 长度。
def longest_common_subsequence(text1: str, text2: str) -> int:
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]- Time: O(mn)
- Space: O(mn)(可压缩至 O(min(m,n)))
6.4 0-1 背包(简化版)
核心:倒序遍历容量,防止重复选取。
def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]- Time: O(n * capacity)
- Space: O(capacity)
6.5 股票买卖的最佳时机(只能买卖一次)
核心:遍历过程中维护最低价格,当天卖出利润 = 当天价 - 最低价格。
def max_profit(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- Time: O(n)
- Space: O(1)
7. 双指针与哈希表
7.1 盛最多水的容器
核心:左右指针,短板决定面积,移动短板试图增高。
def max_area(height: list[int]) -> int:
left, right = 0, len(height) - 1
ans = 0
while left < right:
w = right - left
if height[left] < height[right]:
ans = max(ans, height[left] * w)
left += 1
else:
ans = max(ans, height[right] * w)
right -= 1
return ans- Time: O(n)
- Space: O(1)
7.2 移动零
核心:慢指针指向下一个非零该放的位置,快指针遍历。
def move_zeroes(nums: list[int]):
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1- Time: O(n)
- Space: O(1)
7.3 和为 K 的子数组个数
核心:前缀和 + 哈希表,prefix_sum[j] - prefix_sum[i] = k。
def subarray_sum(nums: list[int], k: int) -> int:
from collections import defaultdict
count = defaultdict(int)
count[0] = 1
prefix = 0
ans = 0
for num in nums:
prefix += num
ans += count[prefix - k]
count[prefix] += 1
return ans- Time: O(n)
- Space: O(n)
8. 二分查找与滑动窗口
8.1 二分查找(标准模板)
核心:闭区间 [left, right],循环条件 left <= right,中点偏向左。
def binary_search(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
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1- Time: O(log n)
- Space: O(1)
8.2 搜索旋转排序数组
核心:判断哪半边有序,再判断 target 是否在有序半边内。
def search_rotated(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- Time: O(log n)
- Space: O(1)
8.3 滑动窗口最大值
核心:单调队列(deque),维护窗口内递减序列,队首即为最大值。
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
q = deque() # 存下标,对应值递减
res = []
for i, v in enumerate(nums):
# 移除窗口外元素
if q and q[0] <= i - k:
q.popleft()
# 维持递减
while q and nums[q[-1]] < v:
q.pop()
q.append(i)
if i >= k - 1:
res.append(nums[q[0]])
return res- Time: O(n)
- Space: O(k)
8.4 最小覆盖子串
核心:滑动窗口 + 哈希表统计需求字符,收缩左边界至满足条件的最小窗口。
def min_window(s: str, t: str) -> str:
from collections import Counter
need = Counter(t)
missing = len(t)
left = start = 0
min_len = float('inf')
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0:
if right - left + 1 < min_len:
min_len = right - left + 1
start = left
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if min_len == float('inf') else s[start:start + min_len]- Time: O(|s| + |t|)
- Space: O(|Σ|)
9. 加密货币交易所风控初面加练
本节为 大型加密货币交易所 / 加密货币交易所 Risk 等部门初面 常见手写题(与「反转链表」同档:Easy ~ Medium)。偏链表、哈希、区间合并、BFS、缓存设计。
9.1 回文链表
核心:快慢指针找中点,反转后半段,逐节点比较;或转数组双指针。
def is_palindrome_list(head: ListNode) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True- Time: O(n)
- Space: O(1)
9.2 相交链表
核心:两指针分别走完 A+B、B+A,长度抵消后相遇点即交点;或先求长度差。
def get_intersection_node(headA: ListNode, headB: ListNode) -> ListNode:
pA, pB = headA, headB
while pA is not pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA- Time: O(m + n)
- Space: O(1)
9.3 合并区间
核心:按起点排序,若当前区间与结果最后一项重叠则合并,否则追加。
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
res = []
for start, end in intervals:
if not res or start > res[-1][1]:
res.append([start, end])
else:
res[-1][1] = max(res[-1][1], end)
return res- Time: O(n log n)
- Space: O(1)(不计输出)
9.4 最大子数组和(Kadane)
核心:cur 为以当前元素结尾的最大和,负数则重新开始;风控可类比滚动 PnL 峰值。
def max_subarray(nums: list[int]) -> int:
cur = ans = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
ans = max(ans, cur)
return ans- Time: O(n)
- Space: O(1)
9.5 LRU 缓存
核心:哈希表 O(1) 定位 + 双向链表 O(1) 移动/删除;满时删尾部,访问时移到头部。
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int):
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)- Time: get/put 均 O(1)
- Space: O(capacity)
9.6 岛屿数量(BFS/DFS)
核心:遍历网格,遇 1 则 count++ 并用 BFS/DFS 沉岛(标 0)。
from collections import deque
def num_islands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
ans = 0
def bfs(r: int, c: int):
q = deque([(r, c)])
grid[r][c] = '0'
while q:
x, y = q.popleft()
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
grid[nx][ny] = '0'
q.append((nx, ny))
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
ans += 1
bfs(i, j)
return ans- Time: O(mn)
- Space: O(mn) 最坏 BFS 队列
9.7 每日温度(单调栈)
核心:递减栈存下标,当前温度大于栈顶对应温度时弹出并计算天数差。
def daily_temperatures(temperatures: list[int]) -> list[int]:
n = len(temperatures)
ans = [0] * n
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- Time: O(n)
- Space: O(n)
9.8 字母异位词分组
核心:哈希 key = 排序后的字符串(或 26 位计数元组),同 key 归一组。
from collections import defaultdict
def group_anagrams(strs: list[str]) -> list[list[str]]:
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s))
groups[key].append(s)
return list(groups.values())- Time: O(n * k log k),k 为字符串最大长度
- Space: O(nk)
9.9 滑动窗口最大值(风控滚动峰值)
核心:与 8.3 相同——单调队列维护窗口递减下标;可用于滚动计算风险指标峰值。
代码见 8.3,面试中常作为「单调栈/队列」模板直接调用。
9.10 初面临场清单(风控向)
| 类型 | 必练题 |
|---|---|
| 链表 | 反转、合并有序、环检测、回文、相交 |
| 数组 | 两数之和、最大子数组和、合并区间、TopK |
| 树 | 层序遍历、BST 验证、LCA |
| 栈/队列 | 有效括号、单调栈(每日温度)、LRU |
| 窗口/哈希 | 无重复最长子串、和为 K 子数组、滑动窗口最大值 |
附:面试现场建议
- 先问清约束:数据范围、是否允许修改输入、边界条件。
- 先讲思路再写代码:即使思路简单,也要用 30 秒交代清楚,体现沟通。
- 边界测试:空输入、单元素、全相同元素、最大值/最小值。
- 复杂度主动报:Time / Space 脱口而出,这是 Senior 的基本功。
- 命名规范:不要用
a / b / c,用left / right / slow / fast / prefix等语义化名字。 - 如果卡壳:可以要求提示,或先写 brute force 再优化,展示 problem-solving 过程。
- 加密货币交易所风控初面:链表 + 哈希 + Kadane + 合并区间 + BFS 出现频率高;先画示意图再写代码,沟通分很重要。