卷一 · 算法与手撕 · 高频面试题

考察点：滑动窗口；哈希记字符最后一次位置；左指针只能右移（用 max 防回退）。

实现：

def length_of_longest_substring(s):
    last = {}      # 字符 -> 最后出现下标
    l, ans = 0, 0
    for r, c in enumerate(s):
        # 关键：max(l, last[c]+1)；last[c] 可能已在窗口外，l 不能回退
        if c in last and last[c] >= l:
            l = last[c] + 1
        last[c] = r
        ans = max(ans, r - l + 1)
    return ans

易错：忘 max 致 l 回退；用 set 删旧元素逻辑复杂；用 l = last[c]+1 不判区间漏过窗口外旧位置。

考察点：三指针迭代 O(1) 空间；递归 O(n) 栈空间；断尾防成环。

实现：

def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # 先存下一节点，否则反转后丢失
        cur.next = prev     # 反转当前节点指针
        prev, cur = cur, nxt
    return prev             # prev 为新头

def reverse_recursive(head):
    if not head or not head.next:  # 空或单节点直接返回（base case）
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head   # 让下一节点指回当前
    head.next = None        # 断尾防成环
    return new_head

易错：忘 head.next=None 致成环；指针顺序错（先改 next 再保存致丢失）；递归 base case 漏判 head 空。

考察点：排序 + 双指针；三处去重（i / l / r）；命中后双指针必须同时移动。

实现：

def three_sum(nums):
    nums.sort()
    n, res = len(nums), []
    for i in range(n - 2):
        if nums[i] > 0:
            break                       # 已排序，最小值 > 0 则无解
        if i > 0 and nums[i] == nums[i - 1]:
            continue                    # 去重 i：同一起点只算一次
        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]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1              # 去重 l
                while l < r and nums[r] == nums[r + 1]:
                    r -= 1              # 去重 r
    return res

易错：只去重 i 漏掉 l/r；命中后只移一个指针；忘记排序导致去重失效。

考察点：哈希表 + 双向链表，get/put 均摊 O(1)；容量为 0 的边界。

实现：

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

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = Node()              # 哨兵头
        self.tail = Node()              # 哨兵尾
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _add_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.map:
            return -1
        node = self.map[key]
        self._remove(node); self._add_front(node)   # 访问即刷新
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
            del self.map[key]
        if self.cap <= 0:
            return
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev        # 尾部即最久未用
            self._remove(lru)
            del self.map[lru.key]

易错：用普通 list 做 LRU 致 O(n) 查删；忘记维护 map 与链表一致；容量 0 时 put 仍插入。

考察点：快速选择（Quickselect）平均 O(n)、最坏 O(n²)；或大小为 K 的小顶堆 O(n log k)。

实现：

import random

def find_kth_largest(nums, k):
    def select(lo, hi, target):
        while lo < hi:
            p = random.randint(lo, hi)
            nums[p], nums[hi] = nums[hi], nums[p]
            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]
            if i == target:
                return nums[i]
            if i < target:
                lo = i + 1
            else:
                hi = i - 1
        return nums[lo]
    return select(0, len(nums) - 1, len(nums) - k)  # 第 K 大 = 升序下标 n-k

def find_kth_largest_heap(nums, k):
    import heapq
    h = nums[:k]
    heapq.heapify(h)                 # 小顶堆，堆顶是这 k 个里最小的
    for x in nums[k:]:
        if x > h[0]:
            heapq.heapreplace(h, x)
    return h[0]

易错：第 K 大误当第 K 小；下标写 k-1 而非 n-k；随机化 pivot 缺失致最坏 O(n²)。

考察点：Kadane 算法；cur = max(x, cur + x) 的取舍即"重新开始 vs 延续"。

实现：

def max_subarray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)   # 前面是负的就丢弃，从 x 重开
        best = max(best, cur)
    return best

易错：初始化 cur = 0 致全负数组返回 0（错，应为最大负数）；漏掉 best 单独维护。

考察点：dummy 哨兵；不足 K 个保持原序；接回时四个边界指针更新。

实现：

def reverse_k_group(head, k):
    dummy = type(head)(0) if head else None
    if not dummy:
        return None
    dummy.next = head
    pre = dummy                          # 上一组的末尾
    while True:
        # 先看后面是否还有 K 个节点；不足 K 直接 break（题目要求保留原序）
        tail = pre
        for _ in range(k):
            tail = tail.next
            if not tail:
                return dummy.next
        nxt_group = tail.next            # 下一组起点，反转前先存
        # 反转 [pre.next, tail] 这一段
        prev, cur = nxt_group, pre.next
        while cur != nxt_group:
            tmp = cur.next
            cur.next = prev
            prev, cur = cur, tmp
        # 接回：原 head 现在是这一组的尾
        new_tail = pre.next
        pre.next = prev                  # 新头接到 pre 后
        pre = new_tail                   # pre 推进到本组末尾

