算法大爆炸 面试通关步步为营

杨峰，资深程序员，微信公众号“算法匠人”作者。多年来致力于算法与数学方法的研究，发表了大量有趣而经典的算法文章，擅长用生动的语言阐述算法的本质问题。著有畅销书《C语言**手册》《妙趣横生的算法（C语言版）》《程序员面试笔记 C/C++、算法、数据结构篇》《Java程序员面试笔记》《那些令人脑洞大开的数学》。

目 录 上篇 数据结构与算法基础 第 1 章 线性结构 ........................................................................................................... 2 1.1 数组 ........................................................................................................................ 2 1.1.1 数组的基本概念 ......................................................................................... 2 1.1.2 数组的定义 ................................................................................................. 3 1.1.3 数组的基本操作 ......................................................................................... 5 1.1.4 数组的性能分析 ....................................................................................... 11 1.1.5 案例分析 ................................................................................................... 12 1.2 链表 ...................................................................................................................... 19 1.2.1 链表的基本概念 ....................................................................................... 19 1.2.2 链表的定义 ............................................................................................... 20 1.2.3 链表的基本操作 ....................................................................................... 21 1.2.4 链表的性能分析 ....................................................................................... 27 1.2.5 不同形态的链表结构 ............................................................................... 28 1.2.6 案例分析 ................................................................................................... 29 1.3 栈 .......................................................................................................................... 38 1.3.1 栈的基本概念 ........................................................................................... 38 1.3.2 栈的定义 ................................................................................................... 38 1.3.3 栈的基本操作 ........................................................................................... 40 1.3.4 案例分析 ................................................................................................... 44 1.4 队列 ...................................................................................................................... 50 1.4.1 队列的基本概念 ....................................................................................... 50 1.4.2 队列的定义 ............................................................................................... 50VI � 1.4.3 队列的基本操作 ....................................................................................... 52 1.4.4 双端队列 ................................................................................................... 56 1.4.5 实战分析 ................................................................................................... 56 第 2 章 树结构 ............................................................................................................. 64 2.1 树的基本概念 ...................................................................................................... 64 2.2 二叉树 .................................................................................................................. 65 2.3 二叉树的遍历 ...................................................................................................... 68 2.4 创建二叉树 .......................................................................................................... 71 2.5 二叉排序树与 AVL 树 ......................................................................................... 76 2.6 案例分析 .............................................................................................................. 81 第 3 章 图结构 ............................................................................................................. 89 3.1 图的基本概念 ...................................................................................................... 89 3.2 图的存储形式 ...................................................................................................... 92 3.3 邻接表的实现 ...................................................................................................... 94 3.4 图的遍历 .............................................................................................................. 97 3.5 案例分析 ............................................................................................................ 103 第 4 章 排序与查找 .................................................................................................... 109 4.1 直接插入排序 .................................................................................................... 109 4.2 冒泡排序 ............................................................................................................ 112 4.3 简单选择排序 .................................................................................................... 114 4.4 快速排序 ............................................................................................................ 117 4.5 希尔排序 ............................................................................................................ 120 4.6 堆排序 ................................................................................................................ 122 4.7 各种排序算法的比较 ........................................................................................ 129 4.8 折半查找算法 .................................................................................................... 130 4.9 案例分析 ............................................................................................................ 132 第 5 章 穷举法 ........................................................................................................... 139 5.1 穷举法的基本思想 ............................................................................................ 139 5.2 案例分析 ............................................................................................................ 142 第 6 章 递归算法 ....................................................................................................... 149 6.1 递归算法的基本思想 ........................................................................................ 149 6.2 案例分析 ............................................................................................................ 150 第 7 章 贪心算法 ....................................................................................................... 159 7.1 贪心算法的基本思想 ........................................................................................ 159 7.2 案例分析 ............................................................................................................ 160 第 8 章 动态规划 ....................................................................................................... 168 8.1 动态规划算法的基本思想 ................................................................................ 168 8.2 案例分析 ............................................................................................................ 173 第 9 章 回溯法 ........................................................................................................... 185 9.1 回溯法的基本思想 ............................................................................................ 185 9.2 案例分析 ............................................................................................................ 188 下篇 大厂经典面试题详解 第 10 章 数组和字符串类面试题 ................................................................................ 200 10.1 数组元素的奇偶重排 ...................................................................................... 200 10.2 不改变顺序的数组元素奇偶重排................................................................... 203 10.3 有序数组的两数之和 ...................................................................................... 206 10.4 三数之和 .......................................................................................................... 209 10.5 两个有序数组的交集 ...................................................................................... 214 11.6 最长公共前缀问题........................................................................................... 219 10.7 最长公共子串问题 .......................................................................................... 221 10.8 长度最小的连续子数组 .................................................................................. 224 10.9 最长无重复子串 .............................................................................................. 232 10.10 删除字符数组中特定字符 ............................................................................ 236 10.11 最短连续子数组问题 ..................................................................................... 240 10.12 字符数组的内容重排 .................................................................................... 242 10.13 字符串数组类面试题解题技巧 .................................................................... 246 第 11 章 线性结构类面试题 ....................................................................................... 249 11.1 约瑟夫环 .......................................................................................................... 249 11.2 单链表的逆置 .................................................................................................. 253 11.3 判断链表中是否存在循环结构 ....................................................................... 256 11.4 判断两个链表是否相交 ................................................................................... 260 11.5 判断回文链表 .................................................................................................. 265 11.6 最小栈问题 ...................................................................................................... 269 11.7 每日温度 .......................................................................................................... 275 11.8 LRU 缓存的设计.............................................................................................. 281 11.9 线性结构类面试题解题技巧 ........................................................................... 291 第 12 章 二叉树类面试题 ........................................................................................... 293 12.1 二叉树的判定 .......................................................................................... 293 12.2 二叉树节点的距离 .................................................................................. 298 12.3 打印二叉树中的重复子树 .............................................................................. 302 12.4 还原二叉树 ...................................................................................................... 307 12.5 二叉树类面试题解题技巧 .............................................................................. 312 第 13 章 递归和动态规划系列面试题 ......................................................................... 315 13.1 分解质因数 ...................................................................................................... 315 13.2 拨号盘字母组合 .............................................................................................. 317 13.3 组合的总和 ...................................................................................................... 322 13.4 在大矩阵中找 k ............................................................................................... 327 13.5 跳跃游戏 .......................................................................................................... 332 13.6 机器人的最小路径长度 .................................................................................. 336 13.7 聪明的侦探 ...................................................................................................... 342 第 14 章 穷举法和回溯法系列面试题 ......................................................................... 347 14.1 数组元素之差的最小值 .................................................................................. 347 14.2 数的分组问题 .................................................................................................. 350 14.3 碰面地点 .............................................................................................. 354 14.4 多点共线问题 .................................................................................................. 360 14.5 复原 IP 地址 ..................................................................................................... 369 14.6 矩阵中的相邻数 .............................................................................................. 372 14.7 被包围的区域 .................................................................................................. 377 第 15 章 其他类型算法面试题 .................................................................................... 382 15.1 相差多少天 ...................................................................................................... 382 15.2 万年历 .............................................................................................................. 386 15.3 1 的数量 ........................................................................................................... 389 15.4 找出人群中的“单身者” ...................................................................... 392 15.5 找出人群中 3 个“单身者”中的任意一个 ................................................... 393 15.6 空瓶换汽水问题 .............................................................................................. 397 15.7 渔夫捕鱼问题 .................................................................................................. 399 15.8 亲密数 .............................................................................................................. 401 15.9 筛选出 100 以内的素数 .................................................................................. 403 15.10 寻找丑数 ........................................................................................................ 405 15.11 组成最小的数 ................................................................................................ 410 15.12 数字翻译器 .................................................................................................... 413 15.13 计算 π 值 ........................................................................................................ 416