简介这份《剑指Offer》C源代码面向准备技术面试、希望系统刷题并提升算法实现能力的程序员也可作为高校数据结构与算法课程的配套练习素材。内容围绕书中经典题目展开覆盖数组、链表、树、栈与队列、动态规划、递归、字符串匹配、排序查找、设计模式、STL容器、智能指针、内存管理、面向对象、异常处理与模板泛型等主题读者可对照题目理解思路并动手调试。压缩包共2098个文件约44.2MB以242个cpp源文件、226个h头文件为主同时包含VC项目工程、编译中间文件、说明文本及少量C#示例便于直接打开工程复现与修改。已有377人学习适合按专题查漏补缺积累可运行的代码实现与排错经验。1. 从一道替换空格说起C 面试真题真正在考什么替换空格这道题多数人的第一反应是新建一个字符串、逐个字符扫、遇到空格塞进%20五行写完自我感觉良好。面试官接着问一句如果在原串上改且保证内存够用你怎么做从前往后搬会反复覆盖还没读到的数据正确做法是先数空格、把长度撑开、两个指针从后往前填。一个追问就把人分层了。剑指 Offer C 这套题被面试官反复抽中原因从来不是难而是每道题背后都挂着一串边界空指针、单元素、全负数、INT_MIN、重复元素。这份按题号组织的 C 源码价值不在“给出答案”而在于每个文件都把这类边界写进了注释和测试用例——它更像一本记录踩坑现场的手册。适合已经把题刷过一轮、但一上白板就露怯的人。2. 考点地图六类题型的分值权重与三层判分口径先看清整张地图再决定时间往哪投。剑指 Offer 的题目数量看着多落到面试现场其实收敛成六类而且每一类的“拿分点”完全不一样。有人把时间平摊给八十多道题结果链表题一写就丢头节点、树题递归返回值写反这就是没看清权重。2.1 六类题型与出场频率题型常考题量一面出场率主要失分点数组与字符串15 道以上极高原地修改覆盖、下标越界链表10 道左右高头节点处理、指针断链树12 道左右高递归返回值语义栈与队列6 道左右中两个结构的同步状态递归与动态规划10 道左右中高状态定义含糊位运算与数值细节8 道左右中符号位、整数溢出这张表的用法不是背是排优先级。数组字符串和链表是必须要得分的地方答错基本就结束了树题答得出来算加分位运算类题目出现频率不高但一旦抽到答不出会很尴尬因为它考的是 C 语言基本功而不是算法。2.2 判分口径面试官心里其实有三层第一层是“能不能编译”。C 面试里写伪代码是减分项面试官要看你是不是真写过。变量声明、引用传参、nullptr还是NULL这些细节在这种面试里是有意义的信号。第二层是“边界对不对”。一道题写完面试官十有八九会问输入为空怎么办只有一个元素呢全是负数呢这一问不是刁难是看你平时写代码有没有防御习惯。很多人代码逻辑完全正确却在这轮被扣掉印象分。第三层是“复杂度说不说得清”。你要能主动报出时间 O(n)、空间 O(1)并且解释为什么。像“两个栈实现队列”这种题单次pop最坏 O(n) 但均摊 O(1)这句话讲不讲得出来直接区分了背答案和理解。提示三层里最容易补的是第一层最容易被忽略的是第三层。写完代码主动报复杂度比等面试官问要加分得多。2.3 三道开胃真题的答题骨架第一道用两个栈实现队列。这题看着像送分但一半人会在“什么时候倒腾”上写错——每次 push 都倒一遍复杂度就废了。class MyQueue { public: void push(int x) { in.push(x); } // 入队永远压 in 栈 int pop() { if (out.empty()) { // 只有 out 空了才搬运保证均摊 O(1) while (!in.empty()) { out.push(in.top()); in.pop(); } } int v out.top(); out.pop(); return v; } int peek() { if (out.empty()) { // 与 pop 同一套搬运逻辑只是不弹 while (!in.empty()) { out.push(in.top()); in.pop(); } } return out.top(); } bool empty() { return in.empty() out.empty(); } private: std::stackint in, out; // in 管入out 管出 };参数说明in是入口栈out是出口栈。关键约束是“只在out为空时搬运”这样每个元素一生最多被搬两次均摊 O(1)。如果面试官追问“为什么不能每次 push 都倒”你就答那样单次 push 退化成 O(n)队列的均摊优势没了。第二道数组中重复的数字。面试官想听的不是哈希表而是“长度为 n、数字范围 0 到 n-1”这个条件怎么用。标准答法是原地交换把数字 i 放到下标 i 上一旦发现nums[i] nums[nums[i]]就找到了。时间 O(n)空间 O(1)。哈希表解法也要会但要主动说明它多花了 O(n) 空间。第三道从尾到头打印链表。两种答法栈显式和递归隐式栈。写递归时补一句“递归深度等于链表长度链表极长时有爆栈风险”这句话是加分项说明你知道递归的代价。3. 高频考点数组、字符串与位运算的四套固定解法这一块是得分的地方。四类题的解法基本是固定的练到能默写、能解释每一步为什么这么做就够用了。3.1 二维数组查找从右上角砍掉一行一列题目给一个每行递增、每列递增的矩阵判断目标值是否存在。暴力 O(mn) 太慢二分每行是 O(m log n)但最优解是从右上角出发。为什么是右上角因为右上角这个位置有两个性质往左都更小往下都更大。比较一次就能整行或整列地排除。左下角同理左上角和右下角不行因为两个方向同向排不掉。bool findNumberIn2DArray(std::vectorstd::vectorint matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; // 空矩阵必须先挡住 int rows matrix.size(), cols matrix[0].size(); int r 0, c cols - 1; // 从右上角起步 while (r rows c 0) { if (matrix[r][c] target) return true; else if (matrix[r][c] target) --c; // 当前元素偏大整列排除 else r; // 当前元素偏小整行排除 } return false; }参数说明r是行游标c是列游标循环条件是r rows c 0两个边界缺一不可。复杂度 O(m n)空间 O(1)。注意matrix[0].empty()这个判断很多人漏掉空矩阵传进来直接matrix[0]就越界了。3.2 替换空格从后往前双指针前面提过这题的核心是“原地改”。面试官给的场景通常是字符数组后面有足够空间要求就地替换。从前往后是 O(n²)因为每次插入都要把后面的字符整体后移。从后往前则是 O(n)先统计空格数算出新长度两个指针一个指向旧尾、一个指向新尾倒着填。std::string replaceSpace(std::string s) { int oldLen s.size(), cnt 0; for (char c : s) if (c ) cnt; // 先数空格才知道数组要撑多长 s.resize(oldLen 2 * cnt); // 每个空格多出 2 个字符位 int i oldLen - 1, j s.size() - 1; // i 走旧尾j 走新尾 while (i 0) { if (s[i] ) { s[j--] 0; s[j--] 2; s[j--] %; } else s[j--] s[i]; --i; } return s; }参数说明oldLen是原始长度cnt是空格数量新长度为oldLen 2 * cnt。注意填充顺序是倒着写0、2、%因为j在自减。如果面试官要求用char*版本逻辑完全一样只是要自己传入length和capacity。3.3 连续子数组最大和状态定义只有一句话动态规划在这一类题里最典型。状态定义f[i]表示以第 i 个数结尾的最大子数组和转移方程f[i] max(f[i-1], 0) nums[i]。含义是“前缀是负的就扔掉不如从我自己开始”。因为f[i]只依赖f[i-1]空间可以压到一个变量。这就是很多题解里那个“看起来像贪心”的写法。int maxSubArray(std::vectorint nums) { int best INT_MIN, cur 0; // best 初始化为最小整数不能写 0 for (int x : nums) { cur (cur 0 ? cur : 0) x; // 前缀为负就归零等价于 f[i]max(f[i-1],0)x best std::max(best, cur); } return best; }参数说明cur是当前结尾的最大和best是全局最大。best初值必须是INT_MIN如果写成 0全负数数组比如[-3, -1, -2]会返回 0这是最经典的一处翻车。面试官常追问“如果要求返回子数组的起止下标”那你需要额外记录起点cur归零时把start更新为i1best更新时同步记录区间。3.4 二进制中 1 的个数n (n-1)与负数陷阱常规写法是每次右移一位判断最低位但遇到负数会死循环——有符号右移是算术右移高位补齐符号位 1永远移不完。正确做法是把参数声明成无符号或者用n (n-1)。n (n-1)的效果是消掉最低位的 1循环次数等于 1 的个数比逐位判断更优。int hammingWeight(uint32_t n) { // 形参用无符号规避算术右移问题 int cnt 0; while (n) { n (n - 1); // 每轮消掉一个最低位的 1 cnt; } return cnt; }参数说明uint32_t保证是无符号 32 位。如果面试官坚持用int那就在函数体内先转成unsigned int再运算并主动说明为什么。追问还可能延伸到“判断一个数是不是 2 的整数次幂”答案就是n 0 (n (n-1)) 0。4. 高频考点链表与树的指针题递归怎么写才不虚指针题是 C 面试的主力。这类题的通病不是不会想而是写出来指针就断了。下面这套模板基本覆盖了八成的链表树题。4.1 链表四件套哨兵、快慢指针、反转、合并四个固定套路哨兵节点dummy省掉头节点判空、快慢指针找中点或倒数第 k 个、三指针反转、双路合并。其中“三指针反转”是最容易写丢的一步一定要先把后继存下来再改指针。ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; while (head) { ListNode* next head-next; // 先存后继否则改完 next 就找不回来了 head-next prev; prev head; head next; } return prev; // 循环结束时 prev 是新的头 } ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode dummy(0); // 哨兵节点避免处理“谁是头”的分支 ListNode* tail dummy; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; // 剩下的一段直接整体挂上 return dummy.next; }参数说明prev初始为nullptr正好成为反转后的尾节点dummy是栈上对象用dummy取地址最后返回dummy.next而不是dummy。合并时用而不是是为了保证相等时也保持“原顺序拼接”如果面试官问“稳定性”这就是回答点。快指针找倒数第 k 个节点的写法ListNode* getKthFromEnd(ListNode* head, int k) { ListNode* fast head; for (int i 0; i k; i) { if (!fast) return nullptr; // k 大于链表长度提前返回 fast fast-next; } ListNode* slow head; while (fast) { fast fast-next; slow slow-next; } return slow; // fast 到尾时slow 正好是倒数第 k 个 }这个写法的关键在“先检查再走”很多人的版本是while (k--) fast fast-next;k 超过长度时直接空指针解引用。4.2 递归的返回值语义树的子结构树题写崩八成是递归函数的返回值含义没定义清楚。以“树的子结构”为例需要一个辅助函数回答“以 A 为根和以 B 为根两棵树是否结构相同”而不是“A 是否包含 B”。// 判断两棵树是否结构和数值完全相同B 走完就算匹配 bool sameTree(ListNode* a, TreeNode* a2) { return false; } // 占位见下方真实版本上面这行是常见的错误示范把链表节点和树节点搞混。正确版本如下bool sameTree(TreeNode* A, TreeNode* B) { if (!B) return true; // B 匹配完说明 B 被完整包含 if (!A) return false; // A 空了但 B 还没完失配 if (A-val ! B-val) return false; return sameTree(A-left, B-left) sameTree(A-right, B-right); } bool isSubStructure(TreeNode* A, TreeNode* B) { if (!A || !B) return false; // 约定空树不是任何树的子结构 return sameTree(A, B) // 从当前根开始匹配 || isSubStructure(A-left, B) // 或者去左子树里找 || isSubStructure(A-right, B); // 或者去右子树里找 }参数说明sameTree的终止条件顺序不能换必须先判!B——因为 B 为空代表匹配成功而不是失败。这个“先判 B 再判 A”的细节是这类题最爱考的点。4.3 二叉搜索树后序遍历单调性判定给一个数组判断是不是某棵二叉搜索树的后序遍历。后序遍历的结构是“左子树、右子树、根”所以数组最后一个元素是根前面一段全部小于根后面一段全部大于根。bool verifyPostorder(std::vectorint post, int l, int r) { if (l r) return true; // 空区间或单元素合法 int root post[r], i l; while (i r post[i] root) i; // 左子树区间 int mid i; while (i r post[i] root) i; // 右子树区间 if (i ! r) return false; // 右子树里混进了比根小的非法 return verifyPostorder(post, l, mid - 1) verifyPostorder(post, mid, r - 1); }参数说明l和r是闭区间端点mid是右子树起点。第二个while走完后i必须等于r否则说明存在既不属于左也不属于右的元素。时间 O(n²)最坏退化成链如果面试官追问优化要提到单调栈的 O(n) 解法但白板上先把递归版写对更重要。4.4 面试官的三连追问写完树题追问基本固定时间复杂度多少空间复杂度多少能不能改成迭代前两个按实际情况报。递归的空间是栈深度最好情况 O(log n)最坏退化成链O(n)——这句话一定要说很多人只报 O(log n)被追问就露怯。第三个问题不要求你真写完迭代版但要能说出思路比如后序遍历可以用“根右左”的逆序技巧配合栈实现。提示递归题写完后主动补一句“这个解法在极端输入下会受栈深度限制”比等面试官问更主动。5. 易错题五个高频翻车现场与补救答法这一章是纯血泪经验。下面五个点每一个我都在不同的模拟面试里见过重复出现而且都是“逻辑其实会就是没写对”的类型。5.1 输入边界类的三个坑坑一空指针、空数组、空矩阵没判。错在哪函数第一行直接head-val或者matrix[0][0]。为什么错题目条件里写了“链表节点数大于等于 1”就还好但面试官经常当场加一句“如果传入空链表呢”。这时候你代码里的第一行就是崩溃点。怎么答对入口统一加三行防御——if (!head) return ...;、if (nums.empty()) return ...;、if (matrix.empty() || matrix[0].empty()) return ...;。写的时候顺口说一句“先挡住空输入”面试官会记住这个习惯。坑二整数溢出。错在哪求中点用(low high) / 2求幂用int result * base或者对大数取绝对值abs(INT_MIN)。为什么错low high超过INT_MAX就溢出成负数abs(INT_MIN)在补码下依然返回负数因为没有对应的正数。怎么答对中点写成low (high - low) / 2累乘前判断是否会溢出或者干脆用long long承接中间结果取绝对值前先判断是不是INT_MIN。这类题在“数值的整数次方”里最典型指数为负时还要先取倒数再算。坑三死循环。错在哪链表快慢指针步长写错、二分查找的low high和low high混用、while (i ! j)但两个指针永远碰不上。为什么错边界更新的方向错了。比如二分里写了low mid而循环条件是low high当区间只剩两个元素时mid恒等于low就卡死了。怎么答对二分统一用low high配low mid 1 / high mid - 1或者low high配low mid 1 / high mid两套不能混。写完在纸上跑一遍长度为 2 的用例三秒钟就能发现。5.2 语言与实现细节类的两个坑坑四原地修改时覆盖未读数据。错在哪字符串替换从前往后填、数组删元素边遍历边erase、合并两个有序数组从前往后写。为什么错目标位置跑到了源位置前面还没读的字符被新数据盖掉了。怎么答对只要涉及“原地改且新长度大于旧长度”一律从后往前。典型场景就是替换空格和合并两个有序数组这两道题的解法是同一套肌肉记忆。坑五递归里的重复计算与栈深度。错在哪斐波那契直接双递归、树的子结构里sameTree每次从头比、跳台阶不记忆化。为什么错f(n) f(n-1) f(n-2)的朴素递归是指数级n 到 40 就明显卡了。怎么答对能改成迭代就改成迭代斐波那契用两个变量滚动改不了就加记忆化实在要用递归主动报出复杂度并说明“可以用数组或哈希表缓存中间结果”。这句话说出来即使不写代码也是加分。注意这五个坑里有四个都不需要额外知识只需要写代码时多停三秒。面试现场的时间压力下这三秒往往就是分水岭。6. 押题与答题节奏上白板前的三分钟怎么用前面五章讲的是“会什么”这一章讲“怎么用出去”。很多人题目会做但在白板前的时间分配是乱的——上来就写写到一半发现思路错了擦掉重来时间就没了。我自己的节奏是固定三步每次上白板前先走一遍阶段时间要做的事说出口的话读题1 分钟复述输入输出、确认边界条件“我先确认一下输入会不会为空”讲思路1 到 2 分钟说解法、说复杂度、说取舍“暴力是 O(n²)我用双指针可以降到 O(n)”写代码主体时间先写主干再补边界“这里我加一个空判断”第一步最容易被跳过但它决定了后面所有事。有一道题我至今记得题目给的数组是“长度为 n元素范围 0 到 n-1”我没读这个条件直接上了哈希表面试官问“还能不能不用额外空间”我当场卡住。后来复盘才发现那句话就是解题钥匙藏在题面第一行。押题思路也一样不要平均用力。按近几年的出场频率最该练熟的是这几类数组的原地修改与双指针、链表的反转与合并、树的递归遍历与返回值语义、栈与队列的相互模拟、动态规划的一维状态压缩。位运算和数值类题出现频率低但“二进制中 1 的个数”“数值的整数次方”“把字符串转换成整数”这三道属于基本功抽到就得会因为面试官默认 C 选手应该掌握。还有一个小习惯值得养成写完代码后不要立刻说“写完了”而是拿一个具体的小用例口头跑一遍——比如“输入[1,2,3]第一次循环 i0cur 变成 1best 更新为 1……”这种自检比任何解释都有说服力而且经常能让你自己发现 bug。这套按题号组织的 C 源码我建议的用法不是从头刷到尾而是对照上面那张权重表先把数组、链表、树三块对应的题号抽出来精练每道题写完关掉参考实现、自己重写一遍再拿边界用例空、单元素、全负数、重复值跑一遍。源码文件里的注释和测试用例就是给这一步准备的别只抄解法。从那以后我每次上白板前都强制走一遍“读题—讲思路—写主干—补边界”这四步哪怕题目再简单也不跳。跳过一次翻车一次记性就是这么练出来的。希望帮到你。本文还有配套的精品资源点击获取