易错：探测不足 k 个时仍翻转；组尾接回时把新旧头弄反；虚拟头未参与最终返回。

考察点：一次遍历维护历史最低价；收益 = 当前价 − 最低价。

实现：

def max_profit(prices):
    if not prices:
        return 0
    low, best = prices[0], 0
    for p in prices[1:]:
        best = max(best, p - low)   # 先算收益，再用当前价更新最低
        low = min(low, p)
    return best

易错：先更新 low 再算收益（同日买卖）；允许多次交易当成单次。

考察点：双指针；max(left_max, right_max) 与 min(left_max, right_max) - h 的推导。

实现：

def trap(height):
    if not height:
        return 0
    l, r = 0, len(height) - 1
    lmax = rmax = 0
    water = 0
    while l < r:
        if height[l] < height[r]:
            lmax = max(lmax, height[l])
            water += lmax - height[l]   # 左侧水位由 lmax 决定
            l += 1
        else:
            rmax = max(rmax, height[r])
            water += rmax - height[r]
            r -= 1
    return water

易错：写成 max(lmax, rmax) - h（应为 min）；循环条件用 l <= r 致重复计数。

考察点：队列按层；用 len(queue) 固定本层节点数。

实现：

from collections import deque

def level_order(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        n = len(q)              # 固定本层节点数
        level = []
        for _ in range(n):
            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

易错：不固定 len(q) 致分层错乱；忘判 root 为空。

考察点：哈希表一趟解；边遍历边查"补数是否已出现"。

实现：

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:      # 先查后存，避免自己和自己配
            return [seen[target - x], i]
        seen[x] = i
    return []

易错：先存后查致 x + x == target 时返回同一元素两次；返回的是值而非下标。

考察点：DFS/BFS 洪水填充；访问标记原地改写避免额外 set。

实现：

def num_islands(grid):
    if not grid or not grid[0]:
        return 0
    R, C = len(grid), len(grid[0])
    count = 0
    for i in range(R):
        for j in range(C):
            if grid[i][j] != '1':
                continue
            count += 1
            stack = [(i, j)]
            grid[i][j] = '0'          # 入栈即标，防重复入栈
            while stack:
                x, y = stack.pop()
                for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < R and 0 <= ny < C and grid[nx][ny] == '1':
                        grid[nx][ny] = '0'
                        stack.append((nx, ny))
    return count

易错：出栈才标记致重复入栈栈溢出；四邻居漏写上下左右。

考察点：快慢指针；fast 每次走 2 步、slow 走 1 步，相遇即有环。

实现：

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:      # 身份比较，不是数值比较
            return True
    return False

易错：用 == 比值（链表节点应比身份）；fast.next.next 未判 fast.next 空致异常。

考察点：前缀和 + 哈希；need = prefix - k 的出现次数即以当前位结尾的答案数。

实现：

def subarray_sum(nums, k):
    from collections import defaultdict
    cnt = defaultdict(int)
    cnt[0] = 1        # 前缀和为 0 的空前缀，出现 1 次
    prefix = ans = 0
    for x in nums:
        prefix += x
        ans += cnt[prefix - k]
        cnt[prefix] += 1     # 先查后加，避免把空子数组算进去
    return ans

易错：忘记 cnt[0]=1 漏掉从 0 开始的子数组；先加后查致 k=0 时计入空数组。

考察点：后序遍历；左右子树都有返回值则当前即 LCA，否则上抛非空的那侧。

实现：

def lowest_common_ancestor(root, p, q):
    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        # p 和 q 分居两侧 → 当前是 LCA
    return left or right

易错：前序遍历时无法判断"两侧都有"；未考虑 p 或 q 就是根节点。

考察点：栈；遇右括号必须与栈顶匹配。

实现：

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack.pop() != pairs[ch]:
                return False   # 空栈或类型不匹配
    return not stack           # 栈必须为空

易错：只判断长度奇偶；栈空时 pop 抛异常；忘记最后判栈空。

考察点：单调递减队列；队首即窗口最大值；新元素入队前清掉队尾 ≤ 它的。

实现：

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()      # 存下标，值单调递减
    res = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:      # 队首过期
            dq.popleft()
        while dq and nums[dq[-1]] <= x:    # 队尾被 x 支配
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

易错：存值而非下标致无法判断过期；清理过期用 < 而非 <=。

考察点：辅助栈同步记录当前最小值；或单栈存 (value, min) 对。

实现：

class MinStack:
    def __init__(self):
        self.data = []
        self.mins = []      # 与 data 等长，mins[-1] 是当前最小值

    def push(self, x):
        self.data.append(x)
        self.mins.append(min(x, self.mins[-1]) if self.mins else x)

    def pop(self):
        self.mins.pop()
        return self.data.pop()

    def top(self):
        return self.data[-1]

    def get_min(self):
        return self.mins[-1]

易错：用 min(self.data) 每次 O(n)；pop 时只弹 data 忘了弹 mins 导致长度错位。

考察点：按左端点排序；与上一个区间重叠时把右端点取 max。

实现：

def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    res = [list(intervals[0])]
    for start, end in intervals[1:]:
        if start <= res[-1][1]:            # 重叠（含相邻端点相等）
            res[-1][1] = max(res[-1][1], end)
        else:
            res.append([start, end])
    return res

易错：合并后右端点没取 max（被短区间覆盖）；忘记先排序。

考察点：两两归并（分治）避免逐条插入的 O(NK)；或小顶堆。

实现：

import heapq

def merge_k_lists(lists):
    heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
    heapq.heapify(heap)
    dummy = ListNode(0)
    tail = dummy
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

易错：堆元素只放值致无法区分同值来自哪条链表（需带序号打破平局）；漏推 node.next。

考察点：贪心 + 二分；tails[k] 存长度 k+1 的递增子序列最小结尾。

实现：

import bisect

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)   # 第一个 >= x 的位置
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x      # 替换为更小的结尾，给后面留空间
    return len(tails)

