Skip to content

Latest commit

 

History

History
30 lines (17 loc) · 1.73 KB

README.md

File metadata and controls

30 lines (17 loc) · 1.73 KB

AlgorithmNote

本项目记录算法学习笔记,重点总结每道题的核心思路、算法实现与正确性证明,注重提炼可复用的算法设计思想。

算法笔记

核心思想:二分查找划分边界。

划分思路本身比较简单,难点在于统一处理边界条件并保证算法正确性。

  1. 奇偶统一:统一使用 (m+n+1)//2 确定划分位置,仅在返回中位数时区分奇偶。
  2. 数组边界:明确变量表示划分位置,而非数组下标;使用正负无穷大作为哨兵处理空区间。
  3. 循环不变量:利用条件的单调性进行二分查找,通过循环不变量证明不会遗漏目标位置,且最终结果不会被覆盖。

可复用经验: 明确变量含义,统一处理特殊情况,利用循环不变量证明算法正确性。

核心思想: 使用 set 加速成员查询,并仅从连续序列的最小元素开始向后检查,避免重复遍历。

  1. 避免不必要的约束:只需要保证整个算法最终得到正确结果,不必为每个中间步骤添加不必要的约束。
  2. 先求解,再优化:在有性能要求的问题上,先找到简单思路,再分析性能瓶颈并逐步优化。

核心思想: 使用双指针将非零元素按原顺序写入数组前部,再将剩余位置填零。

可复用经验: 明确遍历指针与写入指针的含义,通过循环不变量证明原地修改不会破坏尚未处理的数据。