阿甘的博客 | Arganzheng's Blog

面试手撕代码（07）：二分——只有一个模板

Binary Search: One Template, First Position Where the Predicate Holds

二分是”人人都会、人人都写错”的算法：lo <= hi 还是 lo < hi、mid 还是 mid + 1、返回 lo 还是 hi，每次都要现场想一遍。根源在于把二分当成”在有序数组里找一个值”——那只是它最窄的用法。二分的本质是：在一个”假假假……真真真”的单调谓词序列上，找第一个真的位置。用这一个定义写一个 first_true(lo, hi, pred)，所有二分题——找值、找边界、旋转数组、找峰值、”答案二分”、值域二分——都变成”写出那个谓词”。这一篇七道主讲题全部用同一个函数。本篇要回答的核心问题是：为什么”第一个使谓词为真的位置”这一个模板能覆盖全部二分题？1 “答案二分”（吃香蕉、运输包裹、分割数组）怎样把最优化问题变成判定...

Posted by arganzheng | December 8, 2025

面试手撕代码（06）：图——BFS / DFS / 拓扑排序 / 并查集 / 最短路

Graphs: BFS, DFS, Topological Sort, Union-Find and Dijkstra

面试里的图题很少给你一张”图”——给的是网格、课程依赖、单词列表、账户邮箱，第一步是看出它是图：格子是节点、四邻是边；课程是节点、先修关系是有向边；单词是节点、改一个字母能到达是边。看出来之后，可用的算法只有五个：BFS（最短步数、按层扩散）、DFS（连通块、路径存在性）、拓扑排序（有向无环图的依赖顺序）、并查集（动态连通性）、Dijkstra（带权最短路）。这一篇六道主讲题每种一到两道，重点是建图和visited 放在哪——图题的 bug 多半出在这两处。本篇要回答的核心问题是： BFS 的 visited 标记应该在入队时打还是出队时打？1 拓扑排序怎样同时判断有没有环？2 并查集的路径压缩和按大小合并各起什么作用，写哪一个就够？3 一、识别信号...

Posted by arganzheng | December 7, 2025

面试手撕代码（05）：二叉树

Binary Trees: Three Questions Every Recursion Must Answer

二叉树是面试里出题最多的一类结构，因为它天然是递归的：一个节点的答案 = 用左右子树的答案拼出来。几乎所有树题都能用同一个框架写完——决定递归函数返回什么、在哪个位置（前 / 中 / 后序）处理当前节点、递归的终点是什么。难点不在代码长度（多数树题十行以内），而在返回值和”要更新的全局答案”不是一回事：直径、最大路径和、LCA 这类题，递归返回的是”向下的一条链”，答案在合并处产生。这一篇用七道主讲题把这个框架讲透，顺带把迭代遍历、层序、序列化、BST 的性质讲清。本篇要回答的核心问题是：递归函数”返回什么”和”更新什么”为什么常常不是同一个量？1 验证 BST 为什么不能只比较父子节点？2 前序 + 中序建树时，哈希表和递归指针各解决什么问题？3 ...

Posted by arganzheng | December 6, 2025

面试手撕代码（04）：链表

Linked Lists: Dummy Heads, Three Pointers and the Tortoise–Hare Proof

链表题不考算法，考手稳：指针改错一个顺序就丢掉半条链。它在面试里出现频率极高，因为十分钟内能看出一个人写代码是不是有章法——有没有用哑节点统一头节点的特殊情况、反转时三个指针的赋值顺序对不对、边界（空链表、单节点、恰好整除）有没有想到。这一篇把链表题的三个骨架（哑节点、三指针反转、快慢指针）讲透，六道主讲题覆盖反转家族、环、合并与排序，每道都画出指针的移动。本篇要回答的核心问题是：哑节点到底省掉了哪些特判？1 快慢指针相遇后，为什么一个指针回到头、两个同速再走就在环入口相遇？2 K 个一组反转怎样做到 O(1) 空间且代码不失控？3 一、识别信号题面里出现想到骨架 ...

Posted by arganzheng | December 5, 2025

面试手撕代码（03）：栈、单调栈与单调队列

Stacks, Monotonic Stacks and Monotonic Queues: Settle When You Pop