易错：用 bisect_right 把相等元素也算进递增；返回 tails 本身而非其长度。

考察点：多源 BFS；层数即经过的分钟数。

实现：

from collections import deque

def oranges_rotting(grid):
    if not grid:
        return 0
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for i in range(R):
        for j in range(C):
            if grid[i][j] == 2:
                q.append((i, j))
            elif grid[i][j] == 1:
                fresh += 1
    mins = 0
    while q:
        n = len(q)
        for _ in range(n):
            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 < R and 0 <= ny < C and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    fresh -= 1
                    q.append((nx, ny))
        if q:
            mins += 1
    return -1 if fresh else mins

易错：有新鲜橘子但队列耗尽时应返回 -1；层数在空队列轮次仍自增。

考察点：栈存"未匹配左括号下标"，栈底哨兵 −1；遇左括号入栈，右括号匹配后算长度。

实现：

def longest_valid_parentheses(s):
    stack = [-1]        # 栈底哨兵：最后一个未匹配右括号的位置
    best = 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)   # 当前右括号无匹配，作为新哨兵
            else:
                best = max(best, i - stack[-1])
    return best

易错：栈空时直接取 stack[-1] 抛异常；哨兵初值写成 0 而非 -1。

考察点：二维 DP；dp[i][j] = 前 i 个字符变前 j 个字符的最少操作数。

实现：

def edit_distance(word1, word2):
    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 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]

易错：边界初始化写成 0（应 i / j）；相等时仍取 min 三项（等价但多余）。

考察点：中心扩展法；奇偶两种中心都要试。

实现：

def longest_palindrome(s):
    best = ""
    for i in range(len(s)):
        for l, r in ((i, i), (i, i + 1)):   # 奇数中心 & 偶数中心
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            cand = s[l+1:r]
            if len(cand) > len(best):
                best = cand
    return best

易错：只处理奇数长度；边界判断写错致越界。

考察点：回溯；used 数组标记已选；撤销选择回到上层状态。

实现：

def permute(nums):
    res, path, used = [], [], [False] * len(nums)
    def backtrack():
        if len(path) == len(nums):
            res.append(path[:])     # 拷贝，不能直接 append(path)
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False         # 撤销
    backtrack()
    return res

易错：res.append(path) 未拷贝，后续回溯会把已存结果改掉；忘撤销 used。

考察点：快慢指针相差 N+1 步；虚拟头节点处理删头。

实现：

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):      # fast 先走 n+1 步
        if fast is None:
            break
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next  # 删除 slow 的下一个
    return dummy.next

易错：fast 先走 N 步（应 N+1）；不用虚拟头致删头指针悬挂。

考察点：回溯 + 剩余左括号/右括号计数剪枝。

实现：

def generate_parenthesis(n):
    res, path = [], []
    def backtrack(open_c, close_c):
        if len(path) == 2 * n:
            res.append("".join(path))
            return
        if open_c < n:                    # 还能加左括号
            path.append("(")
            backtrack(open_c + 1, close_c)
            path.pop()
        if close_c < open_c:              # 右括号不能多于左括号
            path.append(")")
            backtrack(open_c, close_c + 1)
            path.pop()
    backtrack(0, 0)
    return res

