算法与数据结构：从“会写代码”到“会拆问题”

问题与目标

算法学习容易走向两个极端：只记题型，或认为业务开发完全用不到。本阶段的目标不是追求竞赛技巧，而是能识别数据规模、选择合适结构、解释性能，并把模糊需求拆成可验证步骤。

完成标准：面对一个小问题，能说清输入、输出、约束和异常；至少提出两种实现，比较正确性、时间与空间代价。本篇不展开严格数学证明和冷门结构。

图中先固定输入、输出、约束和示例，再进入结构选择、实现与测试。这样拆解后，算法不再是脱离场景的代码片段，而是一条可以逐步检查的求解链路。

核心概念

数据结构描述数据怎样组织以及支持哪些操作；算法是一组有限、明确、可执行的求解步骤。一个可用算法至少应有清晰输入和输出、能够结束、每一步确定且可以执行。

学习重点按实际开发排序：

1. 把问题改写成输入、输出和边界条件。
2. 认识列表、栈、队列、哈希表、树和图的操作成本。
3. 能读懂复杂度，而不是只看一次运行耗时。
4. 掌握遍历、二分、排序、递归与几类基本求解思想。
5. 优先使用经过验证的标准库，自己实现用于理解和特殊需求。

算法正确不等于工程可用。还要考虑空输入、重复数据、数据质量、内存上限、错误处理和可维护性。

从需求到算法问题

一个含糊需求可以经过四步变成可实现问题：

随后再选择数据结构和算法。若输入是一次性数据流，逐条计数比先保存全部记录更合适；若需要反复查询单条任务，还应额外建立按 ID 的索引。需求变化会改变结构选择。

正确性的三个层次

1. 典型输入能得到预期结果。
2. 边界输入有明确行为，例如空集合和单元素。
3. 非法输入不会静默产生似是而非的结果。

复杂问题可以先写循环不变量：循环每完成一次，已经处理的记录都被准确计数，尚未处理的记录不会影响当前结果。它比“代码看起来没问题”更容易形成验证依据。

可运行实现

问题：给定一组任务记录，返回每个状态出现的次数。输入可能为空，记录必须包含 status。

from collections import Counter


def count_status(tasks: list[dict[str, str]]) -> dict[str, int]:
    counts: Counter[str] = Counter()
    for index, task in enumerate(tasks):
        if "status" not in task:
            raise ValueError(f"第 {index} 条记录缺少 status")
        counts[task["status"]] += 1
    return dict(counts)


data = [
    {"title": "clean data", "status": "done"},
    {"title": "draw chart", "status": "doing"},
    {"title": "write report", "status": "done"},
]

print(count_status(data))
print(count_status([]))

输出：

{'done': 2, 'doing': 1}
{}

逐条扫描是 O(n)，状态计数最多占 O(k) 空间，k 是不同状态数。另一种做法是为每个状态重复扫描列表，结果也能正确，但会产生更多无效遍历。

对照实现与测试

先用简单实现作为正确性参照，再优化复杂版本：

def count_status_reference(tasks: list[dict[str, str]]) -> dict[str, int]:
    statuses = {task["status"] for task in tasks}
    return {
        status: sum(task["status"] == status for task in tasks)
        for status in statuses
    }


assert count_status(data) == count_status_reference(data)
assert count_status([]) == {}

try:
    count_status([{"title": "missing status"}])
except ValueError as error:
    print(error)

参照实现可能更慢，但很适合用随机小样本对照优化实现。完成本篇后，可以为一个真实函数补写问题定义表、至少三个测试样例和复杂度说明。

常见问题与排查

• 先写代码再猜需求：先写三个样例，包括正常、空输入和异常输入。
• 只追求最低复杂度：小数据下清晰实现通常更重要，但必须知道增长风险。
• 自己实现所有容器：业务代码优先使用 list、dict、set、deque、heapq 等标准工具。
• 把刷题答案当成理解：改变输入约束或输出要求后仍能重新设计，才说明方法可迁移。
• 优化前没有测量：先确认瓶颈和输入规模，再选择数据结构或算法。

小结

这个阶段训练的是问题建模：定义数据、操作和约束，再讨论实现成本。最终产出不是题目数量，而是一套能解释、能验证、能调整的求解过程。