#算法
23 篇
摩斯电码：一张表、两处歧义、三个实现细节
摩斯电码本身很简单，麻烦都在细节里：点划的空格归属、全角符号的归一化，以及「一个单位」到底有多长。
让弹球对手会算落点，但算不太准
一个能打赢的 Pong 对手需要两件事：把球的落点算准，再故意算错一点。前者用三角波一次算完，后者每次接球重抽一个偏差。
大 O 的误用：常数和前提比阶更常决定成败
O(n log n) 的排序可能慢过 O(n²) 的插入排序，O(1) 的哈希表可能慢过数组线性扫。判断性能前先确认输入规模、常数和内存局部性。
git bisect：把「哪次提交弄坏的」变成一条命令
回归排查的瓶颈不是二分本身，而是没人说得出「什么样的提交算坏」。先写出能自动判定的脚本，bisect 才能把 n 次构建压到 log n 次。
五子棋 AI：算杀层与搜索层怎么分工
纯 alpha-beta 在五子棋上会漏掉必杀。我把决策拆成三层——成五、堵五、算杀各司其职，剩下的才交给迭代加深加置换表，快棋也能下出像样的棋。
内存布局：同样的算法，慢十倍往往是因为缓存
CPU 取一次内存要几百个周期，取整个缓存行只要一次。顺序访问与随机访问的差别往往大过算法阶数。
死锁的四个条件：破坏其中任意一个就够了
互斥、持有并等待、不可抢占、循环等待——四个同时成立才会死锁。工程上最容易破坏的是循环等待：全局给锁定一个顺序。
灾难性回溯：正则为什么会让 CPU 打满
嵌套量词让匹配尝试数指数增长，(a+)+b 在一条长的不匹配输入上就能拖死进程。修法是去掉嵌套量词或给正则加超时。
SQLite 索引：最左前缀不是限制，是排序的结果
复合索引 (a, b) 只有先按 a 排才能按 b 排，所以「跳过 a 只用 b」自然用不上。理解成排序而非规则，就不会再背前缀口诀。
时区与夏令时：存 UTC，存本地时间一定会出事
夏令时会让某一天有 23 或 25 小时，且切换时刻的本地时间可能不存在或出现两次。只存 UTC 时间戳，展示时再转，是唯一稳的模型。
写中国象棋规则，四处最容易错的地方
蹩马腿、塞象眼、炮打隔子、将帅照面。我把走法生成拆成几何层与合法性层，前者只管兵种怎么走，后者统一兜住送将，四处坑各配了断言。
手写 cron 解析器：五段、并集规则，以及 2 月 30 日
cron 的语法半小时能写完，难的是语义：日与星期同时限定时是并集而非交集，不存在的时间要有终止条件，7 与 0 都是星期天。
CSV 不是「按逗号切」：RFC 4180 的引号与换行
一旦字段里有引号，split 立刻出错：引号能包住逗号和换行，引号自己写成两个。三十行状态机比任何正则都可靠。
黑白棋的合法落点：一次扫描，八个方向
一个空位合法，当且仅当八个方向里至少有一个方向能夹住对方的棋子。判断与翻转用的是同一次扫描，不必先模拟再回滚。
数独生成器：挖洞、唯一解，以及一个把页面卡死的 bug
生成器先填一个完整解，再逐格挖洞并验证唯一性。我在求解器里把「不限」写成 0，结果空盘要枚举全部解，点新局直接卡死。
一致性哈希：加一台机器为什么不用重排所有键
取模分片在机器数变化时几乎搬走全部数据。把哈希空间首尾相接成一个环，键归顺时针第一台机器，加节点只影响一段区间 —— 代价是需要虚拟节点。
五子棋的胜负判定：只查刚落下的那一点就够
每次落子后全盘扫描是浪费：胜负只可能因为最新一手而改变。沿四个方向从落子点向两侧延伸计数，判定成本与棋盘大小无关。
滑动窗口：先定「窗口里维护什么」，再写循环
窗口能成立的前提是「窗口是否合法」随左右边界单调。先写下维护的状态与收缩条件，双指针的两层循环自然会摊还成 O(n)。
单调栈：把「下一个更大的数」从 O(n²) 拉回 O(n)
每个元素最多进栈一次、出栈一次，所以看起来是双层循环的写法其实是线性。认出「左右第一个比自己大/小」这个形状，就能套同一个模板。
数二进制里有多少个 1：从循环到 SWAR
popcount 有三种写法：按 1 的个数循环、查表、以及并行算位的 SWAR。三种复杂度差一个数量级，而 Rust 与 WebAssembly 已经把它做成了单条指令。
并查集：两行优化让每次操作几乎变成常数
路径压缩把树压平，按大小合并让树不会长高。两个都要，复杂度才落到反阿克曼函数上 —— 也就是说 10 亿次操作也不会慢。
2048：把四个方向归一成同一个操作
滑动、合并、计分只需要写一遍，其余三个方向靠转置与反转复用。真正的难点是「每个方块一回合只能合并一次」，写错就得到不该出现的数字。
扫雷：把布雷推迟到第一次点击
第一下就踩雷的扫雷是没写完的扫雷。把布雷推迟到首次点击、并排除点击点周围 3×3，是这类实现最重要的一处设计。