简介面向准备技术面试、希望夯实 C 算法功底的开发者这份《剑指Offer》配套源代码围绕数组、链表、树、栈与队列等基础结构展开并延伸到动态规划、递归、字符串匹配、排序查找、设计模式、STL 容器与智能指针、内存管理、面向对象、异常处理及模板泛型等高频考点可用于按专题刷题、对照实现与复盘解题思路从题目分类到代码组织均有对应线索。压缩包共 2098 个文件整体约 44.2MB其中 242 个 cpp 与 226 个 h 源文件构成主体辅以 txt 说明、vcproj/vcxproj 工程配置及 exe、pdb 等编译产物便于逐题阅读实现也能载入工程调试运行。目前已有 377 人学习读者可借助完整代码和工程结构理解每道面试题从思路到落地的过程观察边界处理、复杂度取舍与 C 特性的运用对时间与空间复杂度的权衡形成直观认识并通过动手编译调试积累排错经验适合作为面试冲刺与日常算法训练的参考。1. 从一道“看着送分”的题说起剑指 Offer C 这套题最常见的错误刷法就是按题号从头刷到尾刷到一半才发现真正卡人的不是算法难度。面试官开场问的往往不是“手写红黑树”而是“给你一个带指针成员的类把赋值运算符补全”——看着是送分题实际是 C 岗的筛人题。它不考你能不能背出 memcpy 的原型考的是你在处理指针成员时能不能同时照顾到自赋值、申请内存失败、返回引用这三件事。整套题真正拉分的地方集中在三块数据结构基本功、递归与动态规划的状态设计、以及 C 语言层面的边界意识。这套东西适合已经能写出“能跑”的代码、但被追问一句“这里会不会内存泄漏”就卡壳的人。2. 考点分布七类题型的分值重心与出场顺序2.1 题型地图哪几类题撑起了大半场面试六十多道题看着杂按考察目标拆开其实就七类。真正决定你能不能过线的是前三类的熟练度和第六类的稳定性剩下的属于加分项。题型大致题量一面出现频率拿分关键典型失分原因数组与字符串约 20 道高双指针、边界处理空串、长度为 1 的用例没跑链表约 10 道高断链顺序、哨兵节点指针改了但没保存后继树约 15 道高递归返回值设计自顶向下递归导致重复计算栈与队列约 8 道中辅助栈思想只想到暴力扫描递归与动态规划约 15 道中高状态定义、转移方程状态含义说不清就开写位运算与数学约 8 道中补码、溢出判断负数右移、INT_MIN 取反C 语言特性约 5 道高C 岗异常安全、const 正确性只答功能正确答不出异常路径这张表最该看的是最后一列的“典型失分原因”而不是第二列。题量分布只说明练什么失分原因才说明你练的时候该盯什么。数组题失分几乎都出在边界链表题失分几乎都出在指针保存顺序树题失分几乎都出在递归设计——这三件事都不是靠多刷题能自动解决的得靠每道题写完之后回头补一遍用例。面试里的出场顺序也有规律。一面通常从数组或字符串起步难度低、好展开用来确认你能把思路翻译成无 bug 的代码然后上一道链表或树的题看你对指针和递归的掌控最后可能追加一道 C 语言特性题用来区分“会写算法的人”和“会写 C 的人”。二面反而更爱直接甩动态规划或者设计类题。搞清楚这个节奏你准备的时候就知道哪块要练到闭眼写、哪块只要说清思路。2.2 C 岗的隐性考点指针、const 与异常安全很多人把剑指 Offer C 当成纯算法题集忽略了里面那几道语言特性题。这类题数量少但区分度极高因为它没法靠背题解混过去——面试官追问两句就能看出你是真写过带资源管理的类还是只会用 vector。最典型的是赋值运算符函数。标准答案里那几个动作缺一个就掉一档。class MyString { public: explicit MyString(const char* data nullptr); MyString(const MyString other); MyString operator(const MyString other); // 返回引用支持 a b c ~MyString(); private: char* m_data_ nullptr; }; MyString MyString::operator(const MyString other) { if (this other) { return *this; // 自赋值直接返回否则下面先删后拷会读到已释放内存 } char* temp new char[std::strlen(other.m_data_) 1]; // 先申请新内存 std::strcpy(temp, other.m_data_); // 再拷贝内容这一步抛异常也不影响原对象 delete[] m_data_; // 最后释放旧内存 m_data_ temp; return *this; // 返回 *this 以支持连续赋值 }这段代码里有四个必须说出口的点。第一是自赋值检查不写这行s s时会先 delete 掉自己的内存再去读它属于未定义行为。第二是“先 new 后 delete”的顺序反过来写就不是异常安全的——如果 new 抛异常原对象的指针已经悬空析构时二次释放直接崩溃。第三是参数用 const 引用既避免拷贝又保证不修改源对象。第四是返回MyString而不是MyString或void前者支持连等后者在链式调用里直接编译不过。面试官顺着这题会追问三层。第一层问“为什么不用 memcpy”答“遇到重叠内存会出问题而且 strcpy 语义更清楚”第二层问“如果 new 失败怎么办”答“原对象保持不变调用方拿到的对象仍是有效状态这本身就是异常安全的体现”第三层问“能不能用拷贝并交换copy-and-swap实现”答“可以先按值传参完成拷贝再 swap代码更短代价是多一次拷贝”。三层都接得住这道题才算满分。提示C 岗的边界题不要只答“功能正确”。面试官默认你能写对功能他想听的是异常路径、资源归属和 const 正确性。2.3 真题演练从这道题看答题的完整闭环把上面这题当成模板题因为它能套出所有语言特性题的答题结构。完整回答顺序是先复述需求并确认约束“这个类管理堆内存允许拷贝需要支持连续赋值对吗”再给出接口声明的关键点返回引用、const 参数然后写实现最后主动补一句“我考虑过自赋值和异常安全两种情况”。主动补这一句的价值在于它把面试从“你写完了吗”变成“你还想到了什么”。面试里最吃亏的不是写错是写对了但没说清为什么这么写。同样一段实现只交代码的人被归到“能干活”讲清四个决策点的人被归到“能维护”这两档在定级上差得不少。3. 高频考点数组与字符串的双指针三板斧3.1 双指针的三种形态对撞、快慢、滑动窗口数组和字符串题占比最大但解法收敛得很厉害绝大多数落到三种双指针形态上。对撞指针是两个下标从两端往中间走典型场景是“和为 S 的两个数字”“反转字符串里的元音”“有序数组的两数之和”。它的前提通常是有序或者问题本身有对称性用一次遍历换掉两层循环。快慢指针是同向不同速典型场景是“调整数组顺序使奇数位于偶数前面”“删除重复项”“移动零到末尾”。它的本质是用一个慢指针维护“已处理好的区间”快指针负责扫描写回时覆盖。滑动窗口是区间伸缩典型场景是“最长不含重复字符的子字符串”“和为 S 的连续正数序列”“最小覆盖子串”。难点全在窗口收缩条件上什么时候右移扩大什么时候左移收缩收缩到什么时候停。写之前必须用一句话把条件说清楚说不清就一定会写出死循环或者漏解。注意双指针题在动笔前先把“指针含义”写下来。比如“left 指向当前窗口的第一个字符”写清楚这一句边界判断基本不会错。3.2 真题调整数组顺序使奇数位于偶数前面题目本身很简单扫描一遍分两拨就行。但面试官考的是可扩展性他会追问“如果改成能被 3 整除的放前面呢”“如果改成负数放前面呢”。能想到把判断条件抽出去的人和重写一遍循环的人是两种评价。// 把“是否满足条件”抽成函数指针换规则时不用动主逻辑 void reorder(int* data, unsigned int length, bool (*func)(int)) { if (data nullptr || length 0) { return; // 入参校验空指针和空数组必须挡在循环外 } int* begin data; int* end data length - 1; while (begin end) { while (begin end !func(*begin)) begin; // 跳过已经在左侧的元素 while (begin end func(*end)) --end; // 跳过已经在右侧的元素 if (begin end) { std::swap(*begin, *end); } } } bool isEven(int n) { return (n 1) 0; } // 判断规则可替换参数说明data是数组首地址长度由length单独传入——这是 C 数组传参的常规写法因为形参退化成指针后sizeof拿不到真实长度。func返回 true 表示该元素应该排在右侧这里传入isEven就是把偶数赶到后面。逻辑上有两个点容易翻车。内层两个 while 必须都带begin end判断少一个就会越界交换前再判一次begin end是因为两个内层循环结束后指针可能已经交叉。这两处是这类题最常见的崩溃来源手写时逐行念一遍条件就能避免。面试官接着会问时间空间复杂度时间是 O(n)每个元素最多被访问两次空间是 O(1)只用了两个指针。再追问稳定性答“这种交换会打乱相对顺序如果需要保持奇数之间、偶数之间的原有次序就得用额外数组或者稳定的划分方式空间换稳定”。答到这里这道题的区分度就吃满了。3.3 真题最长不含重复字符的子字符串滑动窗口的标准题但它是失分重灾区因为窗口左边界怎么更新有多种写法写错一个加减号就得到错误答案。int longestUniqueSubstring(const std::string s) { int last[256]; // 记录每个字符上次出现的位置 std::fill(last, last 256, -1); int left 0, best 0; for (int right 0; right static_castint(s.size()); right) { unsigned char c static_castunsigned char(s[right]); // 先转无符号避免负下标 if (last[c] left) { // 重复字符落在当前窗口内才需要收缩 left last[c] 1; // 窗口左边界跳到重复字符的下一位 } last[c] right; best std::max(best, right - left 1); } return best; }参数说明last用 256 大小的数组做哈希下标是字符的 ASCII 值值是它最近一次出现的下标用std::fill初始化成 -1 表示“从未出现”。left和right是闭区间窗口的两端best记录历史上最大的窗口长度。关键在if (last[c] left)这个条件。如果只写last[c] ! -1那当重复字符出现在窗口左边之外时会把left往回拉窗口直接算错。比如abba处理到最后一个a时last[a]是 0而此时的left已经是 20 不在窗口内不该收缩。这一处是这道题最高频的错误写完之后必须拿abba、abcabcbb、bbbbb三个用例手推一遍。面试官通常会追问复杂度时间是 O(n)right走一遍left单调不减空间是 O(1)因为字符集大小固定为 256不随输入规模增长。如果换成 Unicode就改成哈希表空间变成 O(k)k 是字符集实际出现的字符数。这个补充能体现你对“O(1) 空间”的定义是清楚的——常数与输入规模无关不是“用了一个数组”。4. 高频考点链表与树的指针操作画图比背题管用4.1 链表题的三个固定动作哨兵节点、断链顺序、返回头链表题不考思路考手感。思路谁都能说出来能不能一次写对看的是你有没有固定动作。第一个动作是哨兵节点dummy。凡是涉及“可能修改头节点”的题一律先建一个栈上的 dummy让dummy.next head所有插入删除都在后面做最后返回dummy.next。这一步能省掉大量“如果头节点被删了怎么办”的分支。第二个动作是断链前先保存后继。改cur-next之前必须把原来的next存到临时变量里否则后半条链就找不回来了。这个顺序错了代码跑起来就是段错误或者死循环而且调试时很难看出问题在哪。第三个动作是明确返回值。返回的是新头、原头还是void写之前想清楚。反转链表返回新头删除节点返回原头合并链表返回合并后的头——这种约定在面试里说一句“我返回的是新链表的头节点”能省掉后面很多误会。4.2 真题反转链表与合并两个排序链表反转链表是三指针的标准应用写的时候把三个指针的含义在注释里标出来面试官一眼能看出你想清楚了。struct ListNode { int val; ListNode* next; explicit ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; // 已反转部分的头 ListNode* cur head; // 当前待处理节点 while (cur ! nullptr) { ListNode* next cur-next; // 先存后继否则断链后找不回来 cur-next prev; // 反向指 prev cur; // prev 前移 cur next; // cur 前移 } return prev; // 循环结束时 cur 为空prev 是新头 }参数就是原链表头返回反转后的新头。空链表进来直接返回nullptr因为prev初始就是空循环进不去返回值天然正确——这就是把初始条件设计对的收益不需要额外写 if。合并两个排序链表的关键是 dummy 节点加“剩余整段挂上”。ListNode* merge(ListNode* a, ListNode* b) { ListNode dummy(0); // 栈上哨兵省掉头节点判空分支 ListNode* tail dummy; while (a ! nullptr b ! nullptr) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next (a ! nullptr) ? a : b; // 剩余部分整段挂上不用逐个搬 return dummy.next; }这里的决定了相等元素的相对顺序用小于等于就是稳定合并面试官问“稳定性”时这就是答案。循环结束后不要写 while 一个个接直接把非空的那条链挂上去因为链表剩下的部分本身已经有序逐个接只是浪费。提示链表题写完拿三个用例手推空链表、单节点、两节点。这三个能覆盖绝大多数指针错误。4.3 树的递归先想清楚返回什么再想怎么递归树题基本全是递归而递归写不对九成是因为没想清楚“这个函数返回什么”。返回值定了递归结构就定了。常见返回值有三类。返回布尔值用于判断类问题比如“是否对称”“是否平衡”“是否存在路径”返回节点指针用于构造和修改类问题比如“翻转二叉树”“合并二叉树”“树的子结构”返回整型或 pair用于统计类问题比如“最大深度”“直径”“路径和”。最容易被忽略的是第二类里的“返回 pair”。当一个问题需要同时知道两件事比如“这棵子树是否平衡”和“这棵子树的高度”返回单个值就会逼你写两个递归复杂度直接从 O(n) 掉到 O(n²)。4.4 真题平衡二叉树判断为什么你的递归是 O(n²)自顶向下的写法很好想对每个节点求左右子树高度判断差的绝对值是否不超过 1然后递归判断左右子树。问题是求高度本身要遍历一遍子树外层再遍历一遍节点整体是 O(n²)。面试官让你优化时就是等你把这两个过程合成一个。// 返回 {是否平衡, 高度}后序遍历一次搞定 std::pairbool, int checkBalance(TreeNode* root) { if (root nullptr) { return {true, 0}; } auto left checkBalance(root-left); auto right checkBalance(root-right); int height std::max(left.second, right.second) 1; // 高度自底向上累加 bool ok left.first right.first std::abs(left.second - right.second) 1; // 平衡条件在三处同时成立 return {ok, height}; } bool isBalanced(TreeNode* root) { return checkBalance(root).first; }参数是树根返回值是“这棵子树是否平衡”加“这棵子树的高度”。关键在于先递归左右子树拿到结果再在本层合并——这就是后序遍历每个节点只被访问一次时间 O(n)。空间是递归栈深度最坏 O(n)退化成链平均 O(log n)。这题能延伸出一个通用套路只要递归函数需要携带多个信息就用 pair 或者自定义结构体别拆成两次递归。面试官听到“我让返回值携带高度避免重复计算”这句话基本就知道你写过优化版本不是只背过题解。5. 易错点五类“能跑通但拿不到分”的答案5.1 入参与边界上的三个失分点错在哪空指针和空容器不判直接进循环或者取首元素。为什么错面试官给的用例里一定有空的。数组题传nullptr加长度 0链表题传空头字符串题传空串这三种是最基本的防御。不判不是逻辑错是习惯差而习惯差在代码评审里比逻辑错更致命——逻辑错能改习惯错说明你长期不写防御代码。怎么答对每道题开头固定写两行判空并且说出口“我先处理空输入直接返回。”这一句话的价值是让面试官知道你是有意识地处理不是碰巧没崩。错在哪只跑题目给的样例不跑长度为 1 和长度为 2 的用例。为什么错长度为 1 的用例能暴露指针初始化的错误长度为 2 能暴露循环终止条件的错误。比如反转链表如果prev初始成head而不是nullptr长度为 1 时就露馅。很多人写完不测交上去被面试官一句“你用长度为 1 的数组走一遍”问住。怎么答对写完主动说“我拿三个用例过一遍空、单元素、双元素”然后当场手推。这个动作本身就在加分因为它证明你有自测习惯。错在哪位运算题不处理负数或者对INT_MIN取反、取绝对值。为什么错C 里负数右移是实现定义行为-1 1不保证得到 0INT_MIN取绝对值会溢出因为它的相反数超出 int 范围。这类题面试官一定会问边界问的就是这两个。怎么答对位运算题统一先说“我把输入当无符号处理”或者用static_castunsigned int转一下涉及绝对值时改用long long或者提前判断。答题时说一句“这里要防一下 INT_MIN”比写完不说强很多。5.2 递归与状态设计上的两个失分点错在哪明明可以用循环偏写递归深度一大就栈溢出。为什么错树题用递归是自然的但链表题用递归就要小心——链表长度可能是几万递归深度跟着走栈空间撑不住。面试官问“如果链表有十万个节点呢”就是在提示你这里有坑。怎么答对链表题优先写迭代用三指针或者 dummy 节点确实要递归时主动说明“这里的递归深度等于链表长度工程上我会改成迭代”。承认局限比嘴硬到底得分高。错在哪动态规划题上来就写转移方程说不清dp[i]代表什么。为什么错状态定义不清后面的初始化、遍历顺序、返回值全会跟着错。而且面试官只要问一句“dp[i]是什么意思”答不上来就说明你是背的题解不是自己推的。怎么答对动笔前先用一句话定状态“dp[i]表示以第 i 个字符结尾的最长无重复子串长度。”说完这句再写初始化和转移。状态定义说清楚了转移方程基本是自然推出来的。注意递归题被问“能不能不用递归”时不要直接说“不能”。先答“可以用显式栈模拟”再说“但这里递归深度可控我选递归更清晰”。6. 答题技巧拿到陌生题先做三分钟拆解面试现场最怕的不是不会是慌。慌起来就开始写代码写到一半发现思路不对改也改不动。我后来固定了一个三分钟流程不管题目熟不熟先走一遍再动笔。时间你做什么面试官在观察什么0:00–0:40复述题目问清输入范围和约束有没有真听懂需求0:40–1:30举一个 4 到 5 个元素的小例子手推一遍思路有没有具体依据1:30–2:20报暴力解的时间复杂度再说优化方向有没有复杂度意识2:20–3:00说清数据结构选型和函数返回值代码结构是否清楚写完之后用刚才的例子跑一遍报三个边界有没有自测习惯这五步里最容易被跳过的是第一步和最后一步而这两步恰恰最加分。问清约束能避免你按错误假设写完整道题——比如题目没说数组有序你按有序写了二分面试官一句“数组无序”就全废。写完自测能避免低级错误被当成能力问题——一个漏判空指针的答案在面试官眼里和思路错是同一个印象。第二步的小例子也有讲究不要举题目给的样例。用自己造的、包含重复元素或者边界值的小例子手推过程能让面试官跟着你的思路走他一旦跟上后面的代码他看得更顺。代码结构上有个具体做法先在纸上或注释里写函数签名和返回值含义再填实现。// 返回最长无重复子串的长度输入非空时才进循环空串返回 0 int longestUniqueSubstring(const std::string s);这一行签名里已经包含了三个决策参数用 const 引用、返回值是长度、空串由函数内部处理。写完签名剩下的就是填逻辑不会写着写着改结构。押题思路也可以按这个流程反推。面试前把七类题型各挑两道代表题每道题都用上面五步走一遍重点练“说”而不是“写”。因为面试里写代码的时间通常只有十分钟说不清思路的人根本写不完反过来说清楚的人哪怕代码只写一半面试官也能判断你会。血泪经验是我早期面试栽得最惨的一次题目本身不难是链表删除节点我上来就写写到一半发现头节点可能被删又回头加 dummy改得满纸涂改。后来复盘问题不在不会在于没花四十秒确认“头节点会不会被修改”。从那以后我每次拿到题都强制先问一句“输入会不会为空、头节点会不会变”再动笔。这个习惯比多刷五十道题管用。希望帮到你。本文还有配套的精品资源点击获取
