本书旨在帮助读者筑牢数据结构和算法的基础，提升职场竞争力。本书代码采用 Java 语言编写，分为上、下两篇，共 15 章。其中，第 1~9 章为上篇，讲解数据结构和算法基础，为读者全面梳理基本知识，内容涵盖线性结构、树结构、图结构、排序与查找、穷举法、递归算法、贪心算法、动态规划、回溯法；第 10~15 章为下篇，收集了 50 多道经典且有趣的大厂面试真题，针对每道题都给出了详细的分析和解答，帮助读者全面提升解决实际问题的能力，同时为读者准备笔试、面试提供帮助。 本书坚持"夯实基础、注重实践、举一反三”的理念，内容丰富翔实、妙趣横生，讲解深入浅出、清晰到位。希望能够陪伴读者在轻松愉快的氛围中学习。 本书既可作为计算机相关专业的学生以及算法爱好者学习用书，也可作为应届毕业生及社招人员笔试、面试的求职参考书，还可作为培训机构的教材。

前 言 在信息科技迅猛发展的今天，互联网、5G、人工智能等已成为炙手可热的行业，这些行业凭借其光明的发展前景和令人羡慕的薪资水平，吸引着一届又一届的年轻人，而进入这些行业的门槛也随之“水涨船高”。记得在我毕业找工作时，面试题目比今天容易很多，考查的内容基本就是 Java 或 C++的语法知识和基础的编程题，最多有一两道算法题“压轴”，用以区分面试者的水平。但是现在大厂的面试题更侧重于数据结构和算法，认为这样更能考查面试者的综合水平，包括基本的编程能力、计算机逻辑思维、数学功底，以及对数据结构和算法本身的理解。所以，学好数据结构和算法是通往大厂、获取高薪的必由之路，大家应该认真对待。 如何才能学好数据结构和算法呢？我认为大道至简：只要做到夯实基础、注重实践、举一反三，就一定能学通弄懂。因此在写作本书的过程中，我力求将这三点贯穿始终，努力为广大读者呈现一本适合自学和自我提高的算法书。 夯实基础是指要对数据结构和算法最基础的知识点有非常深刻的理解和认识。这就像盖大楼，地基必须夯实筑牢，否则盖出的大楼不会稳固。这似乎不言自明，但是往往容易被大家忽视。现在人们生活节奏加快，速成、抄近道的想法普遍存在，很多人希望通过背几个模板、学几个套路就把数据结构和算法搞懂，这其实是不太可能的。任何知识体系的构建都有其客观规律，只有扎扎实实地把这些基础的知识点学通透、弄明白，才能稳扎稳打、步步为营。因此我在本书的上篇中用了相当大的篇幅为读者梳理和总结数据结构和算法的基础知识，目的就是希望读者在刷题之前能够温习和巩固这些最基础、最重要的内容。只有这样，我们构建的知识体系大厦才能稳固坚硬，不但有利于应聘职位，对于大家今后从事开发和研究工作也有很多好处。 除了夯实基础，注重实践也是学好数据结构和算法的必要条件。学习数据结构和算法的最终目标是解决实际问题，所以必须进行大量的实践和练习，不断加深理解，进而提高水平。我在本书中为读者整理和分析了大量的题目，旨在帮助读者通过实践和练习提高自身的水平。 大家在刷题的同时，还应该清楚地认识到：题目是无穷无尽的，试图穷举出每一个题目是不可能的。我们如何在有限的时间内高效刷题，覆盖尽可能多的知识点呢？答案就是举一反三。对于一个问题，我们不应当只局限于一个思路、一种解法，而是应当尽可能多地用不同的方法求解。本书中的题目分析就充分体现出举一反三的特点，很多题目并不拘泥于单一解法，而是采取由易到难、由低级到高级的方式给出多种解法，这样读者就可以通过一个问题复习多个知 识点，学习效率也会显著提高。 以上是我的经验总结，也是创作本书的核心理念。除此之外，与同类图书相比，本书还有以下亮点。 结构清晰，内容全面 本书分为上、下两篇。上篇主要介绍数据结构和算法基础知识，为读者梳理数据结构的基础知识以及常用的算法思想，方便读者复习和巩固已有知识、夯实理论基础，为后续刷题打下基础。下篇主要介绍经典的大厂面试题，通过妙趣横生的数据结构和算法题目帮助读者巩固基础、开阔思路，提高职场竞争力。 实例丰富，讲解到位 注重实践是本书的创作理念和主要特色，书中包含大量编程实例，从上篇的案例分析到下篇的大厂面试题，每个题目都经过精挑细选，很值得读者学习研究。同时每个题目都使用星号（★）标注其难度，从难度最小的一星（★）到难度最大的四星（★★★★），一目了然。除此之外，讲解到位是本书的另一大特点，不采用“贴代码”式的讲解，而是将每个题目的思考过程清晰地展示给读者，力求深入浅出、把问题讲清讲透，使读者在看懂题目的同时学到思考问题的正确方法，从而在遇到类似问题时能够举一反三、触类旁通。 题目经典，妙趣横生 本书中选取的题目多为经典的数据结构和算法题目，不但具有明确的针对性，也经常被拿来当作大厂的笔试或面试题目，因此具有很高的学习价值和实用价值。除此之外，本书中的题目还兼具趣味性，力求让读者对数据结构和算法产生兴趣，进而不再畏惧难题，愿意思考和解决它们。 读者可以关注我的微信公众号“算法匠人”并在“匠人作品”中下载全书源代码资源。让我们共同切磋，一起提高。 由于本人水平有限，书中难免存在不足和纰漏之处，欢迎广大读者批评指正。 杨峰 2022 年 7 月

目 录 上篇 数据结构与算法基础 第 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