分类标签归档：leetcode
随机化题的难点通常不在代码，而在「为什么每个结果的概率真的相等」。代码往往只有十来行，写错一个下标范围，分布就悄悄歪掉，样例还照样能过——判题器至多做统计检验，样例过了不代表分布对，自己肉眼更看不出来。所以这类题我的习惯是：先拿 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 = [...字典树（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...
数位 DP 是「统计 $[1, n]$ 内满足某性质的数字个数」这类题的专用咏唱，模板一旦焊死，剩下的只是换性质。本合集收录数位 DP 题目。
题意：如果一个正整数的各位数字互不相同，就称它为特殊整数；给定正整数 n，统计 $[1, n]$ 中特殊整数的个数。
模板题。用记忆化搜索实现比递推直观得多，状态需要携带四样信息：
i：当前填到第几位；mask：已选数字的集合，避免重复选数；is_limit：前面是否一直顶着上界在填——顶着上界时，当前位的可选范围受 n 对应位限制，否则 0 到 9 随便填；is_num：前面是否已经填过非零数...朴素转移超时，不是 DP 的终点，而是优化的起点。本合集收录「先写对、再打磨复杂度」的 DP 优化技巧题（状态怎么设计的题在《DP 状态设计》里）。
题意：统计长度为 n、每个元素都在 $[l, r]$ 内的数组个数，要求相邻元素不相等，且任意连续三个元素都不构成严格递增或严格递减（即上升、下降交替出现），答案对 $10^9+7$ 取模。$3 \le n \le 2000$，$1 \le l < r \le 2000$。
寻找子问题：如果长度为 i 的序列此刻是「递增收尾」的（第 i 个数大于第 i-1 个数，下标从 1 开始），那它的前...
堆只会两招：弹最值、塞新值。但配上贪心，这两招足以打穿一整个题库——反悔堆更是贪心流的后悔药，吃下去连悔棋都是 $O(\log n)$ 的。本合集收录堆类题目。
最小堆解法：先把最小的丑数 1 入堆，每次弹出最小值 x，把 2x、3x、5x 入堆，用哈希表去重。弹 n 次即得第 n 个丑数，时间复杂度 $O(n \log n)$。
枚举所有点对至少 $O(n^2)$ 起步，必须利用两数组非递减的性质。想象一个矩阵：纵坐标是 nums1 下标，横坐标是 nums2 下标，矩阵值是数对和。这个矩阵每行非递减、每列也非递减...