教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载《剑指offer》是程序员算法面试的经典训练书目本仓库以9 Algorithms Job Interview/剑指offer/README.md为核心笔记整理了 50 余道覆盖数值、字符串、链表、数组、栈与队列、矩阵、二叉树的高频面试题并在9 Algorithms Job Interview/codes/目录下沉淀了对应的 C 语言实现。本文以该笔记为骨架逐题讲解题意、核心思路、函数签名、复杂度与边界陷阱并对照仓库源码给出可直接运行的参考实现帮助读者形成题目→思路→代码→鲁棒性的完整备战闭环。一、先看 README 里的备考方法论原文档在开篇给出了三条贯穿所有题目的备考主线这也是面试中比会做某道题更重要的能力代码鲁棒性边界条件、特殊输入、异常处理尤其 C 语言中的空指针 NULL。仓库多个源码文件都能印证这一点例如 replce_blank.c 中if (source NULL) return NULL;的判空、char_first_appear_once.c 中if (tmp NULL) return \0;的兜底都是特殊输入优先处理的直接体现。分析方法画图链表、二叉树题几乎离不开、举例先用手工小例子跑通思路、分解把大问题拆成递归子问题。查找与排序是常考主线重点掌握二分查找、快速排序、归并排序。本文后续的旋转数组的最小数字数字在排序数组中出现的次数数组中的逆序对等题目正是这三板斧的直接应用。文档覆盖的题型分布可概括为数值 6 题、字符串 5 题、链表 7 题、数组与数列 15 题、栈与队列 3 题、矩阵 2 题、二叉树 10 题外加 C 语言层面的不能被继承的类 / Singleton / 赋值运算符函数 3 题。下面按原文档顺序逐类展开。二、数值类问题2.1 二进制中 1 的个数输入一个整数输出该数二进制表示中 1 出现的次数。例如 9 的二进制是1001输出 2。核心技巧只有一个表达式n n (n-1)。它的作用是每次消除二进制表示中最右边的那个 1循环次数恰好等于 1 的个数时间复杂度 O(1 的个数)。仓库中的完整实现见 one_appear_count_by_binary.cint one_appear_count_by_binary(int num){ int count 0; while(num !0 ){ num num-1; count; } return count; }该文件main中用10二进制 1010期望 2和33二进制 100001期望 2做了验证。相比逐位右移 1的写法n (n-1)避免了负数右移引入符号位的坑也更高效。注意文档中此函数签名为int one_appear_count(int n)在从 1 到 n 整数中 1 出现的次数一题中又出现了同名签名两题含义不同前者统计一个数的二进制位后者统计区间内十进制数字 1 的出现次数阅读时需区分。2.2 数值的整数次方实现double power(double base, int exponent)要求不得使用库函数。文档特别强调注意指数是 0 和负数的情况。仓库实现见 Power.c采用快速幂的递归形式指数每次右移一位、结果平方、按奇偶决定是否再乘一次 basedouble Power(double base, int exponent) { if (exponent 0) return 1; if (exponent 1) return base; double result Power(base, exponent 1); result * result; if (exponent 1) result result*base; return result; }这份代码的时间复杂度为 O(log n)。但源码注释自己也标注了Power(2,-3)//负数就挂了说明负指数没有处理同时base 0 exponent 0会出现除零。这正是文档强调代码鲁棒性的典型场景——面试时建议补充负指数先取绝对值计算再取倒数base 0且指数为负时返回错误标志或抛异常浮点数判等要用精度比较而非。2.3 打印 1 到最大的 n 位数比如 n3就打印 1 到 999。签名void print_to_max_with_length(int n)。此题真正的考点是大数陷阱当 n 很大时如 n20999…9远超int/long long的范围直接用数值递增会溢出。经典解法有两条路一是用字符串模拟十进制加法从 0 到 9 进位二是用递归做数字的全排列固定高位逐位枚举再过滤掉以 0 开头的串。仓库 codes 目录未收录本题实现读者可自行用这两种思路补全并额外验证 n1、n2 的小规模边界。2.4 求 12...n签名long long sum(unsigned int n);约束是不能用乘除法也不能用 for/while/if/else/switch 及条件判断语句。文档未给代码只给约束。常见解法思路有三类均与约束强相关利用的短路求值n (result n sum(n-1))用逻辑与的短路特性代替 if 终止递归利用 C 静态成员与构造函数创建 n 个对象构造函数累加静态计数器利用位运算模拟乘法n*(n1)/2中的乘法用移位加累加替代与下一题思路相通。2.5 不用加减乘除做加法求两个整数之和签名int sum(int a, int b)文档原写法int sum(int a,int b缺右括号属笔误实现时应补全。思路是位运算a ^ b得到不考虑进位的和(a b) 1得到进位二者相加直到进位为 0int sum(int a, int b) { while (b ! 0) { int carry (unsigned int)(a b) 1; // 进位 a ^ b; // 不带进位的和 b carry; } return a; }注意 C 中对有符号数左移是未定义行为严谨写法是先把a b转成无符号再移位。此题可与 2.4 联动既然加法可用位运算实现那么12...n的公式n(n1)/2在理论上也能只用位运算 递归完成。2.6 丑数只包含因子 2、3、5 的数叫做丑数ugly number如 62×3、82×2×2。求按从小到大的顺序第 1500 个丑数签名int ugly(int n)。朴素做法是对每个整数逐个判断能否被 2/3/5 整除到 1但第 1500 个丑数很大逐个扫描会超时。正确思路是三指针归并维护已生成的丑数序列用三个指针分别指向乘以 2、乘以 3、乘以 5 后最小的候选每次取三者最小值加入序列并推进对应指针第一个丑数是 1。时间复杂度 O(n)空间 O(n)。注意候选可能重复如 6 既来自 2×3 也来自 3×2取最小值时需要跳过重复值。三、字符串类问题3.1 替换空格把字符串中的每个空格替换成%20签名void replace_blank(char *str);。文档给出的方法论是二遍扫描第一遍统计空格个数算出替换后新串的结尾位置第二遍从后往前拷贝字符遇到空格就写入%20倒序写0、2、%。从后往前移动保证了不额外开辟新数组、每个字符只移动一次。仓库完整实现见 replce_blank.cchar *replace_blank(char *source){ int count 0; char *tail source; if (source NULL) return NULL; while(*tail ! \0){ if (*tail ) count; tail; } while(count){ if(*tail ! ){ *(tail2*count) *tail; }else{ *(tail2*count) 0; *(tail2*count-1) 2; *(tail2*count-2) %; count--; } tail--; } return source; }main中char str[100]we are happy;的用法值得注意必须用足够大的字符数组因为替换后长度增加若直接对字符串字面量操作会因只读内存崩溃后文 3.5 有同款真实案例。另需确认替换后的缓冲区容量足够否则会越界。3.2 把字符串转换成整数如12343567754→12343567754签名int strToInt(char *str)。文档列出的四个边界关键词是NULL、空串、正负号、溢出。仓库实现见 string_to_integer.c采用递归逐位累加int string_to_integer(char *s,int length){ if (length1) { return s[0]-?string_to_integer(s,length-1)*10-(s[length-1]-0):string_to_integer(s,length-1)*10s[length-1]-0; }else{ return s[0]-?-1/10:s[0]-0; } }这份代码在注释里自己列出了三大问题s 是空字符串、s 传参为非数字字符、超出整数所能表示范围——main中测试abcd输出的就是垃圾值证明这些边界全未处理。本题的正确打开方式是判空 → 跳过首字符正负号 → 逐位累加前先判断result (INT_MAX - digit)/10的溢出预检 → 非法字符立即返回错误码。把仓库这份问题版本与文档的四个关键词对照看恰好是一道找 bug 补鲁棒性的绝佳练习题。3.3 第一个只出现一次的字符在字符串中查找第一个只出现一次的字符签名char find_appear_once_char(char *string)。文档方法论哈希表存出现次数 二次扫描。第一次扫描建表第二次扫描按原顺序找第一个计数为 1 的字符。时间复杂度 O(n)空间 O(1)ASCII 字符用固定 256 长度的 int 数组。仓库有两份实现可对照char_first_appear_once.c 用int hash[256]{0};两趟扫描测试串77ah-ba-ccdeff返回hstring.c 中的first_appear_only_once思路相同还演示了用字符的 ASCII 码直接作为哈希表下标hash_table[*tmp]找不到时返回0。注意若要支持中文字符或多字节编码需要改用更宽的键空间或真正的哈希表此时空间不再是常数级。3.4 字符串的排列输入一个字符串打印该字符串中字符的所有排列签名void print_full_permutation(char *string)。文档方法论递归、分解。经典写法是固定首字符对剩余部分全排列void permute(char *s, int start, int end) { if (start end) { printf(%s\n, s); return; } for (int i start; i end; i) { swap(s[start], s[i]); permute(s, start 1, end); swap(s[start], s[i]); // 恢复避免重复分支 } }如果输入含重复字符需要在for内跳过与s[start]相同的字符或用 set 去重否则会产生重复排列。递归深度为字符串长度时间复杂度 O(n!)。3.5 反转单词顺序 VS 左旋转字符串a. 反转单词顺序翻转句子中单词的顺序但单词内字符不变如I am a student.→student. a am I。文档方法论是先以单词为单位翻转、整个句子再翻转一次两步翻转法。仓库 revert_by_word.c 实现了_reverse(start,end)区间逆序、_revert_by_word按空格切分逐词逆序和入口revert_by_word先整句逆序再逐词逆序。string.c 的revertByWord则用了先逐词逆序、再整句逆序的等价顺序并演示了不用临时变量的交换技巧。特别值得注意revert_by_word.c的main中char *test how are you ?;直接对字符串字面量就地改写注释留下了为啥运行时 bus error的疑问——这正是 C 语言的经典陷阱字符串字面量存储在只读段就地修改会触发总线错误。正确做法是拷贝到char dest[]数组再操作。这个案例与 3.1 中str[100]的做法形成正反对照是特殊输入与运行环境鲁棒性的活教材。b. 左旋转字符串把字符串最前面的若干位转到尾部如abcedfsz和数字 2结果是cedfszab签名char *left_rotate_string(char *s,int n)。技巧与单词反转完全同构先翻转前 n 个字符再翻转第 n 个之后的字符最后整体翻转一次三步 O(n) 完成原地左旋。四、链表类问题文档链表部分只给出思路与签名仓库 codes 目录暂未收录链表源码以下思路均源自文档并给出通用实现要点。4.1 从尾到头打印链表签名void print_reversing(LinkList *head);。文档方法论是栈遍历一遍把节点值压栈再依次出栈打印也可等价地用递归递归本质就是栈但链表很长时递归栈会溢出显式栈更稳。4.2 两个链表的第一个公共节点签名LinkListNode *common_node(LinkList *head1, LinkList *head2);文档中head2漏写了指针星号应为LinkList *head2。文档方法论长的链表先走 k 步。先分别遍历两条链求长度算出长度差 k让长链先走 k 步然后两条链同步前进第一个相遇的节点即公共节点。时间复杂度 O(nm)。两条链Y 形相交是前提假设若无公共节点需返回 NULL。4.3 在 O(1) 时间删除链表节点已知头节点指针和指向待删除节点的指针签名void deleteNode(LinkList *head, LinkList *targetToDelete);。文档方法论用下一个节点的内容覆盖当前删除节点的内容再删除下一个节点——即狸猫换太子。将target-next的值拷贝到target然后让target-next target-next-next并释放后者。边界情况若待删除节点是尾节点无后继可覆盖则仍需从头遍历找到前驱若链表只有一个节点则直接置空头指针。这就是O(1) 平均、尾节点 O(n)的经典折中。4.4 输出链表中倒数第 K 个节点签名void print_lastK(LinkList *head);文档签名未含 K 参数实现时应补上。文档方法论两个指针一个先走 k-1 步。指针 A 先走 k-1 步然后 A、B 同步前进A 到末尾时 B 恰好指向倒数第 K 个节点。注意 k 大于链表长度、k 等于 0 的边界若链表长度为 n 且 k 合法只需一次遍历。4.5 反转链表签名void reverse(LinkList *head);。文档方法论三个指针——prev、curr、next遍历时保存后继再改方向void reverse(LinkList **head) { LinkList *prev NULL, *curr *head; while (curr ! NULL) { LinkList *next curr-next; // 先保存后继 curr-next prev; // 反转方向 prev curr; curr next; } *head prev; }文档在同节末尾追问反转二叉树呢——这正是二叉树章节 8.3 的伏笔交换左右子树体现了两类题型的联动。4.6 合并 2 个排序的链表签名LinkList *merge(LinkList *one, LinkList *two);要求合并后依然有序。文档方法论递归。比较两链头节点较小的作为新链头其 next 递归合并剩余部分LinkList *merge(LinkList *one, LinkList *two) { if (one NULL) return two; if (two NULL) return one; if (one-value two-value) { one-next merge(one-next, two); return one; } else { two-next merge(one, two-next); return two; } }递归写法简洁也可以用三指针迭代消除栈开销两者时间均为 O(nm)。4.7 复杂链表的复制每个节点除m_pNext外还有一个指向任意节点的m_pSibling文档给出结构体定义typedef struct LinkListNode{ int m_value; LinkListNode *m_pNext; LinkListNode *m_pSlbling; // 文档原笔误 Slbling应为 Sibling }LinkList;签名LinkList * copy(LinkList *head);。经典三步法第一遍在每原节点后复制一个新节点并插入新节点-next 原节点-next; 原节点-next 新节点第二遍设置新节点-m_pSibling 原节点-m_pSibling-next第三遍按奇偶位置拆分成原链与新链。时间 O(n)、空间 O(1)比先拷贝 next 链再用 O(n²) 逐节点找 sibling的朴素法优。五、数组与数列问题5.1 数组中出现次数超过一半的数字签名int find_more_than_half_num(int *nums, int length);。文档方法论遍历数组下一个数字和之前保存的数字一样就 1否则 -1——即摩尔投票。计数归零时更换候选者。注意此算法只保证若存在超过一半的数则必然是它因此最后需再扫描一遍验证候选出现次数是否真的超过 n/2。5.2 n 个整数中最小的 K 个数签名void find_least_k(int *data, int n, int *output, int k);。文档给出两条路线快速排序的 partition与最大堆。前者期望 O(n)通过 partition 把第 k 个元素放到正确位置其左侧即最小的 k 个数不要求有序后者维护大小为 k 的最大堆遍历一遍堆顶即答案适合海量数据流场景参考仓库4 Tree/8-堆/Top-K 问题.md的延伸讨论。文档随后反问最大的 K 个数呢——把最大堆换成最小堆即可思路完全对称。5.3 连续子数组的最大和输入一个有正有负的整数数组求所有子数组和的最大值签名int max_of_subarray(int *data, int length)。文档方法论分析规律、动态规划。dp[i] max(data[i], dp[i-1] data[i])若前一个累加和为负则果断丢弃从头开始同时用全局变量跟踪历史最大值。时间 O(n)、空间 O(1)只需两个变量这是动态规划在数组题中最典型的入门应用。5.4 从 1 到 n 整数中 1 出现的次数如 n12含 1 的数字有 1、10、11、12共出现 5 次签名int one_appear_count(int n)注意与 2.1 同名不同义。朴素 O(n log n) 逐个数会超时正确做法是按数位统计对每一位个/十/百…分别统计该位上出现 1 的次数公式与高位、当前位、低位三部分相关总体 O(log n)。面试时可先用小例子如 n12手工推演再总结规律。5.5 把数组排成最小的数输入一个正整数数组把所有数字拼接起来排出一个最小数签名int minSort(int *nums, int length);。核心是自定义比较规则对任意两个数字 a、b比较拼接后的ab与ba小的在前。注意要把数字转成字符串比较以避免整数拼接溢出排序后按序输出即答案。延伸若求最大数比较规则取反即可。5.6 菲波那切数列文档给出定义F(0)0F(1)1F(n)F(n-1)F(n-2)即 0、1、1、2、3、5、8、13、21、34、……签名long long fabonacci(unsigned n)。仓库 fibonacci.c 给出了两种实现的直接对比fibonacci(int n)教科书式递归代码最直观但存在大量重复计算时间复杂度 O(2^n)fibonacci2(int n)循环迭代只保留前两项滚动累加时间复杂度 O(n)、空间 O(1)main中fibonacci2(40)计时验证了迭代版的效率。面试的标准答法是先递归演示思路再主动切换到迭代版并说明复杂度差异还可以进一步提出矩阵快速幂的 O(log n) 优化。注意返回值用long long是为容纳 n 较大时的溢出空间。5.7 调整数组顺序使奇数位于偶数前面调整后所有奇数在前半部分、偶数在后半部分签名void reorder(int *data, int length)。文档方法论两边向中间扫描——与快速排序 partition 同构左指针向右找偶数右指针向左找奇数找到就交换两指针相遇即结束。若题目再加保持相对顺序的要求则需改用稳定做法如借助辅助数组或插入式移动。5.8 旋转数组的最小数字旋转数组指把递增数组最开始的若干元素搬到末尾如 {3,4,5,1,2} 是 {1,2,3,4,5} 的一个旋转求最小元素签名int min(int *num, int length)。由于数组两段各自有序可用二分比较mid与high若mid high则最小在右半若mid high则最小在左半含 mid相等时只能顺序收缩如 {1,1,1,0,1} 这类含重复的场景退化为线性扫描。这是二分查找在部分有序数组上的标志性应用。5.9 数组中只出现一次的两个数字数组中除 2 个数字外其余都出现 2 次找出这两个数签名void find_two_numbers_appear_once(int *data, int length, int *output)。文档给出了完整推导先说明退化情形若只有 1 个数字只出现一次把数组依次异或成对的抵消后即该数字有两个目标数时全数组异或结果是a ^ b必非 0其二进制表示中至少有一位是 1在结果中找到第一个为 1 的位记为第 n 位以第 n 位是否为 1为标准把数组分成两个子数组每个子数组各含一个只出现一次的数字分别异或即得答案。时间复杂度 O(n)空间 O(1)是异或 二进制分组思想的完整演绎。5.10 和为 s 的两个数字 VS 和为 s 的连续正数序列两个数字输入递增排序数组和一个数字 s找出和为 s 的两个数输出任意一对即可签名void print_two_numbers(int *data, int length, int sum)。文档方法论两边向中间扫描——左指针 右指针和太大右移左移和太小左移右移相遇即无解。连续正数序列找所有和为 s 的连续正数序列如 s9 时 234、45。仓库 print_continuous_sequence_sum.c 给出了滑动窗口实现small1、big2起步窗口和小了big扩窗大了small缩窗命中即打印直到big n/21while(smallbig bign/21){ if (sumn) printf(%d ,%d\n,small,big); while(sumn){ sum-small; small; if (sumn) printf(%d, %d\n,small,big); } big; sumbig; }该窗口伸缩思路与两个数字的左右指针本质一致可归入双指针家族统一复习。5.11 数组中的逆序对前面数字大于后面数字即构成逆序对如 {7,5,6,4} 的逆序对为 (7,5)(7,6)(7,4)(5,4)(6,4)签名int reversePairs(int *data, int length)。文档方法论归并排序O(n log n)空间 O(n)。归并过程中合并两个有序段时若左段元素大于右段元素则左段剩余元素全部与它构成逆序对累加计数即可。朴素 O(n²) 双重循环仅适用于小数据海量场景见91 Algorithms In Big Data/Hash映射,分而治之.md必须用归并。5.12 数字在排序数组中出现的次数如 {1,2,3,3,3,3,4,5} 中 3 出现 4 次签名int appear_count(int *nums, int length, int n);。文档方法论二分查找找第一个 3 和最后一个 3 的位置次数 last - first 1。仓库 binary_search.c 给出了完整实现两个二分的细节差异值得细读int binary_search_first(int *a,int length,int key){ // 找第一个 int low0, highlength-1, mid0; while(lowhigh){ mid (lowhigh)/2; // 下取整 if (a[mid]key) high mid; // 命中或偏大 → 向左收 else low mid1; } return high; } int binary_search_last(int *a,int length,int key){ // 找最后一个 int low0, highlength-1, mid0; while(lowhigh){ mid (lowhigh1)/2; // 上取整防止死循环 if (a[mid]key) low mid; // 命中或偏小 → 向右收 else high mid-1; } return low; } int element_appear_times(int *a,int length,int key){ return binary_search_last(a,length,key)-binary_search_first(a,length,key)1; }main用{2,3,4,4,4,4,4,5,5,7,7,11,...}分别验证了 2、4、11、36不存在、54 的出现次数。找最后一个时必须用上取整的(lowhigh1)/2否则区间会卡死在[low, low]无法推进——这是二分边界题的高频失分点。若 key 不存在函数会返回相邻元素的边界位置实际使用时需先校验a[first] key。5.13 n 个骰子的点数把 n 个骰子丢到地上朝上一面的点数之和为 s输入 n 打印各可能值出现的概率签名void print_sum_probability(int n)。范围分析s 最小 n、最大 6n共 6n-n1 种可能。实现用动态规划dp[i][j]表示 i 个骰子掷出和为 j 的方案数递推dp[i][j] dp[i-1][j-k]k1..6总方案数 6^n概率 方案数/6^n。第一版可用二维数组优化版只需两行滚动数组。5.14 扑克牌中的顺子从扑克牌中随机抽 5 张判断是不是顺子A 是 1J~K 是 11~13大小王可看成任意数字签名bool is_straight(int *data, int length)。套路先把大小王记为 0排序后统计 0 的个数再扫描非零相邻数字若相等直接不是顺子对子否则累计间隔缺口gap (diff - 1)最后0 的个数 gap即为顺子。注意处理 A 到底是 1 还是 14 需与面试官确认本题按文档默认 A1。5.15 圆圈中最后剩下的数字约瑟夫问题文档给出背景约瑟夫环N 个人围成一圈从第一个开始报数第 M 个被杀掉最后剩一个。例如 N6、M5被杀顺序是 5、4、6、2、3。题目形式0,1,...,n-1 这 n 个数字排成圆圈从 0 开始每轮删除第 m 个数字求最后剩下的数字签名int last_remaining(unsigned int n, unsigned int m);。两条路线一是用循环链表/数组模拟删除过程O(n·m)二是数学递推记f(n,m)为 n 个数字时的幸存者下标则f(n,m) (f(n-1,m) m) % n边界f(1,m) 0迭代 O(n) 求解——面试时建议先讲模拟再给出递推公式展示从暴力到数学的优化路径。六、栈与队列6.1 用两个栈实现队列队列 尾部插入、头部删除。用 stack1 负责入队stack2 负责出队出队时若 stack2 为空先把 stack1 全部倒入 stack2倒序再 pop stack2 顶。摊还复杂度 O(1)。对应文档队列就是在尾部插入节点头部删除节点的描述。6.2 实现能返回栈的最小元素的函数签名int min(Stack *stack);。文档方法论最小元素用辅助栈保存。每次 push 时若新元素 当前最小值则同时压入辅助栈pop 时若弹出的正是当前最小值辅助栈同步弹出min直接取辅助栈顶。辅助栈与主栈同高各操作均为 O(1)。6.3 栈的压入、弹出序列输入两个整数序列第一个是压入顺序判断第二个是否为可能的弹出顺序签名bool is_pop_order(int *push, int *pop, int length);。文档示例1,2,3,4,5 是压栈序列4,5,3,2,1 是弹栈序列但 4,3,5,1,2 不是。做法用真实辅助栈模拟——依次压入 push 序列每次压入后检查栈顶是否等于 pop 序列当前元素相等则弹出并推进 pop 下标循环往复最终辅助栈为空则序列合法。这个贪心模拟在栈类题中几乎必考。七、矩阵文档提示矩阵用二维数组表示代码中通常按一维连续存储、matrix[i*cols j]索引。7.1 从外向里顺时针打印矩阵签名void print_matrix_clockwise(int *matrix, int cols, int rows);。仓库 print_matrix.c 给出了完整实现按圈递归每圈从(start,start)出发依次打印上边、右边、下边、左边四条边void print_matrix_incircle(int *matrix,int rows,int cols,int start){ int endX cols-start-1; int endY rows-start-1; for(int istart;iendX;i) printf(%d ,matrix[start*rowsi]); // 上 for(int istart1;iendY;i) printf(%d ,matrix[i*rowsendX]); // 右 for(int iendX-1;istart;i--) printf(%d ,matrix[endY*rowsi]); // 下 for(int iendY-1;istart;i--) printf(%d ,matrix[i*rowsstart]); // 左 } void print_matrix(int *matrix,int rows,int cols){ if(matrixNULL) return; if(rows0 || cols0) return; int start 0; while(start*2cols start*2rows){ // 圈起始点约束 print_matrix_incircle(matrix,rows,cols,start); start; } }实现细节main用 4×4 的{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}验证圈终止条件是start*2 rows start*2 cols打印下边、左边时需用/防止与上边、右边重复打印矩形非正方形时尤其重要。文档还留了延伸题按大小顺序打印矩阵类似顺时针的排序变体。7.2 二维数组中的查找二维数组每一行从左到右递增、每一列从上到下递增判断是否包含某个整数签名bool find(int *matrix, int rows, int columns, int numbers)。经典策略从右上角或左下角开始——右上角元素是所在行的最大、所在列的最小与目标比较一次即可排除一整行或一整列每次收缩一步O(rowscolumns)。从左上角出发则无法唯一决策这是本题的关键考点。八、二叉树8.1 重建二叉树输入某二叉树的前序遍历和中序遍历结果重建二叉树签名BinaryTree *construct(int *preorder, int inorder, int length);文档将inorder误写为inroder应为数组指针。原理前序第一个元素是根在中序里定位根左边是左子树中序、右边是右子树中序根据左右子树长度切分前序递归构建。哈希表预存中序位置可把单层查找降到 O(1)整体 O(n)。8.2 树的子结构输入两棵二叉树 A 和 B判断 B 是不是 A 的子结构签名bool subTree(BinaryTreeNode *root1, BinaryTreeNode *root2);。文档给出结构体struct BinaryTreeNode{ int m_value; BinaryTreeNode *m_pleft; // 文档原笔误 pleft应为 pLeft BinaryTreeNode *m_pRight; }并配了图示A 为 8-6-5-7-10-9-11B 为 10-11-9B 是 A 右子树的一部分。算法分两步先在 A 中找到值与 B 根相同的节点前序遍历再以该节点为根递归判断 B 是否被包含对应子树A 子树为空而 B 不空则失败。注意子结构与子树的语义差异——子结构只需部分匹配。8.3 二叉树翻转文档图示根 8、左 6 右 10、孙层 5 7 9 11 的树翻转后左右子树整体对调。方法论交换每个节点的左右子树签名void reverse(BinaryTreeNode *root);。递归写法三行交换左右指针 → 递归左 → 递归右与 4.5 的反转二叉树呢呼应。8.4 从上往下打印二叉树按层宽度优先打印签名void print_binary_level(BinaryTreeNode *root);。文档方法论辅助队列——根入队循环出队并打印同时把左右孩子入队即 BFS 层序遍历。注意逐层打印时可在每层结束插入分隔标记如 NULL以区分层。8.5 二叉搜索树的后序遍历序列输入一个整数数组判断它是否是某二叉搜索树的后序遍历结果签名bool is_post_order(BST *root, int *data, int length);。文档示例【5,7,6,9,11,10,8】是图中 BST根 8、左 6 带 5/7、右 10 带 9/11的后序遍历。方法论寻找规律——后序最后一个是根序列前段小于根的属于左子树中段大于根的属于右子树BST 性质若出现小于根却落在右段的元素则非法递归验证左右子树。注意空树与单节点视为合法重复元素的 BST 需要额外约定比较方向。8.6 二叉树中和为某一值的路径文档图示根 10、左 5带 5、7、右 12和为 22 的路径有两条10→5→7 与 10→12。签名void print_path(BinaryTree *root, int n);。方法论递归 栈——前序遍历累加把当前节点压入路径栈到达叶节点时若累计和等于目标则打印路径回溯时弹出栈顶。关键是路径必须到叶子还是任意节点即止需与面试官确认本题按文档示例为根到叶的完整路径。8.7 二叉搜索树转换为排序的双向链表只调整树中节点的指针指向不新建节点签名BST *transform(BST *root);。方法论递归、分解问题——中序遍历 BST 即有序序列把左子树转成链表后用其尾节点连接当前节点再处理右子树。仓库 bt1.c 给出了结构体与convertDoubleLinks的空壳是留给读者补全的练习typedef struct BSTreeNode{ int m_nValue; struct BSTreeNode *m_pLeft, *m_pRight; }BSTree; void convertDoubleLinks(BSTree *root){ /* 待补全 */ }补全思路递归函数返回转换后链表的头尾中序遍历时把当前节点接到左子链表的尾部m_pLeft指向前驱、m_pRight指向后继。8.8 二叉树的深度签名int tree_depth(BTree *root);。方法论递归——depth 1 max(depth(left), depth(right))空树返回 0。O(n)。延伸考点判断是否为平衡二叉树深度差不超过 1时为避免重复计算应让递归同时返回是否平衡标记而非对每个节点重新算深度。8.9 树中两个节点的最低公共祖先文档按树的形态给出三个递进场景对应三种解法二叉排序树利用大小关系——从根出发若两个节点都小于当前节点则向左都大于则向右否则当前节点即最低公共祖先非 BST 但有父节点指针转化为两条链表求第一个公共节点即 4.2 的解法既非 BST 也无父指针的普通树自顶向下判断每个子树是否同时包含两个节点或自底向上用后序遍历标记命中找到第一个左右子树分别包含两目标或自身为其中之一且子树包含另一个的节点。三个场景逐层递进是分析方法分解的典型演示。九、其他C 语言层面的经典题文档在最后列出 3 道纯语言题均无详细正文属于需要读者自行展开的知识点不能被继承的类经典技巧是把构造函数设为私有 用友元函数创建实例更稳妥的方案是利用虚继承基类为 final 语义或 C11 的final关键字。题目意在考察继承机制与构造/析构调用链的理解。实现 Singleton 模式需覆盖懒汉延迟初始化、饿汉静态实例、线程安全双检锁或局部静态变量、防拷贝删除拷贝构造与赋值等要点。赋值运算符函数考察拷贝控制——深拷贝、自赋值检查、释放旧资源、返回引用以支持链式赋值a b c。这三题在面试中常作为基本功快问快答建议结合 C 语言规范补充笔记仓库其余章节如 1 String、2 链表 等分类笔记也可按主题交叉复习。十、用本仓库高效备战的建议按题型分批刷数值与字符串第二节、第三节适合作为热身链表第四节与二叉树第八节建议配合画图分析数组与数列第五节覆盖了二分、双指针、动态规划、位运算四大高频范式。对照源码读实现仓库 codes 目录已给出约 10 个题目的可直接运行 C 实现one_appear_count_by_binary.c、Power.c、replce_blank.c、char_first_appear_once.c、revert_by_word.c、string_to_integer.c、fibonacci.c、print_continuous_sequence_sum.c、print_matrix.c、binary_search.c。阅读时请特别关注源码注释中自曝的缺陷——负指数、字符串转整数的边界、字符串字面量就地修改导致的 bus error——这些恰恰是文档开篇代码鲁棒性的最佳反面教材。带着鲁棒性清单自查每题提交前过一遍文档的检查表——边界条件n0/1、链表为空、K 越界、特殊输入NULL、空串、全空格、异常处理溢出、除零、只读内存。养成习惯后面试中主动补边界的分项会显著加分。关联复习本文题目与仓库 剑指offer/README.md、编程之美 及各大类的算法笔记如 堆与 Top-K、二分查找 所属专题互为补充可形成题目 → 范式 → 源码的闭环。文中各函数签名均以 原文档 为准个别明显笔误如缺右括号、Slbling、inroder已按 C 语法惯例指出仓库未收录实现的部分解法描述属于通用算法思路读者可结合自身代码验证。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐攻克《剑指Offer》从数组到二叉树的算法通关指南攻克《剑指Offer》从数组到二叉树的算法通关指南 开篇算法面试的痛点与解决方案 你是否在面试中遇到过这些困境面对数组去重问题无从下手二叉树遍历总是记混Learn-Algorithms 算法面试笔记矩阵与二维数组五类高频题的解法与源码解析Learn Algorithms 算法面试笔记矩阵与二维数组五类高频题的解法与源码解析 本篇文章以 6 矩阵.md 为核心骨架整理展开并以仓库源码 prin教程OpenVINO AI音频插件Audacity的终极AI音频处理指南OpenVINO AI音频插件Audacity的终极AI音频处理指南 想让你的Audacity音频编辑软件拥有AI超能力吗OpenVINO AI音频插件正是教程上一篇gtop与New Relic集成实现全栈应用性能监控的方案下一篇如何使用McFly快速构建React应用从入门到精通创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考