第8题递归函数f(4)到底是多少题目int f(int n) { if (n 1) return 1; return n f(n - 1); }问f(4)是多少答案D10。① 先别害怕“递归”很多同学看到f(n)又出现f(n - 1)会觉得“函数怎么又调用自己了不会无限循环吗”其实不会。因为这里有一个非常重要的“刹车”if (n 1) return 1;这就是递归的终点也叫递归出口。② 我们把f(4)拆开程序return n f(n - 1);所以f(4) 4 f(3)继续f(3) 3 f(2)继续f(2) 2 f(1)到了f(1) 1因为触发if (n 1) return 1;③ 从最里面往外算现在开始“返回”f(1) 1 f(2) 2 1 3 f(3) 3 3 6 f(4) 4 6 10所以答案 10 把它想成爬楼梯f(4)就像问“从第4层往下走每一层把自己的数字加起来最后走到1层。”4 ↓ 3 ↓ 2 ↓ 1最后4 3 2 1 10 记忆口诀递归题先找到出口再一层一层拆最后倒着算回来。第9题二分查找“第一个大于 x”的位置这道题非常重要。题目int upperBound(const vectorint a, int x) { int l 0, r (int)a.size(); while (l r) { int mid l (r - l) / 2; if (__________________) { l mid 1; } else { r mid; } } return l; }题目要求在升序数组中找第一个严格大于x的元素位置。答案Ca[mid] x① 什么叫“第一个严格大于”比如数组 1 3 3 5 7 9如果x 3我们寻找第一个大于3的数。答案是5它的位置0 1 2 3 4 5 ↑所以答案位置是3② 为什么判断a[mid] x想象我们站在mid这个位置。情况一如果a[mid] x例如a[mid] 3 x 3我们要找的是严格大于 3所以3肯定不行。怎么办往右找于是l mid 1;情况二如果a[mid] x例如a[mid] 7 x 37 已经符合要求。但是会不会左边还有一个更小的位置也同样大于3当然可能所以不能直接结束。应该往左缩小范围于是r mid;③ 所以整个逻辑就是a[mid] x ↓ 不够大 ↓ 往右而a[mid] x ↓ 符合要求 ↓ 左边继续找所以if (a[mid] x) l mid 1; else r mid;答案C⭐ 一个非常重要的二分口诀如果题目问第一个大于 x就记a[mid] x因为小于等于 x 的都不要继续向右。第10题二分答案——猜一个“最小载重”这一题非常有意思。题目背景有很多箱货物要按原来的顺序分成days天运输每天运输连续的一段货物。要求找到能够完成任务的最小载重量。程序已经有check(cap)它可以告诉我们“如果卡车载重是cap能不能在规定天数内完成”题目问二分部分怎么填写。答案B。① 这道题真正的秘密我们不是直接找答案。而是在猜答案例如最小可能载重 10 最大可能载重 100我们猜mid 55然后问check(55)② 如果 55 可以完成说明55够用但是问题是55 是最小的吗不知道所以应该继续尝试更小也就是r mid;③ 如果 55 不够说明55太小那就必须提高载重量往右寻找所以l mid 1;④ 所以答案是if (check(mid)) { r mid; } else { l mid 1; }也就是check(mid) 成功 ↓ mid 可以 ↓ 答案可能更小 ↓ 往左 check(mid) 失败 ↓ mid 太小 ↓ 往右 这就是“二分答案”普通二分在数组里找数字。二分答案在答案范围里猜答案。这是非常重要的算法思想。记忆口诀能做成 → 尝试更小。做不成 → 必须更大。第11题归并排序为什么选择题目是归并排序的合并过程while (i mid j right) { if (__________________) { temp.push_back(a[i]); } else { temp.push_back(a[j]); } }题目要求如果希望排序保持稳定应该怎样填写答案Da[i] a[j]原题代码及选项见试卷。① 什么叫“稳定排序”这是这道题最重要的概念。假设有两个学生小明分数90 小红分数90他们原来的顺序小明 → 小红如果排序以后小明 → 小红顺序没有变化。这叫稳定。② 归并排序正在干什么假设左右两边已经排好左边 90(小明) 右边 90(小红)现在两个 90 一模一样。程序if (a[i] a[j])因为90 90成立。于是选择左边的小明再选择右边的小红最终小明 → 小红原来的顺序被保留。③ 如果写成呢如果if (a[i] a[j])当90 90是false程序就会选择右边小红可能变成小红 → 小明原来的顺序被改变。所以为了保证稳定性a[i] a[j]⭐ 小学生记忆法归并排序遇到左边 右边怎么办公平一点先让左边的人过。所以a[i] a[j]答案D第12题快速排序的 partition题目int partition(int a[], int left, int right) { int pivot a[right]; int i left - 1; for (int j left; j right; j) { if (__________________) { i; swap(a[i], a[j]); } } swap(a[i 1], a[right]); return i 1; }题目说以a[right]为枢轴并把不大于枢轴的元素移动到左侧。答案Aa[j] pivot原题代码见试卷。① pivot 是什么pivot可以理解成守门员比如5 2 8 3 7假设pivot 7我们希望≤7的站到左边。而7的留在右边。最终大概形成≤7 | 7 | 7② 代码正在扫描谁for (int j left; j right; j)也就是j ↓ 一个一个检查如果发现a[j] pivot说明“这个小朋友应该站到左边。”于是i; swap(a[i], a[j]);③ 为什么不是a[j] pivot题目明确说不大于 pivot 的放左边。“不大于”数学语言就是≤所以a[j] pivot答案A第13题活动安排的经典贪心题目一个教室要安排尽可能多场活动每场活动有开始时间start和结束时间end。采用贪心算法时正确策略是A. 每次选择开始时间最早B. 每次选择持续时间最短C. 每次选择参与人数最少D.按结束时间从早到晚排序依次选择与已选活动不冲突的活动答案D。① 为什么不是“开始得最早”比如活动A1 ───────── 10 活动B2 ─ 3 活动C4 ─ 5 活动D6 ─ 7如果选择开始最早的 A整个教室1 ───────── 10后面的 B、C、D 全没了。只能安排1场② 如果选择结束最早的呢先看B2 ─ 3结束时间最早。选 B。接下来C4 ─ 5不冲突继续选。然后D6 ─ 7继续选。最终B → C → D安排了3场③ 为什么“结束得早”这么聪明因为越早结束就越早把教室空出来。后面留下的时间越多。所以结束早 ↓ 给后面的活动留下更多空间 ↓ 最终活动数量可能最多这就是经典的区间调度问题的贪心策略。⭐ 贪心口诀遇到“一间教室最多安排多少个互不冲突的活动”立刻想到按结束时间从小到大排序然后能选就选答案D第14题最大连续子段和题目给数组{-2, 3, -1, 5, -6, 2}函数int maxSubArray(const vectorint a) { int best a[0]; int current a[0]; for (int i 1; i (int)a.size(); i) { current max(a[i], current a[i]); best max(best, current); } return best; }问返回多少答案C7① 什么叫“连续子段”比如-2 3 -1 5 -6 2可以选择3也可以3 -1还可以3 -1 5但是不能3 5因为中间的-1被跳过了。所以必须连续② 我们从左往右走核心代码current max(a[i], current a[i]);这句话是什么意思到了一个新数字我要不要把它接在以前的队伍后面有两个选择选择1重新开始a[i]选择2接着以前的队伍current a[i]哪个大就选哪个。③ 一步一步算数组-2 3 -1 5 -6 2初始current -2 best -2来到 3比较3和-2 3 1选择3所以current 3 best 3来到 -1比较-1和3 (-1) 2选择2于是current 2 best 3来到 5比较5和2 5 7选择7于是current 7 best 7按照题目给出的代码{-2,3,-1,5,-6,2}的最大连续子段和是7。因为3 (-1) 5 7继续验证后面也一样-6 7 (-6) 1所以current 1 best 7最后2 1 2 3最终best 7✅ 第14题答案C7第15题高精度加法中的进位最后一道选择题非常经典。题目给两个高精度整数a b而且采用低位在前也就是a[0] 个位 a[1] 十位 a[2] 百位代码vectorint add(const vectorint a, const vectorint b) { vectorint c; int carry 0; int n max(a.size(), b.size()); for (int i 0; i n; i) { int sum carry; if (i a.size()) sum a[i]; if (i b.size()) sum b[i]; c.push_back(sum % 10); ____________________ } if (carry) c.push_back(carry); return c; }选项A. carry sum % 10; B. carry sum; C. carry sum / 10; D. carry c[i] / 10;答案C① 为什么需要高精度C 的int long long都有范围限制。如果数字特别特别大123456789012345678901234567890普通整数装不下。怎么办我们自己用数组保存。② 为什么“低位在前”例如1234存成a[0] 4 a[1] 3 a[2] 2 a[3] 1这样做有一个巨大好处加法正好从个位开始。这就和我们小学数学竖式加法完全一样。③ 看一个简单例子例如58 67个位8 7 15个位写5同时产生进位 1所以sum 15那么sum % 10得到5这就是当前这一位。而sum / 10得到1这就是下一位要加的进位。所以carry sum / 10;④%10和/10一定要分清这是本题最核心的知识。假设sum 18那么sum % 10得到8它负责留下当前这一位。而sum / 10得到1它负责把进位送给下一位。所以18 ↙ ↘ %10 /10 ↓ ↓ 8 1 当前位 进位 815题最终总结题号知识点答案最重要的一句话8递归D找到递归出口再倒着算9二分查找C找第一个x判断a[mid] x10二分答案B能完成→缩小答案不能完成→增大答案11稳定归并排序D相等时先选左边12快速排序A pivot放左边13贪心D活动安排优先选结束早的14最大子段和Ccurrentmax(当前数, 前面当前数)15高精度加法C%10留当前位/10得进位 “考场藏宝图”如果考试中看到这些关键词可以快速联想到算法“递归” ↓ 先找出口 “第一个大于” ↓ upper_bound ↓ a[mid] x “最小载重量” ↓ 二分答案 “保持稳定” ↓ 相等时左边优先 ↓ “pivot / partition” ↓ 快速排序 “最多安排活动” ↓ 结束时间最早 ↓ 贪心 “最大连续子段和” ↓ current / best “高精度加法” ↓ 个位开始 ↓ %10 当前位 /10 进位尤其要把最后这一组口诀记住二分能行就往左不行就往右。贪心活动安排看结束时间。最大子段和要么重新开始要么接着前面。高精度%10留自己/10往前进。