剑指Offer（专项突破版）：数据结构与算法名企面试题精讲-何海涛
- 书名： 剑指Offer（专项突破版）：数据结构与算法名企面试题精讲
- 作者： 何海涛
- 简介： 本书全面、系统地总结了在准备程序员面试过程中必备的数据结构与算法。本书首先详细讨论整数、数组、链表、字符串、哈希表、栈、队列、二叉树、堆和前缀树等常用的数据结构，然后深入讨论二分查找、排序、回溯法、动态规划和图搜索等算法。除了介绍相应的基础知识，每章还通过大量的高频面试题系统地总结了各种数据结构与算法的应用场景及解题技巧。本书适合所有正在准备面试的程序员阅读。无论是计算机相关专业的应届毕业生还是初入职场的程序员，本书总结的数据结构和算法的基础知识及解题经验都不仅可以帮助他们提高准备面试的效率，还可以增加他们通过面试的成功率。
- 出版时间 2021-07-01 00:00:00
- ISBN： 9787121415203
- 分类： 计算机-编程设计
- 出版社： 电子工业出版社
高亮划线
封面
版权信息
内容简介
前言
第1章 整数
1.2 二进制
- 📌 因为位运算只有6种：非、与、或、异或、左移和右移。 ^6-678-703
- ⏱ 2024-03-04 18:43:21
1.3 本章小结
第2章 数组
2.2 双指针
2.3 累加数组数字求子数组之和
2.4 本章小结
第3章 字符串
3.2 双指针
3.3 回文字符串
3.4 本章小结
第4章 链表
4.2 哨兵节点
4.3 双指针
4.4 反转链表
4.5 双向链表和循环链表
4.6 本章小结
第5章 哈希表
5.2 哈希表的设计
5.3 哈希表的应用
5.4 本章小结
第6章 栈
6.2 栈的应用
6.3 本章小结
第7章 队列
7.2 队列的应用
7.3 二叉树的广度优先搜索
- 📌 由于队列的“先入先出”特性，二叉树的某一层节点按照从左到右的顺序插入队列中，因此这些节点一定会按照从左到右的顺序遍历到。如果用广度优先的顺序遍历二叉树，那么它的下一层节点也是按照从左到右的顺序添加到队列中的。因此，很容易知道每层最左边或最右边的节点，或者每层的最大值、最小值等。如果关于二叉树的面试题提到层这个概念，那么基本上可以确定该题目需要运用广度优先搜索。 ^31-1648-1829
- ⏱ 2024-03-20 21:25:35
7.4 本章小结
第8章 树
8.2 二叉树的深度优先搜索
8.3 二叉搜索树
8.4 TreeSet和TreeMap的应用
8.5 本章小结
第9章 堆
9.2 堆的应用
9.3 本章小结
第10章 前缀树
10.2 前缀树的应用
10.3 本章小结
第11章 二分查找
11.2 在排序数组中二分查找
11.3 在数值范围内二分查找
11.4 本章小结
第12章 排序
12.2 计数排序
12.3 快速排序
12.4 归并排序
12.5 本章小结
第13章 回溯法
-
📌 回溯法可以看作蛮力法的升级版，它在解决问题时的每一步都尝试所有可能的选项，最终找出所有可行的解决方案。回溯法非常适合解决由多个步骤组成的问题，并且每个步骤都有多个选项。在某一步选择了其中一个选项之后，就进入下一步，然后会面临新的选项。就这样重复选择，直至到达最终的状态。 ^53-497-632
- ⏱ 2024-03-15 08:08:59
-
📌 在采用回溯法解决问题时如果到达树形结构的叶节点，就找到了问题的一个解。如果希望找到更多的解，那么还可以回溯到它的父节点再尝试父节点其他的选项。如果父节点所有可能的选项都已经试过，那么再回溯到父节点的父节点以尝试它的其他选项，这样逐层回溯到树的根节点。因此，采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行深度优先遍历。通常，回溯法的深度优先遍历用递归代码实现。 ^53-1431-1617
- ⏱ 2024-03-15 08:15:44
-
📌 由于回溯法是在所有选项形成的树上进行深度优先遍历，如果解决问题的步骤较多或每个步骤都面临多个选项，那么遍历整棵树将需要较多的时间。如果明确知道某些子树没有必要遍历，那么在遍历的时候应该避开这些子树以优化效率。通常将使用回溯法时避免遍历不必要的子树的方法称为剪枝。 ^53-1952-2083
- ⏱ 2024-03-15 08:17:09
13.2 集合的组合、排列
13.3 使用回溯法解决其他类型的问题
13.4 本章小结
第14章 动态规划
- 📌 如果题目要求列举出所有的解，那么很有可能需要用回溯法解决。如果题目是求一个问题的最优解（通常是求最大值或最小值），或者求问题的解的数目（或判断问题是否存在解），那么这个题目有可能适合运用动态规划。 ^57-729-827
- ⏱ 2024-03-15 08:06:57
14.2 单序列问题
14.3 双序列问题
14.4 矩阵路径问题
14.5 背包问题
14.6 本章小结
第15章 图
15.2 图的搜索
-
📌 广度优先搜索能够保证在无权图中从某个起始节点出发用最短的距离到达目标节点 ^64-1484-1520
- ⏱ 2024-03-20 08:14:58
-
📌 深度优先搜索从一个节点到达另一个节点并不能保证一定沿着最短路径。 ^64-1974-2006
- ⏱ 2024-03-20 08:17:18
-
📌 如果面试题要求在无权图中找出两个节点之间的最短距离，那么广度优先搜索可能是更合适的算法。如果面试题要求找出符合条件的路径，那么深度优先搜索可能是更合适的算法。 ^64-2209-2288
- ⏱ 2024-03-20 08:18:09
-
📌 避免死循环的办法是记录已经搜索过的节点，在访问一个节点之前先判断该节点之前是否已经访问过，如果之前访问过那么这次就略过不再重复访问。 ^64-2741-2807
- ⏱ 2024-03-20 08:19:34
-
📌 也可以用深度优先搜索来搜索图中的所有节点并进行着色。深度优先搜索可以用递归代码实现。函数setColor将节点i的颜色设为color。如果该节点在此之前已经着色，并且它的颜色不是color，那么意味着不能按照二分图的规则对图中的节点进行着色，直接返回false。如果此时节点i还没有着色，则将它的颜色设为color，然后给与它相邻的节点涂上颜色1-color。给相邻的节点着色与给节点i着色是相同的问题，可以递归调用函数setColor解决。 ^64-8835
- ⏱ 2024-03-20 20:07:45