Basic Algorithm
笔记列表 8
自动关联目录：Basic Algorithm 这一组是不依赖特定数据结构的通用算法思想。它们不是"某一类题的解法"，而是思考问题的方式——后面所有高级算法都是它们的组合。 一张表 思想 一句话 适用信号 枚…
二分在做什么 二分的本质不是"在有序数组里找数"，而是： 在一个单调的判定函数上，用 O(logn)O(\log n)O(logn) 次询问定位分界点。 把问题看成：有一个序列 [false, false, ...…
枚举在做什么 **枚举（Enumeration / Brute Force）**是最诚实的算法：把所有候选答案试一遍，取最优或计数。 复杂度通常是指数级，所以枚举不是"随便写个 for"，而是：如何高效、不重不漏地遍历答…
递归 递归是用函数自己定义自己。一个正确的递归需要两样东西： 1. 基础情形（Base Case）：最小规模直接给出答案，不再递归 2. 递归情形（Recursive Case）：把问题化归为更小的同类问题 缺了 base case → 无…
排序是所有算法的前置步骤 排序本身很少是目的，更多是手段——排完序之后： 二分查找成为可能 双指针成为可能 贪心策略有了明确的顺序 相同元素聚在一起（去重、计数） **"先排序再说"**是解题时最常用的一步。 比较排…
一对对偶操作 前缀和（Prefix Sum）和差分（Difference）是互逆的： 差分→前缀和原数组,原数组→差分差分数组\text{差分} \xrightarrow{\text{前缀和}} \text{原数组}, \qquad \te…
倍增在做什么 **倍增（Binary Lifting）**的核心思想： 预处理出"跳 2k2^k2k 步"的信息，之后任意 nnn 步都拆成二进制，用 O(logn)O(\log n)O(logn) 次跳跃拼出来。 …
贪心在做什么 贪心（Greedy）：每一步都做当前看起来最优的选择，不回头。 贪心: 局部最优 → 局部最优 → ... → 全局最优（？） DP: 枚举所有选择，取全局最优 核心难点：贪心不一定对。它的正确性必须证明，不能靠&…