复习C/C刷到第31到40题这个区间恰好是整个五十题练习册里最容易产生“错觉”的一段字符串、查找、排序看着都眼熟真下手写代码边界条件、指针操作、内存释放却处处是坑。这一批十道题覆盖字符串反转、回文判断、二分查找、链表反转、快速排序、斐波那契数列、字符统计、动态二维数组、括号匹配和最大公约数几乎把C/C复习最值得练的考点都过了一遍。这篇我按题目分组来写每道题都给出题目描述、参考实现、复杂度分析以及我实际跑码时踩过的坑。适合正在准备期末、考研复试或者求职笔试的读者也适合工作中想把C/C基础快速捡起来的人。如果你已经刷完前面1到30题这一批正好帮你把“感觉会了”变成“真正能写对”。1. 字符串双题热身31题与32题的指针功底1.1 31题不调用库函数实现字符串反转题目描述实现一个函数void reverseString(char s[])把以\0结尾的字符串原地反转。要求空间复杂度 O(1)不允许调用strrev这类现成库函数。输入示例s hello处理后s olleh。这道题考的是双指针和字符数组的底层理解。思路很直白left从开头走right从最后一个字符走两边交换直到两个指针相遇。但“找最后一个字符”这一步新手最容易翻车。void reverseString(char s[]) { if (s nullptr) return; // 空指针直接返回别去解引用 int left 0; int right 0; while (s[right] ! \0) right; // 先找到字符串末尾 right--; // 关键退到最后一个有效字符 while (left right) { char tmp s[left]; s[left] s[right]; s[right] tmp; left; right--; } }我当初第一次写这道题就是忘了right--结果把\0当成有效字符换到了开头字符串直接被截断。这个细节看着小考场上能卡掉不少人。如果题目没限制库函数用strlen(s) - 1来定位右指针当然更省事但这道题既然是练手我建议连strlen也自己写一遍顺便加深对“C风格字符串以\0结尾”这个本质的记忆。C 里如果传入的是std::string同样思路可以写成void reverseString(std::string s) { int left 0, right (int)s.size() - 1; while (left right) { std::swap(s[left], s[right]); left; right--; } }复杂度很干净时间 O(n)空间 O(1)。常见变形是把字符串按单词反转那个要先把整个串反转再逐单词反转属于这道题的加强版复习时值得顺带想想。1.2 32题回文判断边界条件别偷懒题目描述给定一个字符串判断它是不是回文。回文就是正着读和反着读一样比如abcba、abccba。输入示例abcba返回truehello返回false空串返回true。bool isPalindrome(const char* s) { if (s nullptr) return false; int left 0; int right 0; while (s[right] ! \0) right; right--; while (left right) { if (s[left] ! s[right]) return false; left; right--; } return true; }空串和单字符天然是回文循环里left right的判断天然覆盖了这两种情况但前提是你别在循环前面手写一个if (strlen(s) 0) return false之类的错误判断。边界题就怕“想当然”。这道题的常见升级版是忽略大小写并且忽略所有非字母数字字符再判断回文。很多面试官喜欢在这里追加条件完整写法是这样的bool isPalindromeExtended(const std::string s) { int left 0, right (int)s.size() - 1; while (left right) { while (left right !isalnum(s[left])) left; while (left right !isalnum(s[right])) right--; if (tolower(s[left]) ! tolower(s[right])) return false; left; right--; } return true; }加粗提醒isalnum和tolower都在cctype里判断字符时要先做 unsigned char 转换再传进去否则对于扩展 ASCII 字符可能存在未定义行为这点和后面第 37 题的坑同源。这道题还有个兄弟题型判断一个int是否为回文数。做法是把数字反转一半就和原数比较避免整个反转溢出。思路相通我建议一题两练顺手把数字拆解的%、/操作也复习了。2. 查找与数学题的隐藏考点33题二分查找和40题公约数2.1 33题二分查找的三个边界细节题目描述给定一个按升序排列的整型数组和一个目标值target返回target在数组中的下标找不到返回 -1。输入示例arr [1, 3, 5, 7, 9], target 5返回 2。int binarySearch(int arr[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; // 防止 left right 溢出 if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }二分查找看起来是几行代码实际上有三处细节直接决定生死第一循环条件必须用left right。它表达的是“target 当前可能在 [left, right] 这个闭区间内”。有人改成left right就会漏掉left right时的最后一个元素。第二mid的写法要用left (right - left) / 2而不是(left right) / 2。两个很大的 int 相加可能溢出成负数经典线上事故。第三区间收缩用mid 1和mid - 1不能偷懒写成left mid或right mid否则当区间只剩两个元素时会无限循环。解释一下为什么不变量这么重要你只要保证“target 一定在 [left, right] 中且区间长度每次严格递减”整个算法就不会写错。一旦写出left mid这种代码区间不变小死循环就来敲门了。面试常在这道题后面追一题如果数组里有重复元素要求返回第一个等于 target 的下标。这时可以改成right收敛条件为arr[mid] target ? right mid : left mid 1循环结束后检查arr[left]。把基础二分和这个变体一起练复习效率最高。复杂度时间 O(log n)空间 O(1)。2.2 40题辗转相除法与最小公倍数的溢出陷阱题目描述输入两个正整数 a 和 b输出它们的最大公约数GCD和最小公倍数LCM。输入示例a 12, b 18GCD 6LCM 36。教科书算法是辗转相除法核心公式gcd(a, b) gcd(b, a % b)写成循环很干净int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; } int lcm(int a, int b) { return a / gcd(a, b) * b; // 注意先除后乘 }递归版本同样常见面试时写递归更省事int gcdRecursive(int a, int b) { return b 0 ? a : gcdRecursive(b, a % b); }真正值得记的坑在lcm里为什么用a / gcd(a, b) * b而不是a * b / gcd(a, b)因为两个 int 直接相乘很容易溢出 32 位范围。举个例子a 2000000000、b 1999999999先乘a * b直接溢出成负数先除再乘则大概率在安全范围内。这个“先除后乘”的小习惯笔试时能救你一命。顺带一提C17 标准库提供了std::gcd和std::lcm在numeric里工程上直接用没问题。但复习阶段我建议手写因为面试官想看的是你理解原理而不是背 API。复杂度 O(log min(a, b))空间 O(1)。3. 链表与栈34题反转链表的指针陷阱和39题括号匹配3.1 34题链表反转的迭代与递归双解法题目描述给定单链表头节点head反转整个链表返回新头节点。要求不能改链表节点的值只能改指针。struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; // 迭代法三个指针逐步改向 ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* next curr-next; // 必须先保存下一个节点 curr-next prev; // 当前节点指向前一个 prev curr; // prev 前进 curr next; // curr 前进 } return prev; // 最后 prev 就是新头节点 }迭代法的灵魂是那三行赋值顺序保存next→ 改next→ 移动prev→ 移动curr。我见过不下三个人把next的保存放在curr-next prev之后链表当场断成一截程序直接崩溃。这个顺序不是死记而是逻辑必然——你先断了curr-next后面就没法找到原来的下一个节点了。递归版本的思路略有不同它假设“后半个链表已经被反转好”把当前节点接到尾巴上ListNode* reverseListRecursive(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseListRecursive(head-next); head-next-next head; // 让下一个节点指向自己 head-next nullptr; // 断开原来的正向指针 return newHead; }这个递归我第一次看的时候想了半天为什么反过来之后head-next-next是安全的因为head-next在递归深入时还是原链表的下一个节点反转后它变成了新链表的尾部而head恰好要接在这个尾部之后。想通了这层递归就彻底看懂了。复杂度上迭代法时间 O(n)、空间 O(1)递归法时间 O(n)、空间 O(n)递归栈。面试手写推荐迭代法工程上也更稳。这题后续常追问“反转链表前 k 个节点”建议练习时顺便把指针操作的套路吃透。3.2 39题括号匹配与栈的使用边界题目描述给定一个只包含(、)、[、]、{、}的字符串判断它的括号是否合法。输入示例()[]{}返回true([)]返回false(]返回false(返回false。栈的经典应用。遇到左括号就入栈遇到右括号就弹栈顶比对#include stack #include string bool isValid(const std::string s) { std::stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; // 没有左括号可以配 char top st.top(); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { return false; // 类型不匹配 } st.pop(); } } return st.empty(); // 循环结束还有左括号剩余 }这道题的三个边界条件我列出顺序笔试时按这个顺序自查遇到右括号时栈为空说明多了一个右括号直接false。栈顶元素和当前右括号类型对不上比如([)]这属于“数量对但交叉错位”必须查类型。循环结束后栈不为空说明有多余的左括号比如(((返回false。工程上这套逻辑是编译器语法解析、表达式求值、IDE 代码缩进的基础。理解了这道题后面再学计算器实现里的中缀转后缀就会顺很多。复杂度稳定时间 O(n)空间 O(n)最坏情况全是左括号。4. 排序与递归的复杂度对比35题快排和36题斐波那契4.1 35题手写快速排序时选对分划方式题目描述对一个整型数组实现快速排序升序输出。快速排序的写法在教科书里有好几种我推荐复习时用 Lomuto 分划法因为代码最不容易写错int partition(int arr[], int low, int high) { int pivot arr[high]; // 选右端点作为基准 int i low - 1; // i 是最后一个 pivot 的位置 for (int j low; j high; j) { if (arr[j] pivot) { i; std::swap(arr[i], arr[j]); } } std::swap(arr[i 1], arr[high]); // 基准归位 return i 1; // 返回基准最终位置 } void quickSort(int arr[], int low, int high) { if (low high) { int p partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p 1, high); } }理解 Lomuto 的关键是i这个指针它永远指向“已经扫描过的部分里最后一个小于等于 pivot 的元素”。j从头扫到尾只要发现arr[j] pivot就把它换到i1的位置。扫描结束i1就是 pivot 该待的地方。为什么推荐 Lomuto 而不是教科书里那种“左右双指针、一个从右往左找小、一个从左往右找大”的写法因为那种写法虽然实际运行更快但边界条件极其容易写串——我见过太多人把arr[i] pivot和arr[j] pivot的等号处理反导致死循环。Lomuto 几个分支清清楚楚考试时宁可慢一点也要写对。快速排序的复杂度要背清楚平均 O(n log n)最坏 O(n^2)发生在每次基准都恰好选中最大或最小元素比如对已排序数组固定选右端点。工程上会加随机选基准或者三数取中来规避。空间复杂度 O(log n)递归栈。还有一个特性不稳定排序这点面试喜欢追问。4.2 36题斐波那契数列是递归性能的典型教材题目描述求斐波那契数列第 n 项F(0) 0, F(1) 1, F(n) F(n-1) F(n-2)。输入示例n 10输出 55。这道题的三种写法正好可以对照“递归的性能陷阱”// 写法一朴素递归指数级复杂度n50 就卡死 long long fibRecursive(int n) { if (n 1) return n; return fibRecursive(n - 1) fibRecursive(n - 2); } // 写法二迭代滚动数组时间 O(n)、空间 O(1) long long fibIterative(int n) { if (n 1) return n; long long a 0, b 1; for (int i 2; i n; i) { long long c a b; a b; b c; } return b; } // 写法三记忆化递归时间 O(n)、空间 O(n) long long fibMemo(int n, std::vectorlong long memo) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; memo[n] fibMemo(n - 1, memo) fibMemo(n - 2, memo); return memo[n]; }朴素递归慢的原因值得展开它会把fib(n-1)和fib(n-2)当成两个独立问题递归求解于是fib(1)被重复计算了几万次。计算量以 1.618 的 n 次方增长n 50的时候要算大约 200 亿次实际跑起来按分钟计。迭代写法把每个子问题只算一遍这就是“重叠子问题”和动态规划思想的雏形。还有一个实际细节long long也扛不住很大的 n。fib(93)大约 1.22e19已经逼近long long最大值 9.22e18实际上fib(94)就会溢出。所以考试时如果 n 可能到 100题目一般会要求“输出对某个大数取模”或者你干脆用unsigned long long并小心验证范围。练习题里通常限制 n 60用long long没问题但要知道这个边界在哪。5. 数组与内存细节37题字符统计和38题动态二维数组5.1 37题字符频率统计的下标陷阱题目描述给定一个字符串统计每个字符出现的次数按字符从小到大输出出现次数大于 0 的项。输入示例s hello输出e: 1, h: 1, l: 2, o: 1。最简单高效的办法是用数组当哈希表ASCII 字符一共 256 个一个int count[256]足够#include iostream #include string void countCharacters(const std::string s) { int count[256] {0}; for (char c : s) { count[(unsigned char)c]; // 必须强转 unsigned char } for (int i 0; i 256; i) { if (count[i] 0) { std::cout (char)i : count[i] std::endl; } } }这题最大的坑在count[(unsigned char)c]。C 的char是有符号还是无符号由编译器决定很多平台上它是 signed取值范围 -128 到 127。如果字符串里有一个字节值大于 127 的字符直接count[c]就会用负数下标访问数组越界读内存结果完全不可预期。我见过有人在处理带重音符号的文本时程序突然输出一堆乱码排查半天才发现是这个负下标问题。另一个扩展点是如果字符串里包含中文UTF-8 多字节编码按char统计就失去意义了因为一个汉字由三到四个字节组成每个字节单独统计没有任何语义。这时候要用std::unordered_mapstd::string, int按“码点”或者按字节序列统计。练习题通常限 ASCII但要心里有数。复杂度时间 O(n)空间 O(1)固定 256 大小。这题还有个常见变体是找出现次数最多的字符只需要在统计时维护一个maxIndex就行。5.2 38题动态二维数组的申请与释放题目描述输入行数 n 和列数 m动态申请一个 int 类型的 n 行 m 列二维数组填入数据后输出最后正确释放内存。动态二维数组在 C 里的经典做法是指针数组int** createMatrix(int n, int m) { int** mat new int*[n]; // 先申请 n 个行指针 for (int i 0; i n; i) { mat[i] new int[m]; // 每行再申请 m 个 int } return mat; } void freeMatrix(int** mat, int n) { if (mat nullptr) return; for (int i 0; i n; i) { delete[] mat[i]; // 先释放每一行的数组 } delete[] mat; // 再释放行指针数组 }这里要背熟两条铁律第一new[]必须配delete[]new配delete绝对不能混用。释放了错误的对象行为未定义不报错才是运气好。第二释放顺序不能乱——先释放每行的mat[i]最后释放mat本身。如果反着来你会先丢了行指针数组后面每一行都找不着直接内存泄露。工程上我更推荐另一种布局开一块连续的一维数组来代替二维数组int* data new int[n * m]; // 访问第 i 行第 j 列data[i * m j] delete[] data;这种做法的好处我提三个一是缓存局部性好遍历时按连续地址访问快得多二是申请和释放都只做一次代码不容易出错三是不会有“每行指针散落各处”的内存碎片问题。做数值计算的项目基本都这么干。练习题如果没限定必须是int**可以主动用连续数组方案面试时反而显得有工程经验。排查内存错误我建议用 AddressSanitizer编译时加-fsanitizeaddress越界和泄漏会在运行时直接报出来比用valgrind在 Windows 折腾配置要省心得多。6. 十道题复盘考点地图与复习顺序十道题刷完先别急着翻下一批。我建议用一张表把知识点和易错点过一遍这比反复抄代码有效题号核心考点时间复杂度高频易错点31字符串、双指针O(n)把\0当有效字符交换32字符串、边界判断O(n)忽略大小写/非字母数字条件漏写33二分查找、区间不变量O(log n)mid 溢出、left mid死循环34链表、指针操作O(n)改指针前没保存next35分治、递归、不稳定排序O(n log n) 平均分划边界写错、基准退化36递归 vs 迭代、动态规划O(n) 迭代朴素递归重复计算、long long 溢出37哈希思想、类型转换O(n)signed char 负下标越界38动态内存、new/deleteO(n)释放顺序错、漏释放行39栈、括号类型匹配O(n)遇到右括号时栈空未判断40辗转相除法、溢出O(log min(a,b))LCM 先乘后除溢出我个人复习时的顺序是这样的先把 31、32、40 当热身题要求自己五分钟内无错写出来然后攻 33、36、37 这三道“模板题”重点背边界写法和复杂度最后啃 34、35、38、39 这四道数据结构题每道题至少手写两遍。两遍之间隔两周避免短期记忆的假象。实操上还有一个笨但有用的方法把每道题改一个条件再写一遍。比如 32 题改成忽略大小写33 题改成返回第一个等于 target 的下标39 题改成同时支持和的尖括号。这样一变你对原题的理解立刻暴露无遗比对着答案抄十遍都管用。这一批题目真正的价值不在于“会做”而在于“想明白为什么这么做”。链表断链的瞬间、二分死循环的调试、字符负下标的诡异越界——这些体验都是纸面刷题给不了的。把代码亲自跑通、把错误亲眼看到第 41 到 50 题再往下走就会轻松很多。