第1题数组 vs 链表答案✔️ 正确1、故事两种存储方式 数组 整齐的房子[10][20][30][40] 可以直接跳到第3个a[2] // O(1)2、 链表 火车10 - 20 - 30 - 40 已知某个节点插入p-next newNode; 也是 O(1)3、结论正确 ✔️ 第2题二分查找答案✔️ 正确1、故事找第一个 ≥ xif(a[mid] x) r mid; else l mid 1;2、为什么对 正确的要包含midmid可能就是答案。3、例子a [1,3,5,7] x 4 答案是 5位置24、结论正确 ✔️ 第3题快排稳定性答案❌ 错误1、故事同分同学排队稳定排序 相同值顺序不变2、快排问题[2a, 2b, 1]排序后可能[1, 2b, 2a] 顺序变了3、结论错误 ❌ 第4题递推复杂度答案✔️ 正确1、故事分裂树类似T(n) 2T(n/2) n2、✨分析每层n层数log n 总n log n3、正确 ✔️ 第5题逆序对答案错误❌️1、故事逆序统计定义i j 且 a[i] a[j]2、例子[3,1,2]逆序对(3,1), (3,2)3、✨代码核心cnt (m - i 1); 一次加一段看起来与课堂讲解的很像。但是缺少合并操作函数中只进行了逆序对的统计但未实际合并左右子数组。归并排序的核心是分治合并若不合并会导致后续归并步骤的数组顺序混乱。例如当处理完左子数组[5,6]和右子数组[3,4]后若不合并成有序数组[3,4,5,6]后续处理更大区间时如与另一子数组[1,2]合并将无法正确识别新的逆序对。4、错误❌️ 第6题质数判断答案✔️ 正确1、故事试除法 判断 n 是否是质数只需检查2 ~ sqrt(n)2、例子49 7×73、结论正确 ✔️ 第7题二分复杂度答案✔️ 正确O(log n)1、故事猜数字游戏每次砍掉一半2、✨过程n → n/2 → n/4 → ... log n 次3、正确 ✔️ 第8题贪心算法答案❌ 错误1、故事局部最优 ≠ 全局最优2、例子找零钱硬币1, 3, 4 金额6贪心4 1 1 3枚最优3 3 2枚3、结论错误 ❌ 第9题线性筛答案错误❌️1、故事标记工厂埃氏筛 一个数可能被多次标记线性筛 每个数只被标记一次2、✨关键思想只用最小质因子筛原题说法中每个合数只被其最大质因子筛去的表述完全错误。线性筛的正确策略是每个合数只被其最小质因子筛去一次。3、复杂度O(n)4、错误❌️ 第10题递归转非递归答案❌ 错误1、故事模拟递归确实可以改成循环 ✔️2、❗但 不一定要“显式栈”3、例子阶乘// 不需要栈 for(int i1;in;i)4、结论错误 ❌ 判断题考试技巧1️⃣ 看“绝对词”出现一定、所有、必须 80%是错的2️⃣ 想反例 能举反例 → 一定错3️⃣ 抓本质知识点本质二分不断缩小贪心不一定最优递归可转循环排序稳定性