LeetCode Hot 100

利用异或运算的自反性，将所有元素依次异或，出现两次的数会两两抵消为 0。

Boyer-Moore 投票算法：维护候选者和计数器，不同则抵消，最终剩下的就是多数元素。

先异或标记不同位，再用 Brian Kernighan 算法统计 1 的个数。

用哈希表存储已遍历的数，一次遍历即可找到互补对。

将字符串排序后作为哈希表的键，相同字母组合映射到同一个键。

利用哈希集合实现 O(1) 查找，只从序列起点开始向右扩展。

快慢指针：快指针探索非零元素，慢指针标记放置位置。

对向双指针，贪心策略：移动较短的那端，才有可能增大盛水量。

排序 + 双指针：固定一个数后，在其后子数组中用双指针查找两数之和。

遇到左括号入栈，遇到右括号检查栈顶是否配对，遍历结束栈为空则合法。

辅助栈同步记录最小值，只在更小值出现时才压入辅助栈。

双指针消除长度差：走完一条链后切换到另一条，交点处相遇。

迭代法三指针：prev、curr、next，逐个反转指针方向。

哑节点 + 尾指针，每次比较两链表头节点，将较小的接到尾部。

Floyd 快慢指针：快指针每次两步，慢指针每次一步，有环必相遇。

递归交换每个节点的左右子树，分治思想的典型应用。

递归：max(左子树深度, 右子树深度) + 1，空节点深度为 0。

迭代法：一路向左压栈，弹出栈顶访问，转向右子树。

BFS 队列逐层遍历，记录每层大小实现按层分组。

跳跃式滑动窗口：右指针扩张，遇到重复时左指针直接跳到重复字符之后。

固定大小窗口滑动，用数组计数对比窗口与目标串的字符频率。

need/window 双字典 + valid 计数器，右扩左缩找最小满足条件的窗口。

Kadane 算法：dp[i] = max(dp[i-1] + nums[i], nums[i])，负前缀不如重新开始。

按起点排序后线性扫描，重叠区间合并为取更大终点。

两次遍历：左到右记录左侧乘积，右到左乘上右侧乘积，空间 O(1)。

三次翻转法：翻转全部 → 翻转前 k 个 → 翻转剩余部分。

标准二分查找，左闭右开区间，最终 left 即为插入位置。

两次二分：lower_bound 找第一个 ≥ target，upper_bound 找第一个 > target。

旋转数组仍满足"一半有序"，判断 mid 落在有序半边再确定 target 位置。

降维映射：将二维矩阵视为一维有序数组，mid 对应 (mid//n, mid%n)。

前缀和 + 哈希表：pre[j] - pre[i] = k 等价于 pre[j] - k = pre[i]。

双栈法：数字栈管重复次数，字符串栈管层级，遇到 ] 弹出重建。

维护历史最低价，每天计算当前价与最低价的差值取最大。

维护最远可达位置，遍历时若当前位置超过最远可达则无法继续。

维护当前跳跃边界和最远可达，到达边界时必须跳一次。

先记录每个字母最后出现位置，贪心扩展直到覆盖片段内所有字符。

经典回溯模板：选择 → 递归 → 撤销，用 used 数组去重。

每个节点都是答案，start 参数确保不重复选择前面的元素。

允许重复选同一元素（传 i 而非 i+1），remain < 0 提前返回剪枝。

right < left 保证合法性：任何前缀中左括号数 ≥ 右括号数。

DFS + 回溯：用 # 标记已访问，搜索完恢复，注意不回头（3个方向）。

维护大小为 k 的最小堆，堆满后弹出最小值，最终堆顶即第 k 大。

Counter 统计频率 + 大小为 k 的最小堆，堆满后弹出频率最低的。

斐波那契数列：dp[i] = dp[i-1] + dp[i-2]，空间优化为两个变量。

dp[i] = max(dp[i-1], dp[i-2] + nums[i])，抢当前 vs 不抢当前。

完全背包变体：dp[i] = min(dp[i - j²] + 1)，完全平方数即物品。

dp[i] = min(dp[i - coin] + 1)，凑出金额 i 的最少硬币数。

tails 数组 + 二分替换：tails[i] 表示长度 i+1 的递增子序列最小末尾。

快慢指针相遇后，一指针回 head，同步前进再次相遇处即入环点。

归并排序链表版：快慢指针找中点 → 递归排序两半 → 合并有序链表。

最小堆：所有链表头节点入堆，每次弹出最小节点并将其 next 推入堆。

哈希表 + 双向链表 / OrderedDict，get 和 put 均 O(1)。

逐位相加维护进位，divmod 同时得到商和余数，注意最终进位。

DFS/BFS 遍历连通块，遇到 1 时计数并将相连的 1 标记为已访问。

多源 BFS：所有腐烂橘子同时入队，逐层扩展记录扩散层数。

Kahn 算法拓扑排序：不断移除入度为 0 的节点，检查是否能完成所有课程。

每个节点含 children 字典和 is_end 标记，insert/search/prefixSearch 均 O(L)。

dp[i][j] = dp[i-1][j] + dp[i][j-1]，空间优化为一维数组。

中心扩展法：以每个字符和每对相邻字符为中心向两边扩展。

dp[i][j]：字符匹配则 dp[i-1][j-1]+1，否则 max(dp[i-1][j], dp[i][j-1])。

dp[i][j] = min(删除/插入/替换)，三种操作对应三个子问题。

中序遍历检查严格递增，或递归传递上下界验证每个节点。

中序遍历 BST 得到有序序列，第 k 个即为答案，可提前终止。

BFS 每层最后一个元素，或 DFS 优先右子树每层首个节点。

Morris 遍历思想：将右子树接到左子树最右节点后面，空间 O(1)。

前序首元素为根，中序找根位置划分左右子树，哈希表加速查找。

前缀和 + DFS：curr_sum - target 在哈希表中存在则存在合法路径。

后序遍历：两边都找到则当前为 LCA，只一边找到则 LCA 在那一侧。

同时维护最大乘积和最小乘积，遇负数时交换两者，应对负数翻转效应。

0-1 背包：能否选出和为 sum/2 的子集，从后往前遍历避免重复使用。

dp[i] = OR(dp[j] && s[j:i] in dict)，完全背包的字符串变体。

栈存储下标，-1 作哨兵，弹出后当前下标减栈顶即为有效长度。

原地标记：复用首行首列作为标记数组，需单独处理首行首列的零。

四边界收缩法：右→下→左→上逐层遍历，注意边界合法性检查。

顺时针 90° = 转置 + 水平翻转，原地操作 O(1) 空间。

从右上角开始搜索，利用行列有序性每步排除一行或一列。