面试题集锦:常见手写算法

面试题集锦:常见手写算法

Hello,我是小兔大白糖。 面试手写常卡在「会做但写不快」——这篇按题型收高频题:核心思路、可跑代码、复杂度,并配结构示意图。


目录

  1. 链表
  2. 数组与字符串
  3. 树
  4. 栈与队列
  5. 排序
  6. 动态规划
  7. 双指针与哈希表
  8. 二分查找与滑动窗口
  9. 加密货币交易所风控初面加练

1. 链表

1.1 反转链表

核心:三个指针 prev / cur / nxt 逐个翻转 next 指向。

interview handwritten algorithms · 图 1
interview handwritten algorithms · 图 1 · 点击查看 SVG 原图
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,逐节点比较拼接。

interview handwritten algorithms · 图 2
interview handwritten algorithms · 图 2 · 点击查看 SVG 原图
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 步,相遇则有环。

interview handwritten algorithms · 图 3
interview handwritten algorithms · 图 3 · 点击查看 SVG 原图
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 回到头,快慢同速走,再次相遇即为入口。

interview handwritten algorithms · 图 4
interview handwritten algorithms · 图 4 · 点击查看 SVG 原图
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 正好在中点。

interview handwritten algorithms · 图 5
interview handwritten algorithms · 图 5 · 点击查看 SVG 原图
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 在目标前驱。

interview handwritten algorithms · 图 6
interview handwritten algorithms · 图 6 · 点击查看 SVG 原图
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,一次遍历。

interview handwritten algorithms · 图 7
interview handwritten algorithms · 图 7 · 点击查看 SVG 原图
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 向中间夹逼。

interview handwritten algorithms · 图 8
interview handwritten algorithms · 图 8 · 点击查看 SVG 原图
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 收缩至无重复。

interview handwritten algorithms · 图 9
interview handwritten algorithms · 图 9 · 点击查看 SVG 原图
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 最长回文子串(中心扩展)

核心:枚举每个中心,向两边扩展,处理奇偶长度。

interview handwritten algorithms · 图 10
interview handwritten algorithms · 图 10 · 点击查看 SVG 原图
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)

核心:跳过前导空格,判断符号,逐位累加,越界处理。

interview handwritten algorithms · 图 11
interview handwritten algorithms · 图 11 · 点击查看 SVG 原图
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 二叉树前序遍历(迭代)

核心:栈模拟递归,根入栈,先右后左。

interview handwritten algorithms · 图 12
interview handwritten algorithms · 图 12 · 点击查看 SVG 原图
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 二叉树中序遍历(迭代)

核心:一路向左压栈,到底后弹出访问,再处理右子树。

interview handwritten algorithms · 图 13
interview handwritten algorithms · 图 13 · 点击查看 SVG 原图
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 二叉树层序遍历

核心:队列,逐层出队入队。

interview handwritten algorithms · 图 14
interview handwritten algorithms · 图 14 · 点击查看 SVG 原图
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。

interview handwritten algorithms · 图 15
interview handwritten algorithms · 图 15 · 点击查看 SVG 原图
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) 边界。

interview handwritten algorithms · 图 16
interview handwritten algorithms · 图 16 · 点击查看 SVG 原图
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。

interview handwritten algorithms · 图 17
interview handwritten algorithms · 图 17 · 点击查看 SVG 原图
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 有效的括号

核心:左括号入栈,右括号匹配栈顶。

interview handwritten algorithms · 图 18
interview handwritten algorithms · 图 18 · 点击查看 SVG 原图
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) 取最小值)

核心:辅助栈同步存当前最小值。

interview handwritten algorithms · 图 19
interview handwritten algorithms · 图 19 · 点击查看 SVG 原图
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 出队(空时一次性倒腾)。

interview handwritten algorithms · 图 20
interview handwritten algorithms · 图 20 · 点击查看 SVG 原图
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 用队列实现栈

核心:一个队列,每次入队后把前面所有元素重新出队入队,使新元素到队首。

interview handwritten algorithms · 图 21
interview handwritten algorithms · 图 21 · 点击查看 SVG 原图
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,递归左右。

interview handwritten algorithms · 图 22
interview handwritten algorithms · 图 22 · 点击查看 SVG 原图
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,然后合并两个有序数组。

interview handwritten algorithms · 图 23
interview handwritten algorithms · 图 23 · 点击查看 SVG 原图
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 大/小,只递归一边。

interview handwritten algorithms · 图 24
interview handwritten algorithms · 图 24 · 点击查看 SVG 原图
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)。

interview handwritten algorithms · 图 25
interview handwritten algorithms · 图 25 · 点击查看 SVG 原图
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)。

