数据结构与算法 / 系统课时

先讲清思路再开始写代码

先讲清思路再开始写代码

面试中直接动手写代码,最容易在中途暴露假设不一致、数据结构选错或复杂度失控。更稳的做法是先用输入输出、不变量、数据结构和复杂度四部分把方案讲完整,再把已经明确的推理翻译成代码。

学习目标

  • 用四部分结构在一到两分钟内口述完整解法
  • 在编码前明确算法不变量与核心数据结构职责
  • 让代码实现与已经承诺的复杂度保持一致

四部分口述框架

第一部分是输入输出:说明你接收什么、需要返回什么,以及是否有会影响方案的边界条件。第二部分是不变量:说明算法执行过程中始终成立的事实,它通常是正确性的核心。第三部分是数据结构:解释为什么需要哈希表、栈、队列、堆或数组,而不是只报名称。第四部分是复杂度:给出时间和空间成本,并指出代价来自哪里。

编码前四部分口述框架

这四部分不是固定台词,而是防止遗漏的检查框架。简单题可以几十秒讲完,复杂题则多花一点时间解释不变量和状态定义。只要面试官能在你开始编码前复述出“你准备怎么做”,说明表达已经足够清楚。

用两数之和演示先讲后写

以“返回两个下标,使对应元素之和等于目标值”为例,可以先口述:输入是整数数组和目标值,输出一组下标;扫描到当前位置时,哈希表保存此前元素到下标的映射;若 target - x 已出现,就得到答案;因此每个元素只处理一次,时间复杂度 O(n)O(n),额外空间复杂度 O(n)O(n)。

当这四点已经明确,代码只是在实现既定方案,而不是边写边决定算法:

python
def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        # 先查补数,避免同一个元素被重复使用。
        if need in seen:
            return [seen[need], i]
        # 保存当前值,供后续元素查询。
        seen[x] = i
    return []

if __name__ == "__main__":
    print(two_sum([2, 7, 11, 15], 9))

预期输出

text
[0, 1]

这里代码中的哈希表职责与口述完全一致:它只保存已经扫描过的元素。若你在写到一半才发现自己还需要排序、回溯原下标或维护额外状态,往往说明前面的方案还没有讲清。

让不变量约束代码结构

“不变量”是最值得在编码前说清的部分,因为它直接决定代码顺序。上例必须先检查补数,再写入当前元素;否则当 target == 2 * x 时,可能错误地让同一个位置和自己配对。把这个不变量提前说出来,代码评审时就有明确标准,而不是只看样例是否碰巧通过。

类似地,滑动窗口要先说明窗口内维护什么条件,单调栈要说明栈内单调性,二分答案要说明判定函数为什么具有单调性。口述越准确,编码时需要临时改结构的次数越少。

复杂度要和实现一致

不要在口述中承诺 O(n)O(n),代码里却加入嵌套扫描;也不要说“常数空间”,随后建立与输入等长的辅助数组。编码完成后花十几秒沿着主循环重新核对一次:每个元素被处理几次,数据结构最多保存多少对象,是否有隐藏的排序或递归栈成本。

如果发现实现偏离原方案,可以直接说明:“这里为了保留原下标使用了额外哈希表,因此空间是 O(n)O(n)。”这种及时修正比坚持错误复杂度更可靠。面试官真正需要看到的是你能把思路、代码和复杂度三者对齐。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

先讲清思路再开始写代码

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通