第9题找最大值的“分身术”1、故事数字王国举行比赛谁是最大数魔法师用了一个技能 把队伍一分为二 左边找最大、右边找最大 最后再比一次2、步骤分析① 分成两半拆问题② 各自解决递归③ 合并答案取较大 这就是分治算法3、⚠️易错点❌ 不是贪心 贪心是“一步一步选最优”这里是“分开解决再合并”4、✅结论答案C小口诀 一分为二再合并 分治 第10题另一种找最大值的方法1、故事这次不用魔法了用最朴素的方法 从头到尾一个一个比较2、步骤分析① 设第一个数为最大值② 依次遍历③ 遇到更大的就更新 这是普通遍历循环3、⚠️关注点❌没有递归4、✅结论答案D这道题是争议题 其实这两个方法时间复杂度一样都是O(n)但是项目分治法遍历法写法复杂简单速度稍慢有递归开销更快空间O(log n)O(1)5、小口诀 一个一个比 遍历 第11题二分查找找最后一个1、故事你在书里找某个单词 不是找“有没有” 是找“最后一次出现的位置”2、步骤分析① 每次取中间② 如果还满足条件 → 往右找③ 否则 → 往左找关键代码mid (low high 1) / 23、这段代码的“配套规则”是条件mid写法更新方式low high(low high 1)/2if(lst[mid]target) {lowmid;}else{highmid-1; 这一整套是“找右边界”的标准写法4、⚠️易错点❌B.当target小于lst中所有元素时该函数会返回 0❌return -1;❌C.循环条件改为while (low high)程序执行效果相同且能提高准确性原本规则是 当只剩一个位置low high就停 但如果改成 low high 那就变成 只剩一个位置也继续找 ⚠️ 这就容易出问题❌D.将代码中(low high 1) / 2修改为(low high) / 2效果相同 可能会卡住死循环5、✅结论答案A6、小口诀 二分查找找最后一个→ mid一定要偏右 第12题二分求平方根1、故事数学精灵要算 √n平方根但可能是小数2、步骤分析 分两步① 找整数部分② 用二分逼近小数停止条件high - low epsilon3、⚠️易错点❌ 题目中说“浮点数不能这样比较” 实际上✔️ 这是标准写法4、✅结论答案D5、小口诀 浮点二分靠误差 第13题找零钱问题1、故事你买东西要找钱 规则 每次优先用最大面额2、步骤分析例如要找 18硬币1051 先用10 再用5 再用1 每一步都选“当前最优”3、⚠️易错点❌ 不是分治❌ 不是枚举 是贪心4、✅结论答案A5、小口诀 能用大的先用大的 第14题快速排序的秘密1、故事排序大师用“快速排序” 选一个数当“分界线”pivot 小的放左边大的放右边2、步骤分析① 随机选 pivot② 分区③ 递归排序左右3、⚠️易错点❌ “快速排序是稳定的” 实际上 快排是不稳定排序4、✅结论答案D5、小口诀 快排很快但不稳定 第15题高精度除法竖式计算1、故事普通数字太小了 现在用“超级大整数”做除法就像手算除法一样2、步骤分析关键动作 “往下带一位”步骤① 当前余数左移② 加入新的一位③ 再去减对应代码r.d[0] a.d[i]; r.len;3、⚠️易错点❌ 不能乱放位置❌ 不能覆盖错误下标4、✅结论答案A5、小口诀 除法核心一位一位往下带 知识点总结 7个关键知识1️⃣ 分治拆开再合并2️⃣ 遍历一个一个比3️⃣ 二分找最后一个要偏右4️⃣ 浮点二分靠误差停止5️⃣ 贪心每步选最优6️⃣ 快排不稳定7️⃣ 高精度模拟竖式