易错：漏掉 close_c < open_c 剪枝产生非法串；未用 path.pop() 回溯。

考察点：二维 DP；相等时取左上+1，否则取上/左较大者。

实现：

def longest_common_subsequence(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]

易错：相等时写成 max(dp[i-1][j-1], ...)（应直接取左上）；边界全 0 未处理。

考察点：Boyer-Moore 投票；候选人与计数成对维护。

实现：

def majority_element(nums):
    cand = None
    count = 0
    for x in nums:
        if count == 0:
            cand = x
        count += 1 if x == cand else -1
    return cand

易错：题目只保证多数元素存在才可不二次校验；把它写成"求众数"（可多个）致逻辑不符。

考察点：BFS 必给最短（无权图）；visited 入队即标（非出队）；DFS 求所有路径不能求最短。

实现：

from collections import deque

def bfs_shortest(grid, start, goal):
    # grid: 2D list；0 通行、1 障碍；返回最短步数或 -1
    R, C = len(grid), len(grid[0])
    if grid[start[0]][start[1]] or grid[goal[0]][goal[1]]:
        return -1
    visited = [[False] * C for _ in range(R)]
    q = deque([(start[0], start[1], 0)])
    visited[start[0]][start[1]] = True  # 入队即标，防重复入队 TLE
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)  # 四邻居
    while q:
        x, y, d = q.popleft()
        if (x, y) == goal:
            return d
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            # 边界 + 障碍 + visited 三道闸
            if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny] and not grid[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny, d + 1))
    return -1

易错：visited 出队才标 → 重复入队 TLE；用 DFS 求最短（应 BFS）；八邻居斜走代价应 √2 而非 1。

考察点：Dijkstra h=0、A* f=g+h；h 必须 admissible（≤真实代价）保证最优；用 g_best 替代 closed set。

实现：

import heapq

def heuristic(p, goal):
    # 4 邻居用 Manhattan；8 邻居/自由方向用 Euclidean；都 admissible
    return abs(p[0] - goal[0]) + abs(p[1] - goal[1])

def astar(grid, start, goal):
    R, C = len(grid), len(grid[0])
    g_best = {start: 0}
    pq = [(heuristic(start, goal), 0, start)]  # (f, g, pos)
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
    while pq:
        f, g, p = heapq.heappop(pq)
        if p == goal:
            return g
        if g > g_best.get(p, float('inf')):  # 懒删除：过期条目跳过
            continue
        for k in range(4):
            nx, ny = p[0] + dx[k], p[1] + dy[k]
            if not (0 <= nx < R and 0 <= ny < C) or grid[nx][ny]:
                continue
            ng = g + 1
            np_ = (nx, ny)
            # 仅当新 g 更小才入队（替代 closed set，更简洁）
            if ng < g_best.get(np_, float('inf')):
                g_best[np_] = ng
                heapq.heappush(pq, (ng + heuristic(np_, goal), ng, np_))
    return -1

易错：h 不 admissible（高估）→ 解不最优；按 g 入堆而非 f；同节点重复入队忘懒删除致路径错。

考察点：双检锁的内存可见性问题——没有 volatile 时指令重排会返回未完全初始化的对象。

实现：

import threading

class Singleton:
    _instance = None
    _lock = threading.Lock()

    def __new__(cls, *args, **kwargs):
        if cls._instance is None:          # 第一重：无锁快速路径
            with cls._lock:
                if cls._instance is None:  # 第二重：持锁复查
                    cls._instance = super().__new__(cls)
                    cls._instance._init_done = False
        return cls._instance

    def __init__(self, value=0):
        if getattr(self, "_init_done", False):
            return                          # 避免重复初始化
        self.value = value
        self._init_done = True

易错：漏 volatile（Java）致其他线程读到半初始化对象；__init__ 每次都重跑致状态被重置；用模块级判断在多进程下失效（每进程一份）。

追问：① 进程内单例 vs 跨进程单例怎么实现？② Python 里为什么不需要 volatile（GIL + CPython 内存模型）？③ 单例的测试怎么写？

考察点：令牌桶允许突发；滑动窗口限流更平滑；两者都是"时间维度上的计数"。

实现：

import time
from collections import deque

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate              # 每秒生成令牌数
        self.capacity = capacity      # 桶容量 = 最大突发量
        self.tokens = capacity
        self.last = time.monotonic()

    def allow(self, n=1):
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

易错：用 time.time()（会被 NTP 调整回退，应用 time.monotonic()）；漏了容量上限致长时间空闲后一次放行无限流量；并发下未加锁。

追问：① 令牌桶和漏桶区别？② 分布式限流怎么做（Redis + Lua 保证原子）？③ 限流维度：全局 / 用户 / 接口 / IP？