interview handwritten algorithms · 图 26
interview handwritten algorithms · 图 26 · 点击查看 SVG 原图
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 长度。

interview handwritten algorithms · 图 27
interview handwritten algorithms · 图 27 · 点击查看 SVG 原图
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 背包(简化版)

核心:倒序遍历容量,防止重复选取。

interview handwritten algorithms · 图 28
interview handwritten algorithms · 图 28 · 点击查看 SVG 原图
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 股票买卖的最佳时机(只能买卖一次)

核心:遍历过程中维护最低价格,当天卖出利润 = 当天价 - 最低价格。

interview handwritten algorithms · 图 29
interview handwritten algorithms · 图 29 · 点击查看 SVG 原图
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 盛最多水的容器

核心:左右指针,短板决定面积,移动短板试图增高。

interview handwritten algorithms · 图 30
interview handwritten algorithms · 图 30 · 点击查看 SVG 原图
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 移动零

核心:慢指针指向下一个非零该放的位置,快指针遍历。

interview handwritten algorithms · 图 31
interview handwritten algorithms · 图 31 · 点击查看 SVG 原图
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。

interview handwritten algorithms · 图 32
interview handwritten algorithms · 图 32 · 点击查看 SVG 原图
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,中点偏向左。

interview handwritten algorithms · 图 33
interview handwritten algorithms · 图 33 · 点击查看 SVG 原图
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 是否在有序半边内。

interview handwritten algorithms · 图 34
interview handwritten algorithms · 图 34 · 点击查看 SVG 原图
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),维护窗口内递减序列,队首即为最大值。

interview handwritten algorithms · 图 35
interview handwritten algorithms · 图 35 · 点击查看 SVG 原图
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 最小覆盖子串

核心:滑动窗口 + 哈希表统计需求字符,收缩左边界至满足条件的最小窗口。

interview handwritten algorithms · 图 36
interview handwritten algorithms · 图 36 · 点击查看 SVG 原图
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 回文链表

核心:快慢指针找中点,反转后半段,逐节点比较;或转数组双指针。

interview handwritten algorithms · 图 37
interview handwritten algorithms · 图 37 · 点击查看 SVG 原图
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,长度抵消后相遇点即交点;或先求长度差。

interview handwritten algorithms · 图 38
interview handwritten algorithms · 图 38 · 点击查看 SVG 原图
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 合并区间

核心:按起点排序,若当前区间与结果最后一项重叠则合并,否则追加。

interview handwritten algorithms · 图 39
interview handwritten algorithms · 图 39 · 点击查看 SVG 原图
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 峰值。

interview handwritten algorithms · 图 40
interview handwritten algorithms · 图 40 · 点击查看 SVG 原图
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) 移动/删除;满时删尾部,访问时移到头部。

interview handwritten algorithms · 图 41
interview handwritten algorithms · 图 41 · 点击查看 SVG 原图
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)。

interview handwritten algorithms · 图 42
interview handwritten algorithms · 图 42 · 点击查看 SVG 原图
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 每日温度(单调栈)

核心:递减栈存下标,当前温度大于栈顶对应温度时弹出并计算天数差。

interview handwritten algorithms · 图 43
interview handwritten algorithms · 图 43 · 点击查看 SVG 原图
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 归一组。

interview handwritten algorithms · 图 44
interview handwritten algorithms · 图 44 · 点击查看 SVG 原图
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 相同——单调队列维护窗口递减下标;可用于滚动计算风险指标峰值。

interview handwritten algorithms · 图 45
interview handwritten algorithms · 图 45 · 点击查看 SVG 原图

代码见 8.3,面试中常作为「单调栈/队列」模板直接调用。


9.10 初面临场清单(风控向)

类型必练题
链表反转、合并有序、环检测、回文、相交
数组两数之和、最大子数组和、合并区间、TopK
树层序遍历、BST 验证、LCA
栈/队列有效括号、单调栈(每日温度)、LRU
窗口/哈希无重复最长子串、和为 K 子数组、滑动窗口最大值

附:面试现场建议

  1. 先问清约束:数据范围、是否允许修改输入、边界条件。
  2. 先讲思路再写代码:即使思路简单,也要用 30 秒交代清楚,体现沟通。
  3. 边界测试:空输入、单元素、全相同元素、最大值/最小值。
  4. 复杂度主动报:Time / Space 脱口而出,这是 Senior 的基本功。
  5. 命名规范:不要用 a / b / c,用 left / right / slow / fast / prefix 等语义化名字。
  6. 如果卡壳:可以要求提示,或先写 brute force 再优化,展示 problem-solving 过程。
  7. 加密货币交易所风控初面:链表 + 哈希 + Kadane + 合并区间 + BFS 出现频率高;先画示意图再写代码,沟通分很重要。