第8题泛洪填充——如何给一片连在一起的区域换颜色正确答案D1. 题目内容在二维网格上实现泛洪填充时为了防止递归层数过深最适合的非递归实现方式是 。A. 使用哈希表记录每个格子被访问的次数B. 使用快速排序预处理网格C. 使用二分查找定位边界D. 使用队列实现 BFS 或使用显式栈模拟 DFS2. 什么是泛洪填充同学们是不是使用过画图软件里的油漆桶工具假设我们有一张由很多小格子组成的地图。每个格子有自己的颜色蓝色代表海洋。黄色代表沙漠。绿色代表森林。红色代表火山。现在我们想把一片连在一起的绿色森林全部变成红色。应该怎么办这就是泛洪填充Flood Fill。它的基本思想是从一个起始格子出发不断寻找与它连通、并且满足条件的相邻格子把它们全部处理。3. 如何寻找相邻格子假设我们站在二维数组的Ca[x][y]如果只考虑上下左右四个方向那么相邻格子分别是Ca[x - 1][y] // 上 a[x 1][y] // 下 a[x][y - 1] // 左 a[x][y 1] // 右在C中我们通常使用方向数组Cint dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};这样就可以使用循环寻找四个方向。4. 方法一使用DFSDFS叫作深度优先搜索。我们可以把它想象成一位森林探险家发现一条可以走的路就一直向前探索走不通了再返回。泛洪填充的DFS代码Cvoid dfs(int x, int y) { if (x 1 || x n || y 1 || y m) return; if (a[x][y] ! oldColor) return; a[x][y] newColor; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; dfs(nx, ny); } }这里有几个关键步骤首先判断是否越界。判断当前格子是不是需要填充的颜色。如果符合条件就把它改成新颜色。然后继续向四个方向探索。注意一定要先标记当前格子再继续搜索否则可能出现两个格子互相访问、不断重复搜索的问题。5. 为什么题目不推荐递归递归DFS有一个潜在问题如果一片森林特别大可能有几万个甚至更多格子连在一起。那么递归可能不断深入dfs(1,1) dfs(1,2) dfs(1,3) dfs(1,4) ...递归调用太深可能造成栈空间不足。这就是题目所说的为了防止递归层数过深。我们需要寻找非递归实现方式。6. 方法二使用队列实现BFSBFS叫作广度优先搜索。我们可以把它想象成水滴落入池塘第一圈向外扩散。第二圈继续扩散。第三圈继续扩散。它使用队列来保存等待访问的格子。看代码C#include iostream #include queue using namespace std; const int N 105; int a[N][N]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int n, m; void bfs(int sx, int sy, int oldColor, int newColor) { if (oldColor newColor) return; queuepairint, int q; a[sx][sy] newColor; q.push(make_pair(sx, sy)); while (!q.empty()) { pairint, int p q.front(); q.pop(); int x p.first; int y p.second; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 1 || nx n || ny 1 || ny m) continue; if (a[nx][ny] ! oldColor) continue; a[nx][ny] newColor; q.push(make_pair(nx, ny)); } } }这里有三个特别重要的操作Cq.push(make_pair(nx, ny));把新发现的格子加入队列。Cq.front();查看队头的格子。Cq.pop();处理完后把队头格子移出队列。7. 方法三使用显式栈模拟DFS除了队列我们还可以自己定义一个栈。原来递归DFS使用的是系统调用栈现在可以用自己的栈保存待处理格子。因此BFS使用队列。非递归DFS使用显式栈。两者都可以解决泛洪填充问题。最终答案D记忆口诀泛洪填充找连通区域DFS可以递归BFS可以用队列非递归DFS可以用显式栈。第9题哈希表——为什么查找速度快也可能发生冲突正确答案C1. 题目内容关于哈希表下列说法正确的是 。A. 只要哈希函数选择合适就可以完全避免冲突。B. 在链地址法中查找一个元素的时间复杂度一定为 O(1)。C. 开放定址法发生冲突后会在表内寻找下一个可用位置。D. 哈希表的查找速度与表中元素个数无关。这道题考查哈希表Hash Table。2. 先讲一个故事学校的储物柜假设学校有100个储物柜。现在来了很多同学每个同学都需要一个柜子。如果按照名字一个一个寻找柜子可能很麻烦。老师想出了一个办法把学生的学号经过某种计算直接得到柜子的编号。例如C柜子编号 学号 % 100;假设学号是12345那么12345 % 100 45这个同学就可以使用45号柜子。这种根据数据计算存储位置的方法就是哈希思想。3. 什么是哈希函数哈希函数就是一个计算位置的函数。例如Cint hash(int x) { return x % 10; }如果有下面这些数字12、23、35、42计算结果原始数字哈希值122233355422大家发现问题了吗12和42都得到位置2。那么两个数字都想放到2号位置怎么办这就出现了哈希冲突。4. 什么是哈希冲突当两个不同的数据经过哈希函数计算后得到相同的存储位置就称为哈希冲突。例如Chash(12) 2; hash(42) 2;虽然12和42不相等但是它们的哈希值相同。所以A选项错误。再好的哈希函数也不能保证对任意可能的数据都完全没有冲突。5. 哈希冲突的两种常见解决办法方法一链地址法我们可以让同一个位置挂上一条链表。例如假设12和42都映射到位置2位置2 → 12 → 42这样就不用担心两个数据抢同一个位置。但是如果大量数据都集中在同一个位置位置2 → 12 → 22 → 32 → 42 → 52那么查找时就可能需要沿着链表一个一个寻找。所以链地址法的平均查找效率通常可以达到 O(1)但最坏情况下可能达到 O(n)。因此B选项错误。方法二开放定址法开放定址法不另外建立链表。如果原来的位置被占用了就在哈希表内部继续寻找其他空位置。例如12 → 位置2 42 → 位置2发生冲突 42 → 尝试位置3如果位置3空着就把42存放到位置3。这正是C选项描述的内容。所以C正确。6. 为什么D也错误D说哈希表的查找速度与表中元素个数无关。这显然不准确。哈希表通常很快但元素数量增加后可能发生更多冲突。哈希表的装载因子可能增大。查找时可能需要检查更多位置或链表节点。因此查找速度会受到元素数量、哈希函数、冲突处理方式等因素的影响。最终答案C七级考试记忆哈希函数计算存储位置。哈希冲突不同数据映射到同一个位置。链地址法一个位置挂一条链表。开放定址法冲突后在表内寻找其他位置。第10题引用——为什么函数可以直接修改外面的变量正确答案B41. 题目内容看下面的C程序C#include iostream using namespace std; void inc(int x) { x; } int main() { int a 3; inc(a); cout a; return 0; }问程序输出什么选项A. 3B. 4C. 5D. 编译错误这道题非常重要因为它考查C中的引用。2. 什么是引用看函数参数Cint x这里的表示引用。引用可以理解为给原来的变量再起一个别名。例如Cint a 3; int x a;现在a是这个盒子的原名字。x是这个盒子的另一个名字。它们不是两个盒子而是同一个盒子。引用就像给同一个盒子起两个名字名字a名字xa和x指向同一个变量不是两个独立的盒子。因此Cx;其实就是Ca;3. 分步模拟第一步Cint a 3;此时a 3第二步Cinc(a);把变量a传入函数。由于函数参数是Cint x所以x就是a的别名。此时a 3 x 3第三步执行Cx;x增加1。由于x和a是同一个变量所以a 4第四步函数结束回到main函数。执行Ccout a;输出4所以正确答案是B。4. 对比总结参数形式传递方式能否修改原变量int x值传递不能int x引用传递能const int x常量引用不能通过该引用修改最终答案B4记忆口诀普通参数传副本引用参数起别名。修改引用里的值原变量也会跟着变。第11题最长公共子序列LCS——两个字符串有多少共同的字符正确答案A1. 题目内容用动态规划求两个序列 s1 和 s2 的最长公共子序列长度。若dp[i][j]表示 s1 前 i 个元素与 s2 前 j 个元素的LCS长度。当s1[i-1] s2[j-1]时正确的状态转移是A/B/C/D选项内容见试卷。2. 先理解什么是公共子序列我们讲一个故事。小明喜欢一串字母A B C D E小红喜欢一串字母B A D E现在我们想找出他们共同拥有的、顺序不变的最长字母序列。注意子序列可以删除一些字符但不能改变剩余字符的先后顺序。例如A B C D E可以得到A C E因为只需要删除B和D。但是不能得到E A C因为改变了原来的顺序。3. 什么是最长公共子序列例如s1 A B C D E s2 B A D E公共子序列有A D E B D E它们的长度都是3。因此最长公共子序列长度为3。这就是LCSLongest Common Subsequence。4. 为什么使用二维DP我们定义dp[i][j]表示第一个序列取前i个字符。第二个序列取前j个字符。这两个部分的最长公共子序列长度。为了方便处理我们通常让数组下标从1开始代表字符数量。也就是说Cs1[i - 1] s2[j - 1]才是两个序列当前正在比较的字符。5. 最重要的状态转移现在来看题目中的条件s1[i-1] s2[j-1]也就是两个序列当前最后一个字符相同。例如s1 A B C s2 B A C当我们比较到最后一个字符时s1最后一个字符 C s2最后一个字符 C既然两个字符相同那么我们就可以把它们一起加入公共子序列。于是dp[i][j] dp[i-1][j-1] 1为什么因为先去掉两个序列最后一个字符。求剩余部分的最长公共子序列。再把当前相同的字符加进去。所以长度增加1。这就是A选项。6. 如果两个字符不相同怎么办虽然题目只问相等的情况但是我们必须掌握完整的LCS状态转移。如果s1[i-1] ≠ s2[j−1]那么当前两个字符不能同时作为公共子序列的最后一个字符。我们可以去掉第一个序列的最后一个字符。或者去掉第二个序列的最后一个字符。两种情况取较大值dp[i][j] max(dp[i−1][j],dp[i][j−1])所以完整公式是7. 完整C程序C#include iostream #include algorithm #include string using namespace std; const int N 1005; int dp[N][N]; int main() { string s1, s2; cin s1 s2; int n s1.size(); int m s2.size(); for (int i 1; i n; i) { for (int j 1; j m; j) { if (s1[i - 1] s2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max( dp[i - 1][j], dp[i][j - 1] ); } } } cout dp[n][m] endl; return 0; }最终答案A记忆口诀两个字符相同左上角加1两个字符不同上方和左方取最大。第12题0/1背包——为什么一维数组必须从大到小枚举正确答案D51. 题目内容题目给出下面的程序C#include iostream #include algorithm using namespace std; int main() { int w 3, v 5, W 8; int dp[9] {0}; for (int c W; c w; c--) dp[c] max(dp[c], dp[c - w] v); cout dp[8] endl; return 0; }问Cdp[8]最终输出多少选项A. 0B. 1C. 3D. 52. 先讲故事魔法背包假设我们有一个容量为8的魔法背包。现在只有一种宝物宝物重量价值魔法宝石35我们的问题是背包最多装8单位重量的物品最多能够获得多少价值注意每种物品只能选择一次。这就是0/1背包问题。为什么叫0/1背包因为对于每件物品只有两种选择0不选。1选择。不能选择两次也不能选择三次。3. 理解dp数组Cint dp[9] {0};这里的Cdp[c]表示背包容量为c时目前能够得到的最大价值。初始状态容量 0 1 2 3 4 5 6 7 8 价值 0 0 0 0 0 0 0 0 0因为一开始还没有放入任何宝物所以所有价值都是0。4. 重点分析循环题目给出Cint w 3; int v 5; int W 8;表示物品重量为3。物品价值为5。背包容量为8。循环Cfor (int c W; c w; c--)等价于Cfor (int c 8; c 3; c--)为什么从8开始因为背包容量最大是8。为什么到3结束因为物品重量是3容量小于3的背包装不下它。5. 状态转移公式Cdp[c] max(dp[c], dp[c - w] v);翻译成小朋友能听懂的话对于容量为c的背包有两种选择选择一不放这件宝物。那么价值保持原来的dp[c]选择二放入这件宝物。那么需要先留出3个单位的空间p[c−3]5我们选择价值更大的方案dp[c] max(dp[c],dp[c−3]5)6. 一步一步计算初始dp[0] 0 dp[1] 0 dp[2] 0 dp[3] 0 dp[4] 0 dp[5] 0 dp[6] 0 dp[7] 0 dp[8] 0现在开始循环。第一次c8Cdp[8] max(dp[8], dp[5] 5);dp[8] max(0,05) 5第二次c7Cdp[7] max(dp[7], dp[4] 5);dp[7] 5第三次c6Cdp[6] max(dp[6], dp[3] 5);dp[6] 5第四次c5Cdp[5] max(dp[5], dp[2] 5);dp[5] 5第五次c4dp[4] 5第六次c3dp[3] 5最终数组容量c012345678dpcc000555555所以dp[8] 5答案是D。7. 为什么0/1背包必须从大到小枚举假设我们把循环改成从小到大Cfor (int c w; c W; c)那么Cdp[3] dp[0] 5 5;接着Cdp[6] dp[3] 5 10;但是注意dp[3]刚刚已经使用了这件宝物。现在计算dp[6]时又使用了它。相当于同一件宝物被使用了两次这就变成了完全背包的思想而不是0/1背包。所以0/1背包必须0/1背包从大到小完全背包从小到大8. 两种背包的对比类型物品能否重复选择容量循环0/1背包每件最多一次从大到小完全背包每件可以多次从小到大最终答案D5记忆口诀0/1背包倒着走防止物品被重复使用完全背包正着走允许物品重复使用。第13题稳定排序——为什么有些排序会改变相同元素的顺序正确答案D1. 题目内容若要求排序后相等元素的相对顺序保持不变下列排序算法中最不适宜使用的是 。A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序这道题考查一个重要的概念稳定排序Stable Sort。2. 什么叫稳定排序我们讲一个故事。学校要给学生的考试成绩排序。有四个学生学生成绩原来的顺序小明90第1个小红80第2个小刚90第3个小华70第4个现在按照成绩从高到低排序。排序结果学生成绩小明90小刚90小红80小华70注意小明和小刚的成绩相同。原来小明排在小刚前面排序之后仍然保持这个顺序。这就叫稳定排序。3. 四种排序算法的稳定性排序算法是否稳定冒泡排序稳定插入排序稳定归并排序稳定快速排序不稳定为什么快速排序不稳定因为快速排序会根据基准值进行分区操作。在交换元素的过程中即使两个元素的关键字相同也可能改变它们原位置第14题分析程序的时间复杂度正确答案B. O(n log n)题目代码Clong long s 0; for (int i 1; i n; i) for (int j 1; j n; j i) s i j;题目问这段代码的时间复杂度是多少选项A. O(n)B. O(nlog⁡n)C. O(n^2)D. O(n sqrt(n))第一步先看外层循环Cfor (int i 1; i n; i)外层循环从1开始一直执行到n。所以外层循环一共执行n 次如果内层循环每次都执行n次那么总次数就是n×n n^2但是这道题有一个陷阱内层循环并不是每次都执行n次我们继续往下看。第二步观察内层循环Cfor (int j 1; j n; j i)注意最后一句Cj i它表示每次循环j都增加当前的i。也就是说内层循环每次增加多少取决于外层循环的变量i。我们用一个具体例子来观察。假设n10当i1时j 1, 2, 3, 4, 5, 6, 7, 8, 9, 10一共执行10次。当i2时j 1, 3, 5, 7, 9一共执行5次。当i3时j 1, 4, 7, 10一共执行4次。当i4时j 1, 5, 9一共执行3次。当i5时j 1, 6一共执行2次。当i6时j 1, 7一共执行2次。当i10时j 1只执行1次。发现规律了吗外层变量 i 越大内层循环执行的次数越少第三步制作循环次数统计表我们把刚才的情况整理起来外层变量i内层j的取值执行次数11,2,3,...,101021,3,5,7,9531,4,7,10441,5,9351,6261,7271,8281,9291,1021011所以总执行次数是1054322222133如果真的是普通的两层循环执行次数应该是10×10100但是现在只执行了33次。这说明它并不是简单的 O(n^2)。第四步推导真正的时间复杂度当外层变量为 i 时Cfor (int j 1; j n; j i)每次增加 iii所以内层循环大约执行次。外层循环从1到n因此总执行次数大约是提取公因数 n括号里的部分叫作调和级数它的增长量级是O(log⁡n)因此所以正确答案是B. O(n log n)第五步为什么不是O(n²)我们对比一下两种程序。程序一普通双重循环Cfor (int i 1; i n; i) { for (int j 1; j n; j) { // 执行操作 } }内层每次都执行n次n×nn^2所以是O(n^2)程序二本题的循环Cfor (int i 1; i n; i) { for (int j 1; j n; j i) { // 执行操作 } }内层循环步长随着i增大而增大执行次数越来越少所以是O(nlog⁡n)给学生的记忆方法看到两层for循环不要马上写 O(n2)。先检查三个问题内层循环从哪里开始内层循环什么时候结束内层循环每次增加多少特别注意Cj;和Cj i;它们的执行次数可能完全不同第15题指针与数组的关系正确答案C. 9题目已知Cint a[6] {1, 3, 5, 7, 9, 11}; int *p a 1;则表达式C*(p 3)的值是多少选项A. 5B. 7C. 9D. 11这道题需要理解三个知识点数组下标从哪里开始指针加1是什么意思*运算符是什么意思第一步给数组里的元素安排座位数组Cint a[6] {1, 3, 5, 7, 9, 11};可以想象成6个连续排列的小房间。数组a的六个位置1下标03下标15下标27下标39下标411下标5注意数组下标从0开始而不是从1开始。对应关系数组表达式数组下标存储的值a[0]01a[1]13a[2]25a[3]37a[4]49a[5]511一定要记住数组的第一个元素下标是0。第二步理解int *p a 1原代码Cint *p a 1;这里的a在这个表达式中会转换成指向第一个元素的指针。因此Ca相当于Ca[0]那么Ca 1就是指向下一个元素Ca[1]因此Cint *p a 1;相当于Cint *p a[1];也就是说现在指针p指向哪里p指向a1也就是数值3所在的位置。第三步理解p 3题目要求计算C*(p 3)我们先不要着急计算最外面的*。先看Cp 3因为p指向的是Ca[1]那么向后移动3个元素原来位置a[1] 向后移动3个位置 a[1] → a[2] → a[3] → a[4]因此Cp 3相当于Ca[4]第四步理解最外面的*现在表达式变成C*(a[4])这里的*表示根据地址取出这个地址里存放的值。所以C*(a[4]) a[4]而Ca[4] 9最终答案9选择C第五步把整个过程写成一条公式原表达式C*(p 3)已知Cp a 1代入∗(a13)合并∗(a4)取出对应位置的值a[4] 9所以三、指针加减法的通用规律假设Cint a[6] {1, 3, 5, 7, 9, 11}; int *p a;那么表达式实际对应结果*pa[0]1*(p1)a[1]3*(p2)a[2]5*(p3)a[3]7*(p4)a[4]9*(p5)a[5]11记住这个公式如果Cp a t;那么注意指针加1表示移动到下一个同类型元素而不是简单地让内存地址增加1个字节。例如int*加1移动一个int元素。double*加1移动一个double元素。char*加1移动一个char元素。考点汇总题号知识点必须掌握的内容8泛洪填充Flood Fill、DFS、BFS、队列、栈9哈希表哈希函数、哈希冲突、链地址法、开放定址法10C引用值传递、引用传递、变量别名11LCS最长公共子序列、二维DP120/1背包一维优化、倒序枚举13稳定排序冒泡、插入、归并、快速排序14时间复杂度嵌套循环、调和级数、O(nlog⁡n)O(n\log n)O(nlogn)15指针指针运算、数组下标、解引用特别值得大家掌握的五组知识联系第一组DFS、BFS与泛洪填充它们解决的都是搜索问题。DFS一条路走到底再返回。BFS一层一层向外扩散。泛洪填充寻找满足条件的连通区域。第二组哈希表与STL容器后续学习STL时可以进一步认识Cmap unordered_map set unordered_set特别是unordered_map和unordered_set都与哈希思想密切相关。第三组引用与指针这是C语言学习中非常重要的一组知识。Cint x a;引用是变量的别名。Cint *p a;指针保存变量的地址。两者不能混为一谈。第四组LCS与背包DP这两道题都是动态规划但是思考方式不同LCS考虑两个序列的前缀。0/1背包考虑物品和背包容量。尤其要记住0/1背包的一维优化必须倒序枚举。第五组时间复杂度与算法效率学会分析O(1)O(log⁡n)O(n)O(nlog⁡n)O(n^2)不能简单地看到两个for循环就认为是 O(n^2)。课后巩固下面设计一组小测验帮助大家查自己是否真正理解了这些知识。1. 泛洪填充中为了避免递归层数过深可以使用什么A. 快速排序B. 队列实现BFS或显式栈模拟DFSC. 二分查找D. 哈希排序2. 哈希表发生冲突时开放定址法通常怎么处理A. 删除原来的数据B. 扩大所有数组C. 在表内寻找其他可用位置D. 停止程序3. void add(int x)中的表示什么A. 按位与B. 取地址C. 引用D. 逻辑与4. LCS中如果两个当前字符相同应该怎样转移A. 左上角加1B. 上方加1C. 左方加1D. 取05. 0/1背包一维优化时容量应该怎样枚举A. 从小到大B. 从大到小C. 随机D. 只计算最大容量6. 以下哪种排序通常不稳定A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序7. 两个嵌套循环中内层 j 每次增加 i外层 i 从 1到n总复杂度是什么A. O(n)B. O(n log n)C. O(n²)D. O(log n)8. int a[]{1,3,5,7,9}; int *pa1; 那么*(p2)是多少A. 3B. 5C. 7D. 9