系列目录 · 上一篇

本篇属于 智能体面试与工程基础 系列。

练习时同时覆盖正常、异常和边界输入。模拟模型可用于测试控制流程，但不能证明真实模型的推理和纠错能力。

C01｜P0：手写 LRU Cache，为什么能做到平均 O(1)？

思路： 哈希表把key映射到链表节点，双向链表维护使用顺序，头部最近使用、尾部最久未使用。get命中与put更新都把节点移到头部，超容量时删除尾部节点。哨兵节点减少空链表与单节点分支。

class Node:
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity):
        if capacity < 0:
            raise ValueError('capacity must be nonnegative')
        self.capacity, self.nodes = capacity, {}
        self.head, self.tail = Node(), 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 _recent(self, node):
        first = self.head.next
        node.prev, node.next = self.head, first
        self.head.next, first.prev = node, node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._recent(node)
        return node.value

    def put(self, key, value):
        if self.capacity == 0:
            return
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
        else:
            node = self.nodes[key] = Node(key, value)
        self._recent(node)
        if len(self.nodes) > self.capacity:
            old = self.tail.prev
            self._remove(old)
            del self.nodes[old.key]

复杂度与边界： 哈希操作平均O(1)，链表移动O(1)，空间O(capacity)。容量0、更新已有key、未命中以及淘汰后再访问都要验证。get也会修改链表；多线程版本需保护完整get/put复合操作，不能只保护字典读写。这里采用题目约定以-1表示未命中，通用缓存接口应避免与合法值混淆。

C02｜P1：字符串解码，如何处理嵌套与多位重复次数？

口述： 遇到数字累计重复次数；遇到左括号把外层片段和次数入栈，开始新的内层；遇到右括号把内层展开，再放回外层。3[a2[c]]先得到acc，再重复三次，结果是 accaccacc。

def decode_string(s):
    # Assumes the valid k[encoded] grammar; k is positive.
    stack, pieces, number = [], [], 0
    for ch in s:
        if '0' <= ch <= '9':
            number = number * 10 + int(ch)
        elif ch == '[':
            stack.append((pieces, number))
            pieces, number = [], 0
        elif ch == ']':
            inner = ''.join(pieces)
            pieces, repeat = stack.pop()
            pieces.append(inner * repeat)
        else:
            pieces.append(ch)
    return ''.join(pieces)

边界与复杂度： 此实现按题目保证的合法输入工作。12[a]不能只读一位数字；普通前后缀、连续编码段和多层嵌套都要测试。耗时取决于输入扫描和各层实际字符串拼接/复制总量，不能只报输入长度O(n)；若嵌套中反复复制很长中间串，成本可高于最终输出长度。外部输入还需括号/语法校验，以及展开长度和嵌套深度上限，防止短输入展开成巨量数据。

C03｜P1：岛屿数量，为什么要在入栈时标记？

口述： 扫描每个格子，遇到未访问陆地就计一个岛，并用DFS/BFS遍历所有四向连通陆地。入栈时立即标记，避免同一格子被多个邻居重复加入。题目默认上下左右相邻，不包含对角线。

def num_islands(grid):
    # Rectangular grid of '0'/'1'; consumes it by marking visited land.
    if not grid or not grid[0]:
        return 0
    rows, cols, count = len(grid), len(grid[0]), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            count += 1
            grid[r][c] = '0'
            stack = [(r, c)]
            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 < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                        grid[nx][ny] = '0'
                        stack.append((nx, ny))
    return count

复杂度与边界： 对m×n矩形网格，时间O(mn)，显式栈最坏O(mn)。空网格、全水、全陆地、单行、对角相邻都要测试。代码会修改输入；需要保留原网格时使用visited集合或复制，并计入空间成本。显式栈避免大连通块造成递归深度溢出。

系列目录 · 上一篇