分类标签归档：leetcode
字典树（Trie）是前缀匹配的专用兵装：把一堆字符串挂在同一棵树上，前缀问题就变成了从根往下走的问题。本合集收录字典树题目。
模板题。唯一容易漏的点：节点上要挂 is_end 标记单词结束，否则「前缀存在」和「单词存在」区分不开。
对每个单词找最短的词根前缀。沿树下行，一碰到 is_end 就停——最先命中的就是最短前缀。
要求输出所有最顶级的父文件夹。坑在 / 的特判：前缀匹配上不代表就是父文件夹，/a/b 是 /a 的子文件夹，但 /ab 不是——匹配结束后下一位是 / 的才算。
表达式解析是栈的看家副本：数字栈、符号栈、递归下降，三件套凑齐就能通关四则运算全系列。本合集收录栈类题目。
逆波兰一般要维护数字、操作符两个栈；这题操作符顺序是固定循环的，可以省掉操作符栈。乘除是连着算的，加法单独算，减法减的总是一段乘除的结果，按此模拟即可。需要注意负数除法的取整方向。
可以用栈迭代模拟，也可以 dfs。这里新学了一个名词：这种 dfs 叫递归下降解析——「下降」指从最高层级一层层往下匹配，是处理嵌套结构的标准方式。
它的特点是维护一个全局 index 扫描字符串。相比每次去搜索匹配的右括号（$O(n...
前缀和的核心式只有一条：子数组和可以写成两个前缀和之差，$\text{sum}(i, j) = s_j - s_{i-1}$。围绕这条式子做变形，就是本合集的全部内容。
题意：是否存在长度大于 1 的子数组，其和能被 k 整除。
前缀和的经典问题，务必掌握。子数组和写成 $s_j - s_i$ 后，「和能被 k 整除」即 $s_j - s_i \equiv 0 \pmod k$，移项立刻得到关键结论：两个前缀和关于 k 同余。
于是一遍扫描：把出现过的前缀和对 k 的余数塞进哈希表，扫到每个新前缀和时 $O(1)$ 查同余的旧前缀和是否存...
双指针的精髓在于「不回头」：每个元素只被指针扫过常数次，$O(n^2)$ 的枚举就塌缩成 $O(n)$。本合集收录滑动窗口与双指针题目。
同向双指针的一种特殊形态，可以省掉一个显式指针。
数组会被切成若干组，每一组的处理逻辑相同。
外层循环负责进组前的准备（记录起点）和出组后的统计（更新答案）；内层循环负责走完这一组，找出它最远在哪结束。
n = len(nums)
i = 0
while i < n:
start = i
while i < n and ...:
i += 1
# 从 star...数论小道具一件：把每个数的平方因子全部剥掉，剩下的「核」才是判断乘积是否为完全平方数的本体。
平方剩余核 core(n)（square-free core）：n 除去所有完全平方因子后剩下的部分。
线性筛的写法，一次预处理出值域内所有数的 core：
MX = 100_001
core = [0] * MX
for i in range(1, MX):
if core[i] == 0:
for j in range(1, isqrt(MX // i) + 1):
core[i * j * j] = i
外层扫到的...
数位 DP 是「统计 $[1, n]$ 内满足某性质的数字个数」这类题的专用咏唱，模板一旦焊死，剩下的只是换性质。本合集收录数位 DP 题目。
模板题。用记忆化搜索实现比递推直观得多，状态需要携带四样信息：
i：当前填到第几位；mask：已选数字的集合，避免重复选数；is_limit：前面是否一直顶着上界在填——顶着上界时，当前位的可选范围受 n 对应位限制，否则 0 到 9 随便填；is_num：是否已经开始计数，用来处理前导零。class Solution:
def countSpecialNumbers(self, n...朴素转移超时，不是 DP 的终点，而是优化的起点。本合集收录「先写对、再打磨复杂度」的 DP 优化技巧题（状态怎么设计的题在《DP 状态设计》里）。
寻找子问题：如果长度为 n 的序列此刻是「递增收尾」的，那它的前一个状态必须是「递减收尾」的，且第 n 个数（index 从 1 开始）大于第 n-1 个数。于是状态需要两个维度、两个数组：维度 i 表示当前序列长度，维度 j 表示当前结尾的数字；dp1 表示以递增收尾的方案数，dp2 表示以递减收尾的方案数，两者的转移完全对称。为简化计算，把值域 $[l, r]$ 平移到 $[0, r-l...
堆只会两招：弹最值、塞新值。但配上贪心，这两招足以打穿一整个题库——反悔堆更是贪心流的后悔药，吃下去连悔棋都是 $O(\log n)$ 的。本合集收录堆类题目。
最小堆解法：先把最小的丑数 1 入堆，每次弹出最小值 x，把 2x、3x、5x 入堆，用哈希表去重。弹 n 次即得第 n 个丑数。
枚举所有点对至少 $O(n^2)$ 起步，必须利用两数组非递减的性质。想象一个矩阵：纵坐标是 nums1 下标，横坐标是 nums2 下标，矩阵值是数对和。这个矩阵每行非递减、每列也非递减，左上角 (0, 0) 是全局最小。
于...
树题是刷题修行的主线任务之一。本合集按套路分节收录二叉树题目：每题给出关键观察、做法与复杂度。
BST 的第一反应是中序遍历——中序遍历 BST 会得到一个严格递增的序列，大量题目围绕这条性质展开。
中序遍历得到递增序列，对每个询问在序列上做一次二分查找。时间复杂度 $O(n \log n)$。
合并 BST。需要先观察出两条性质：