LRU 缓存机制
哈希表负责“找得快”，双向链表负责“挪得快”，两个 O(1) 的结构各管一半，拼出完整的 O(1)。
LEARNING IN PUBLIC · 2026
把每一道题，
沉淀为可复用的思路。
这里记录我的 LeetCode 学习过程：不只写答案，也留下推导、踩坑， 以及可以迁移到下一道题的模式。
- 笔记
- 87 篇
- 已归类模式
- 24 类
- 最近更新
- 2026-07-16
# 一次遍历 · O(n)
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] = iHASH MAPTIME O(n) · SPACE O(n)
01问题拆解02复杂度分析03模式归纳04定期复盘
LATEST NOTES最近整理
共 87 篇 · 持续更新
- 146Medium
- 053
最大子数组和
把状态定义成“以 i 结尾的最大和”，转移就只剩一个选择：前面的和是正资产就带上，是负资产就抛弃重开。
Medium - 206
反转链表
反转的本质是逐个改写 next 指针，难点在于改指针之前别把后继节点弄丢。
Easy - 001
两数之和
用一次遍历和一张哈希表，把“寻找另一个数”从线性搜索降到常数时间。
Easy - 416
分割等和子集
分成两个等和子集等价于“能否从数组里凑出 sum/2”，这是标准的 0/1 背包，一维数组必须倒序刷。
Medium - 704
二分查找
二分的难点不在取中点，而在于始终说清楚搜索区间的定义。
Easy - 347
前 K 个高频元素
频次最大不超过 n，把它当下标开桶，排序这一步就被计数替代了——O(n) 拿到前 K 高频。
Medium - 101
对称二叉树
对称不是一棵树的性质，而是两棵子树互为镜像的性质，问题从一元变成了二元。
Easy - 003
无重复字符的最长子串
用滑动窗口维护一个始终合法的区间，并在右边界移动时更新答案。
Medium - 215
数组中的第K个最大元素
快速排序每趟 partition 都能确定一个元素的最终位次，只要这个位次恰好是 n-k，剩下的排序都可以不做。
Medium - 207
课程表
判断能否修完所有课就是判断有向图无环：不断摘掉入度为 0 的点，摘得完就无环。
Medium - 141
环形链表
快慢指针每轮把间距缩短一格，只要有环就一定追上，这是它必然相遇的原因。
Easy - 494
目标和
设正号子集的和为 p，由 p - (sum - p) = target 解出 p = (sum + target) / 2，问题瞬间变成“凑出 p 的方案数”计数背包。
Medium - 005
最长回文子串
与其枚举子串再验证是不是回文，不如枚举回文的中心向两边扩——回文的对称性让验证和枚举合二为一。
Medium - 236
二叉树的最近公共祖先
递归返回值只回答一个问题——这棵子树里有没有 p 或 q；左右都给出肯定答复的最深节点，就是 LCA。
Medium - 020
有效的括号
括号匹配的本质是“最近打开的必须最先关闭”，这正好是栈的定义。
Easy - 253
会议室 II
把开始时间和结束时间拆开各自排序，双指针推进：某场会议开始时还没有任何会议结束，就必须新开一间房。
Medium - 128
最长连续序列
排序思路被 O(n) 卡死后，出路是让每段连续序列只从它的起点被数一次——“v-1 不在集合里”这一判断就是起点的身份证。
Medium - 208
实现 Trie（前缀树）
每个节点开 26 个孩子槽位，单词沿字符逐层走；insert、search、startsWith 其实共用同一副“走链”骨架。
Medium - 160
相交链表
两个指针各自走完自己再走对方，走过的总长相同，会在交点或同时到达终点相遇。
Easy - 105
从前序与中序遍历序列构造二叉树
前序的第一个元素永远是根，拿它去中序里一切两半，左右子树的边界就都确定了——递归只传下标区间，不必真的切数组。
Medium - 056
合并区间
按左端点排序后，结果集里的区间彼此隔开，新区间够不着最后一个就更够不着前面的——所以只需和最后一个比较。
Medium - 033
搜索旋转排序数组
旋转破坏了全局有序，但从中点切开，必有一半仍然完整有序——二分不需要全局有序，只需要每次都能安全地扔掉一半。
Medium - 102
二叉树的层序遍历
队列天然按访问顺序吐出节点，但要按层分组，诀窍是在每层开始前先把“当前队列长度”定格下来。
Medium - 022
括号生成
合法性可以在构造过程中步步维持——左括号没用完就能加，右括号少于左括号才敢加，剪枝后每条路径都通向合法解。
Medium - 019
删除链表的倒数第 N 个节点
让快指针先走 n 步制造固定间距，快指针到尾时慢指针恰好停在待删节点的前驱——一遍扫描就把“倒数”变成“同步走”。
Medium - 300
最长递增子序列
dp[i] 按“以谁结尾”分类是子序列 DP 的通用入口；而 tails 抓住“同长度下结尾越小越有潜力”，用二分替换把复杂度压到 O(n log n)。
Medium - 070
爬楼梯
到第 n 阶的走法数 = 到 n-1 阶 + 到 n-2 阶，它其实就是斐波那契。
Easy - 200
岛屿数量
每发现一块陆地就用 DFS 把整座岛“淹掉”，网格本身就是 visited 数组——计数器加一的时机比遍历本身更本质。
Medium - 114
二叉树展开为链表
后序思维：左右子树各自先展开成链，再把左链整体插到根和右链之间——大问题只做一次“接线”。
Medium - 017
电话号码的字母组合
每个数字对应一小组字母，答案是各组的笛卡尔积，回溯按位递归拼接就是逐层展开这个乘积。
Medium - 046
全排列
回溯就是把“做选择”的循环和“撤销选择”的复原动作夹住一次递归——path 与 used 进什么状态，返回前就得退回什么状态。
Medium - 021
合并两个有序链表
用一个哨兵节点省掉“第一个节点特殊处理”的分支，合并就退化成不断挑更小的那个。
Easy - 148
排序链表
链表不能随机访问，堆排快排都施展不开，但归并只需要“找中点、断开、合并”这三个链表恰好擅长的动作。
Medium - 015
三数之和
排序把“找组合”变成“找有序对”，而去重不靠哈希集合，靠的是在三个位置各跳过一次重复值。
Medium - 049
字母异位词分组
互为异位词的字符串排序后完全相同——给每个词算出一个“规范形式”当哈希键，同键即同组。
Medium - 079
单词搜索
网格 DFS 逐字符匹配，把走过的格子原地改掉当访问标记，回溯时改回来，一个 visited 数组都不用开。
Medium - 062
不同路径
到达每个格子的路径数等于上方与左方之和，一维数组从左到右滚动时旧值恰好就是“上方”。
Medium - 394
字符串解码
括号天然嵌套，嵌套就用栈：遇 [ 把“外层进度”存档，遇 ] 取档拼接，当前层永远只处理自己的事。
Medium - 152
乘积最大子数组
负数一乘会把最大翻成最小、最小翻成最大，所以要同时维护以 i 结尾的最大积与最小积。
Medium - 064
最小路径和
只能向右或向下，意味着每个格子的来源只有上、左两个——取较小者累加，网格本身就是一张现成的 dp 表。
Medium - 039
组合总和
组合去重的关键是给候选定一个顺序，只准往后选不准回头；“可以重复用”体现在递归时 start 传 i 而不是 i+1。
Medium - 234
回文链表
把找中点、反转后半、再对比拼在一起，就能在 O(1) 空间里判断链表是否回文。
Easy - 094
二叉树的中序遍历
递归天然记住了“回来以后接着往下走”，显式栈就得自己把这件事补上。
Easy - 739
每日温度
递减栈里压着的是“还没等到更暖日子”的下标，更高的温度一到，就把能结算的全部弹出来结算。
Medium - 078
子集
每个元素独立地面临“选或不选”两个分支，2^n 个叶子恰好对应 2^n 个子集——回溯树的形状就是答案的结构。
Medium - 048
旋转图像
顺时针转 90° 可以拆成两次镜像：先沿主对角线转置，再把每行左右反转。
Medium - 337
打家劫舍 III
树形 DP 的入门题：每个节点向父节点上报（偷它, 不偷它）两个值，父节点无法预知哪个更优，所以两个都得传。
Medium - 011
盛最多水的容器
面积受制于短板，移动长板宽度变小、高度封顶，不可能更优——所以每次只动较短的一边。
Medium - 142
环形链表 II
快指针走的路程恰好是慢指针的两倍，这个等式化简后给出 a = (n-1)(b+c) + c——从头和从相遇点同速出发，必在入口碰面。
Medium - 104
二叉树的最大深度
把整棵树的深度拆成子树的深度加一，递归就成了对定义的直接翻译。
Easy - 121
买卖股票的最佳时机
只买卖一次，答案就是“每天卖出”时能拿到的最大利润，而它只依赖历史最低价。
Easy - 031
下一个排列
字典序的“下一个”意味着改动越靠右越好、换上的数刚好大一点、后缀降到最小——三条贪心叠出四步指针操作。
Medium - 240
搜索二维矩阵 II
站在右上角，这个矩阵就是一棵二叉搜索树：往左变小，往下变大，每次比较排除一行或一列。
Medium - 136
只出现一次的数字
异或让成对的数字自我湮灭，无需额外空间就能把落单的那个筛出来。
Easy - 647
回文子串
每个回文都有一个中心，枚举 2n-1 个中心向两侧扩展，扩一步成功就多一个回文子串。
Medium - 098
验证二叉搜索树
BST 的约束是全局的：每个节点要落在祖先划定的 (low, high) 开区间里，只比较父子必然漏判。
Medium - 096
不同的二叉搜索树
以 i 为根时左右子树各自独立，形态数按乘法原理相乘，再对所有根求和，G(n) 正是卡特兰数。
Medium - 075
颜色分类
荷兰国旗三指针：0 换到前面、2 换到后面，唯一的陷阱是和后面交换回来的数还没检查，i 不能动。
Medium - 055
跳跃游戏
不必记录怎么跳，只要一路维护“最远能到哪”——当前位置一旦超出这个边界，就永远补不回来了。
Medium - 034
在排序数组中查找元素的第一个和最后一个位置
一个 lower_bound 就够了：左边界是 target 的第一个位置，右边界是 target+1 的第一个位置减一。
Medium - 221
最大正方形
以 (i,j) 为右下角的正方形能有多大，由左、上、左上三个邻居中最短的那块板决定——min 三者加一，就是木桶原理在网格上的写照。
Medium - 002
两数相加
逆序存储恰好让低位对齐，加法可以边走边算；把 carry 写进循环条件，最高位进位就不需要任何特判。
Medium - 322
零钱兑换
和爬楼梯同一张递推图，但目标从“数路径条数”换成“找最短路径”，加法变成取 min，初值也要跟着从 0 变成无穷大。
Medium - 287
寻找重复数
把 nums[i] 看成 i 指向 nums[i] 的边，重复的数就是两条边汇入的节点——链表环的入口，Floyd 判环直接套用。
Medium - 155
最小栈
让每个元素在入栈时就记住“它之下的最小值”，getMin 就退化成读栈顶。
Medium - 560
和为 K 的子数组
子数组和为 k 等价于两个前缀和相差 k，用哈希表数“sum - k 出现过几次”，一遍扫完。
Medium - 139
单词拆分
dp[i] 只回答“前 i 个字符能否拆开”，内层枚举最后一个单词从哪里开始，查表交给哈希集合。
Medium - 238
除自身以外数组的乘积
不许用除法，就把“除自身”拆成左边前缀积乘右边后缀积，两趟扫描各补一半。
Medium - 226
翻转二叉树
翻转整棵树等于交换根的左右孩子，再让两棵子树各自翻转——一个动作递归下去就够了。
Easy - 309
最佳买卖股票时机含冷冻期
冷冻期让“空仓”分裂成两种：刚卖完的和可以买的，三状态机把转移关系一次说清。
Medium - 198
打家劫舍
每间房只有偷与不偷两种选择，最优值只依赖前两间的结果——骨架和爬楼梯完全同构。
Medium - 437
路径总和 III
树上一条向下的路径和等于两个“根到节点”前缀和之差，用哈希表存前缀和，递归返回时记得撤销。
Medium - 283
移动零
把“搬运零”反过来想成“收拢非零元素”，一个慢指针就能标记它们该落的位置。
Easy - 279
完全平方数
每个平方数都能无限次使用，这是完全背包求最小件数：dp[i] = min(dp[i - j²]) + 1。
Medium - 543
二叉树的直径
直径的答案藏在每个节点的“左深 + 右深”里，顺着求深度的递归就能顺手捞出来。
Easy - 169
多数元素
摩尔投票把“统计谁最多”变成“互相抵消”，多数元素靠数量优势一定活到最后。
Easy - 617
合并二叉树
让两棵树的指针同步下探，空节点就地把位置让给另一棵，合并只需处理“同时存在”这一种情况。
Easy - 581
最短无序连续子数组
无序段的边界由“越界”的元素决定，一左一右两趟扫描就能同时定位两端。
Medium - 621
任务调度器
最高频任务决定了时间轴的骨架，答案是 (maxCount-1)*(n+1)+同频任务数与总任务数的较大者。
Medium - 438
找到字符串中所有字母异位词
窗口长度固定，每滑一步只有一进一出两个字符，维护差异计数就能把比较降到 O(1)。
Medium - 399
除法求值
把每个等式看成带权边（a→b 权 a/b），查询就变成在图上找一条路径并把沿途权重乘起来。
Medium - 538
把二叉搜索树转换为累加树
反着中序遍历，节点就按从大到小的顺序出现，一个累加变量便能一路加下去。
Medium - 338
比特位计数
i 右移一位只丢掉最低位，所以 bits[i] = bits[i >> 1] + (i & 1)，答案表自己递推自己。
Easy - 461
汉明距离
先用异或把“不同的位”变成 1，问题就归结成“数一个数里有几个 1”。
Easy - 406
根据身高重建队列
先安排最高的人，矮个按 k 值插队不会破坏任何已就位者的 k——排序定顺序，插入定位置。
Medium - 448
找到所有数组中消失的数字
数值范围恰好等于下标范围，把数组本身当哈希桶，用正负号记录谁来过。
Easy
KNOWLEDGE MAP
不是刷题清单，
是我的模式库。
把零散题目归回核心数据结构与算法模式，下一次遇见相似问题时，能更快识别它。
01
数组与哈希
15 篇02
双指针
16 篇03
滑动窗口
2 篇04
二分查找
5 篇05
链表
10 篇06
二叉树
15 篇07
栈
5 篇08
单调栈
1 篇09
递归
13 篇010
分治
4 篇011
回溯
7 篇012
动态规划
20 篇013
贪心
5 篇014
位运算
4 篇015
图
3 篇016
深度优先
2 篇017
广度优先
2 篇018
堆
3 篇019
排序
7 篇020
前缀和
3 篇021
矩阵
3 篇022
区间
2 篇023
字典树
1 篇024
设计
2 篇ABOUT THIS LOG
“理解一道题的标志，不是记住代码，而是能说清楚为什么这样做。”