栈解决的是”最近的未完成事项“：括号匹配里最近一个没配对的左括号、表达式里最近一个还没结算的运算数、嵌套字符串里最近一个还没展开的 [。单调栈是它的特化——栈里的元素保持单调，于是”弹出”这个动作有了新含义：被弹出的元素在此刻找到了它右侧第一个更大（或更小）的数，左侧第一个更大的就是新栈顶。每日温度、柱状图最大矩形、接雨水都是这一句话。单调队列把同样的想法用在滑动窗口上：队首永远是窗口最值。这一篇的六道主讲题，前三道是普通栈（括号、解码、计算器），后三道是单调结构（每日温度、柱状图、滑窗最大值）。每道题的代码都短，但”弹出时结算什么”这一句必须想清楚。本篇要回答的核心问题是：单调栈里的元素弹出时，为什么左右两侧的边界同时确定了？1 柱状图最大矩形的...

Posted by arganzheng | December 4, 2025

面试手撕代码（02）：双指针与滑动窗口

Two Pointers and Sliding Windows: Monotonicity Turns O(n²) into O(n)

上一篇用哈希表换掉一层循环；这一篇不用额外空间，靠单调性做同一件事。两个指针都只往一个方向走，每个元素最多被每个指针经过一次，\(O(n^2)\) 的枚举就变成了 \(O(n)\)。它有三种形态：同向的滑动窗口（子串、子数组问题）、相向的对撞指针（有序数组的配对、面积、接雨水）、同向不同速的快慢指针（原地分区、链表中点）。三种形态的代码骨架都不到十行，难点全在什么时候动哪个指针——这个决定必须能用一句话证明”不动的那种情况不可能更优”。本篇要回答的核心问题是：滑动窗口的”右扩左收”什么时候成立、什么时候不成立？1 最小覆盖子串里”已满足的字符数”怎样让每一步都是 O(1)？2 接雨水的双指针为什么可以只看自己这一侧的最大值？3 一、识别信号 ...

Posted by arganzheng | December 3, 2025

面试手撕代码（01）：数组、哈希与前缀和

Arrays, Hashing and Prefix Sums: Trade Space for a Loop

数组题是面试的开场题：题面短、代码短、十分钟内必须写完。它考的其实只有一件事——能不能用一张哈希表换掉一层循环。两数之和是”边查边存”，和为 K 的子数组是”前缀和 + 哈希计数”，最长连续序列是”只从起点数”，缺失的第一个正数是”把数组自己当哈希表”。四个题四种用法，背后是同一个动作：把”我之前见过什么”记下来，让第二层循环变成一次 O(1) 查询。这一篇把哈希的四种用法、前缀和与差分这对互逆操作、以及原地哈希讲清楚，五道主讲题每道给完整的推演和 Python / Java 两个版本。本篇要回答的核心问题是： “和为 K 的子数组个数”为什么是前缀和 + 哈希，而不是滑动窗口？1 “最长连续序列”怎样做到 O(n) 而不排序？2 “缺失的第一个正数...

Posted by arganzheng | December 2, 2025

面试手撕代码：从 LeetCode 中等题到 Transformer 组件（总纲）

Coding Interviews: From LeetCode Mediums to Hand-Written Transformer Components

内容简介《面试手撕代码》是一组共十九篇的系列文章，面向要参加 AI 算法 / AI-Infra / 后端岗位面试、需要在白板或共享编辑器上当场写出能跑的代码的求职者。前十三篇覆盖 LeetCode 中等偏上难度的算法题——按解题模式而不是按数据结构的名字组织，每篇讲清一种模式怎么识别、模板长什么样、三到五道最典型的题怎样从题面推到代码、面试官会顺着问什么；后六篇覆盖 AI 岗位特有的”手撕模型组件”——attention、Transformer block、反向传播、tokenizer、采样、损失函数、经典 ML 与评测指标、以及 Infra 岗的并发与系统题。它回答的问题是：面试官给你一道没见过的中等题，四十分钟。你怎样在前五分钟认出它属于哪一类...

Posted by arganzheng | December 1, 2025

Python 中如何定义数据类并做校验：从 init、dataclass 到 Pydantic

在 Python 编程中，我们经常需要定义各种数据结构（如用户信息、配置项、API 请求体）。传统的写法不仅伴随着大量重复的模板代码，还面临着数据校验繁琐的痛点。本文将带你梳理从原生 init、标准库 @dataclass 到 Pydantic 的演进过程，带你看看现代 Python 是如何优雅地处理数据建模与校验的。同时为了方便Java程序员快速上手，我们也横向对比了Java 生态（Record / Lombok / Bean Validation）的实现差异。一、 Python 语法的演进：三种数据模型的构建方式 1. 传统流派：原生的 init 构造方法在最传统的面向对象写法中，我们通过显式定义构造函数来接收并赋值属性。 class Use...

Posted by arganzheng | July 22, 2024

测试驱动开发

什么是TDD TDD的核心思想是先写测试用例，然后通过测试来推动整个开发的进行，包括接口的设计，代码的编写和重构。整个TDD的过程就是红绿蓝三色循环迭代：为什么要推行TDD 首先一个显而易见的好处就是编码阶段，通过单元测试验证我们的代码，可以方便的进行本地自测，提高代码的质量。《重构》中Matin Flower就说：一套测试就是一个强大的bug侦测机，能够大大缩减查找bug所需的时间。但是TDD最大的好处还在于它不只是覆盖编码阶段，还对设计阶段产生重大影响。因为要提前写测试用例，意味着我们需要从接口调用方的角度使用我们定义的接口，这种角色的换位会让我们更好的设计出面向用户的友好接口。并且，为了能够单元测试该接口，在接口设计上还会考虑到接口的可...

Posted by arganzheng | August 1, 2020

Arganzheng's Blog

面试手撕代码（07）：二分——只有一个模板

Binary Search: One Template, First Position Where the Predicate Holds

面试手撕代码（06）：图——BFS / DFS / 拓扑排序 / 并查集 / 最短路

Graphs: BFS, DFS, Topological Sort, Union-Find and Dijkstra

面试手撕代码（05）：二叉树

Binary Trees: Three Questions Every Recursion Must Answer

面试手撕代码（04）：链表

Linked Lists: Dummy Heads, Three Pointers and the Tortoise–Hare Proof

面试手撕代码（03）：栈、单调栈与单调队列

Stacks, Monotonic Stacks and Monotonic Queues: Settle When You Pop

面试手撕代码（02）：双指针与滑动窗口

Two Pointers and Sliding Windows: Monotonicity Turns O(n²) into O(n)

面试手撕代码（01）：数组、哈希与前缀和

Arrays, Hashing and Prefix Sums: Trade Space for a Loop

面试手撕代码：从 LeetCode 中等题到 Transformer 组件（总纲）

Coding Interviews: From LeetCode Mediums to Hand-Written Transformer Components

Python 中如何定义数据类并做校验：从 init、dataclass 到 Pydantic

测试驱动开发

ABOUT ME

HOT TAGS

RECOMMEND

面试手撕代码（07）：二分——只有一个模板

Binary Search: One Template, First Position Where the Predicate Holds

面试手撕代码（06）：图——BFS / DFS / 拓扑排序 / 并查集 / 最短路

Graphs: BFS, DFS, Topological Sort, Union-Find and Dijkstra

面试手撕代码（05）：二叉树

Binary Trees: Three Questions Every Recursion Must Answer

面试手撕代码（04）：链表

Linked Lists: Dummy Heads, Three Pointers and the Tortoise–Hare Proof

面试手撕代码（03）：栈、单调栈与单调队列

Stacks, Monotonic Stacks and Monotonic Queues: Settle When You Pop

面试手撕代码（02）：双指针与滑动窗口

Two Pointers and Sliding Windows: Monotonicity Turns O(n²) into O(n)

面试手撕代码（01）：数组、哈希与前缀和

Arrays, Hashing and Prefix Sums: Trade Space for a Loop

面试手撕代码：从 LeetCode 中等题到 Transformer 组件（总纲）

Coding Interviews: From LeetCode Mediums to Hand-Written Transformer Components

Python 中如何定义数据类并做校验：从 __init__、dataclass 到 Pydantic

测试驱动开发

ABOUT ME

HOT TAGS

RECOMMEND

Python 中如何定义数据类并做校验：从 init、dataclass 到 Pydantic