随机化题的难点通常不在代码，而在「为什么每个结果的概率真的相等」。代码往往只有十来行，写错一个下标范围，分布就悄悄歪掉，样例还照样能过——判题器至多做统计检验，样例过了不代表分布对，自己肉眼更看不出来。所以这类题我的习惯是：先拿 n = 2、3 这种小数把概率一项项乘出来，乘对了再写代码。
本合集收录随机化类题目：$O(1)$ 增删 + 随机取（380、381）、按权重随机（528）、链表随机节点 / 蓄水池（382、398）、洗牌（384）、用 rand7 造 rand10（470）等题型。先放一节 Python 随机数速查模板，题目小节随训练进度补上。
区间题看着花样多，拆开来常常只剩一件事：把每个区间拆成「开始」和「结束」两个事件，按时间扫一遍。本合集收录区间类题目。
给一组会议 [start, end]，求最少需要几间会议室。
我的第一版：排序 + 堆，模拟分配。 按开始时间排序，堆里放每间会议室什么时候空出来。新会议到来时看最早空出来的那间：能用就复用，不能用就新开。11 分钟 AC：
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
hp = [...DP 的胜负手在状态定义——状态立住了，转移不过是水到渠成。本合集收录状态定义与递推方向设计类的题目（复杂度优化技巧类见《优化DP》），随训练持续补完。
有 n 对门，每对门分左、右两个通道。初始时左右通道各有 1 个人，且已在通道内的人不能中途切换通道。
通过第 i 对门的某个具体门（左或右）时：
+ a：额外产生 a 个新人，该通道原有人数不变。x a：设该通道操作前有 P 人，操作后变为 P·a 人——相当于原有 P 人保持为「基底」，额外新增 (a...图论一类题的合集，随训练持续补完。用 Python 打 CF，除了算法本身，还得和语言特性过几招——这类实战经验也一并记录在此。
题意：给出无序的边集，它们构成一条链，从端点按序输出这条唯一路径。
思路本身朴素：度为 1 的点是端点，从任一端点 dfs 走到底即可。这题真正的收获是两条 Python 实战经验：
sys.setrecursionlimit(int(2 * 10**5...数据结构里的高达：拼装麻烦，但拼好之后区间问题基本横着走。本合集收录线段树题目，随训练持续补完。
用 Python 重写的线段树模板。线段树的记忆点在于写代码时脑子里要有那棵树——自顶向下构建，节点 root 的左右孩子是 2*root 和 2*root+1，懒标记在下探时才向下推。数组开 4n：这样建出的树高不超过 $\lceil \log_2 n \rceil + 1$ 层，节点编号小于 $2^{\lceil \log_2 n \rceil + 1} < 4n$，开 4n 一定够用。
代码末尾的驱动部分按洛谷 P3372 的输...
字典树（Trie）是前缀匹配的专用兵装：把一堆字符串挂在同一棵树上，前缀问题就变成了从根往下走的问题。本合集收录字典树题目。
模板题。唯一容易漏的点：节点上要挂 is_end 标记单词结束，否则「前缀存在」和「单词存在」区分不开。
对每个单词找最短的词根前缀。沿树下行，一碰到 is_end 就停——最先命中的就是最短前缀；走不下去也没碰到 is_end，就保留原词。
要求输出所有最顶级的父文件夹。坑在 / 的特判：前缀匹配上不代表就是父文件夹，/a/b 是 /a 的子文件夹，但 /ab 不是——...
表达式解析是栈的看家副本：数字栈、符号栈、递归下降，三件套凑齐就能通关四则运算全系列。本合集收录栈类题目。
中缀表达式求值一般要维护数字、操作符两个栈；这题操作符顺序是固定循环的，可以省掉操作符栈，只留一个数字栈：乘除和栈顶连着算，加号把数正着入栈，减号把数取负入栈，最后求和。需要注意负数除法的取整方向：题目里的数都是正数，但减号后的那段乘积以负数入栈后再做除法，Python 的 // 向下取整（-42 // 5 == -9），而这里要的是先算正数的商再取负（-8），得写成 int(a / b) 或对绝对值做除法。
可...
前缀和的核心式只有一条：子数组和可以写成两个前缀和之差。记 $s_j$ 为前 j 个元素之和（$s_0 = 0$），第 i 到第 j 个元素（从 1 开始数）的和就是 $\text{sum}(i, j) = s_j - s_{i-1}$。围绕这条式子做变形，就是本合集的全部内容。
题意：是否存在长度大于 1 的子数组，其和能被 k 整除。
前缀和的经典问题，务必掌握。把子数组记成第 i+1 到第 j 个元素（长度为 j - i），它的和写成 $s_j - s_i$ 后，「和能被 k 整除」即 $s_j - s_i \equiv 0 \pm...
双指针的精髓在于「不回头」：每个元素只被指针扫过常数次，$O(n^2)$ 的枚举就塌缩成 $O(n)$。本合集收录滑动窗口与双指针题目。
同向双指针的一种特殊形态：左端点 start 只在每组开头记一次，右端点就是循环变量 i 本身，组与组之间不回退。
数组会被切成若干组，每一组的处理逻辑相同。
外层循环负责进组前的准备（记录起点）和出组后的统计（更新答案）；内层循环负责走完这一组，找出它最远在哪结束。
n = len(nums)
i = 0
while i < n:
start = i
i += 1 # a gro...数论小道具一件：把每个数的平方因子全部剥掉，剩下的「核」才是判断乘积是否为完全平方数的本体。
先澄清名字：本文的「平方剩余核」指无平方因子核（square-free core，也叫 square-free part），和数论里的「平方剩余」（二次剩余，quadratic residue）是两个不同的概念，不要混淆。
平方剩余核 core(n)（square-free core）：n 除以它的最大完全平方因子后剩下的部分，结果一定不含平方因子。例如 core(12) = 12 / 4 = 3，core(18) = 18 / 9 = 2，core(72) = 72 / 36...