本项目记录算法学习笔记。总结每道题的核心思路、算法实现与正确性证明，提炼可复用的算法设计思想。
题目按 LeetCode 热题 100 官方学习计划 的专题顺序排列。已完成笔记：16/100；— 表示尚无解题笔记。
核心思想：二分查找划分边界。
划分思路本身比较简单，难点在于统一处理边界条件并保证算法正确性。
- 奇偶统一：统一使用
(m+n+1)//2确定划分位置，仅在返回中位数时区分奇偶。 - 数组边界：明确变量表示划分位置，而非数组下标；使用正负无穷大作为哨兵处理空区间。
- 循环不变量：利用条件的单调性进行二分查找，通过循环不变量证明不会遗漏目标位置，且最终结果不会被覆盖。
可复用经验： 明确变量含义，统一处理特殊情况，利用循环不变量证明算法正确性。
核心思想： 使用 set 加速成员查询，并仅从连续序列的最小元素开始向后检查，避免重复遍历。
- 避免不必要的约束：只需要保证整个算法最终得到正确结果，不必为每个中间步骤添加不必要的约束。
- 先求解，再优化：在有性能要求的问题上，先找到简单思路，再分析性能瓶颈并逐步优化。
核心思想： 使用双指针将非零元素按原顺序写入数组前部，再将剩余位置填零。
核心思想： 利用双指针维护左右两侧的最大高度，每次处理最大高度较小的一侧，逐步确定各位置的接水量。
- 从确定性出发：先解决能够确定结果的边界位置，再逐步扩展到未解决区域。
- 利用问题性质推进：根据接水量由左右最大高度的较小值决定这一性质，选择可以安全处理的一侧。
核心思想： 将问题分解为以不同位置为起点的子问题，再利用滑动窗口复用相邻子问题的计算结果，避免重复搜索。
- 解空间分解：按照某一维度划分候选解，分别求出局部最优解，再合并得到全局最优解。
- 增量计算：利用相邻子问题之间的关联，复用已有计算结果，避免重复计算。
核心思想： 通过解空间分解，将问题转化为统计每个起点或终点对应的合法子数组数量。按终点枚举更适合从左向右遍历：利用前缀和与哈希表维护历史信息，即可直接统计当前终点对应的合法起点，无需重复扫描后续元素，将时间复杂度从
核心思想： 通过解空间分解，将问题转化为判断每个固定长度的子串是否为字母异位词。利用滑动窗口复用相邻子问题的字符频次，并通过 diff 记录频次不匹配的字符种类数，采用新贡献减去旧贡献的方式增量更新，将每次窗口判断优化为
核心思想： 通过解空间分解，将问题规约为求解每个固定长度窗口的最大值。利用支配关系进行候选剪枝：当新元素在数值和有效期上均不劣于较早元素时，可以安全淘汰较早元素。使用单调队列增量维护最大值候选，将时间复杂度从
- 支配关系与候选剪枝：根据数值优势和位置优势，证明被支配的元素不可能再成为必须保留的最大值候选。
- 增量维护：通过队首删除过期元素、队尾淘汰被支配元素，实现窗口最大值的高效更新。
- 循环不变量：不变量只需在每轮完整迭代结束时成立即可。
核心思想： 通过解空间分解，将问题规约为寻找每个起点对应的最短合法子串。利用覆盖条件的单调性，通过滑动窗口使左右指针单向移动，避免枚举所有子串；使用字符需求表 need 和缺失计数 missing 增量维护覆盖状态，将时间复杂度从朴素枚举的
核心思想： 排序 + 贪心。朴素解法中，当前合并区间的最终结果依赖于所有剩余区间，需要反复检查。通过按左端点排序建立单调性，使得当前区间一旦与下一个区间不重叠，就必然与所有后续区间不重叠，从而实现局部解与剩余区间的解耦。局部解可以安全确定，无需回溯，将反复扫描转化为一次线性扫描。一般性的算法思路是：通过引入某种结构（排序、单调性、边界约束等），将原本相互依赖的子问题转化为可以独立确定的局部问题。
核心思想：原地标记。 将问题规约为判断 [1,n] 中各整数是否存在。通过建立整数 x 与数组下标 x-1 的映射关系，利用数组元素的正负号记录存在性，并通过绝对值保留原始数值信息。将原本需要额外哈希集合存储的信息编码到输入数组中，实现时间复杂度
核心思想：快慢指针 + Floyd 算法。 利用快慢指针的相对运动检测环，再定位环入口。首先将问题分解为检测环、计算环长、定位入口三个子问题：利用环的周期性，计算环长后让两个指针相距一圈并同步移动，即可找到入口。进一步分析首次相遇点蕴含的距离关系，发现可以直接从头节点和相遇点同步移动找到入口，省去显式计算环长的步骤。
可复用经验： 先通过问题分解和结构性质构造直观、易于证明的解法，再分析中间状态蕴含的信息，利用数学关系消除不必要的计算。
核心思想：固定距离双指针。 当目标位置与链表末尾存在固定距离关系时，可以通过双指针保持固定间距，利用一个指针的终止条件确定另一个指针的位置，避免显式计算链表长度。
核心思想：DFS 连通分量计数。 每次从未访问陆地启动 DFS，标记同一个岛屿中的所有陆地，DFS 的启动次数即岛屿数量。采用入栈即标记避免重复访问，并通过原地标记省去额外的访问数组。
核心思想：多源 BFS + 分层遍历。 从所有初始腐烂橘子同时出发，每一层对应一分钟；新橘子入队时立即标记避免重复访问，全部腐烂后提前终止，得到最短传播时间。
核心思想：DFS 有向环检测 + 搜索结果复用。 将课程依赖关系转化为有向图，通过 DFS 判断是否存在环。朴素路径枚举存在重复搜索，通过三状态标记区分未访问、正在搜索和已完成的节点，实现环检测与结果复用，将时间复杂度优化至
核心思想：从初始状态和目标状态出发，通过循环不变量设计状态迁移，再推导具体实现。
以回文链表的反转操作为例，将算法设计分为四个步骤：
- 状态定义：明确初始状态与目标状态，提取不同情况的共同结构，统一边界条件。
- 不变量设计：根据合法中间状态推导状态变量、初始化和终止条件。
- 状态迁移与实现：先设计抽象状态迁移，再根据数据依赖推导具体操作顺序，必要时引入临时变量。
- 正确性证明：证明初始化、不变量保持、算法终止及目标达成。
2. 表格化递归算法设计方法
核心思想：示例驱动的父子问题关系分析。 用六列表格描述父问题输入、子问题分解方式、子问题输入、子问题结果、分支结果与父问题结果；通过输入关系推导递归调用，通过输出关系推导结果构造与汇总，并利用边界示例明确终止条件。
核心内容： 介绍常见渐近复杂度记号的严格数学定义，以及 Python 常用数据结构操作的时间复杂度。
- 复杂度记号：理解大 O、大 Ω、大 Θ、小 o、小 ω 等渐近记号及其数学含义。
- 数据结构复杂度：掌握 Python
list、dict、set等常用数据结构的典型操作复杂度及适用条件。