微博雪球力扣 CSDN 博客园 51CTO 账号“闻缺陷则喜何志丹”： C/C++/ VC QQ 群：2508429
闻缺陷则喜之算法册
--缺陷让我们成长
何志丹 魏家瑜
高效暴露问题才能更有效率的解决问题，这是本丛书命名为《闻缺陷则喜》的原因。此
书是我们的经历和积累，经历越和我们相近，此书的价值越大。我热情邀请大家共同完成此
丛书。以前知识供给不足，“教会徒弟饿死师傅”；现在知识爆炸，不但要尽善尽美，还要
宣传。有价值的内容很多，比如：工作需要但百度不到的东西。个人体会：写论文（书）不
难。买本好书，认真看一遍，吸收 1%。理论上看 100 本的体会就是一本书。 实际操作：10
本书反复看 6 遍，10 本书看 3 遍，10 本书看一遍。低配版：吸收博文精华，“积沙成塔”。
或者做操作视频，教是最好的学。
更多阅读与沟通：
最新版（包括源码）下载
https://pan.baidu.com/s/1wMsUK4hZpdttFzOK66n3mQ?pwd=x7a7 提取码 x7a7
微博：https://weibo.com/u/1700134511
CSDN 博客：https://blog.csdn.net/he_zhidan/
博客园：https://www.cnblogs.com/he-zhidan/Q
通讯方式：群：288
Q 群：C/C++/VC 2508429 C# 9993488
QQ:154168835
微信 he_zhidan：
微博雪球力扣 CSDN 博客园 51CTO 账号“闻缺陷则喜何志丹”： C/C++/ VC QQ 群：2508429
目录
闻缺陷则喜之算法册..............................................................................................1
视频算法 ..................................................................................................................3
1. 二分查找 .............................................................................................................................4
1.1. 基础 ....................................................................................................................................4
1.2. 习题 ....................................................................................................................................8
最短路径 ................................................................................................................11
1. 深度优先搜索(BFS)最短路径的原理和 C++实现 ...............................................................11
1.1. 时间复杂度 ......................................................................................................................11
1.2. 使用前提 ..........................................................................................................................11
1.3. 典型场景 ..........................................................................................................................11
1.4. 可理解性强的解法 ..........................................................................................................12
1.5. 核心代码 ..........................................................................................................................12
1.6. 测试样例 ..........................................................................................................................13
1.7. 滚动队列优化 ..................................................................................................................14
1.8. 一个队列就够了 ..............................................................................................................15
2. 01BFS 最短距离的原理和 C++实现 ...................................................................................15
2.1. 时间复杂度 ......................................................................................................................15
2.2. 使用前提 ..........................................................................................................................16
2.3. 典型场景 ..........................................................................................................................16
2.4. 解题思路 ..........................................................................................................................16
微博雪球力扣 CSDN 博客园 51CTO 账号“闻缺陷则喜何志丹”： C/C++/ VC QQ 群：2508429
2.5. 核心代码 ..........................................................................................................................16
2.6. 测试样例 ..........................................................................................................................17
2.7. 类似场景 ..........................................................................................................................18
2.8. 用双向队列优化 ..............................................................................................................18
3. 朴素迪氏最短单源路径 ....................................................................................................18
3.1. 时间复杂度 ......................................................................................................................18
3.2. 使用前提 ..........................................................................................................................19
4. 堆优化迪氏最短单源路径.................................................................................................19
4.1. 时间复杂度 ......................................................................................................................19
4.2. 使用前提 ..........................................................................................................................19
5. 存在负权边的单源最短路径 .............................................................................................19
6. 多源最短路径....................................................................................................................19
其它 ........................................................................................................................19
1.1. KMP...................................................................................................................................19
1.2. 让数组不相等的最小总代价 ..........................................................................................23
1.3. 美丽塔 ..............................................................................................................................26
1.4. 美丽塔单调栈优化 ..........................................................................................................30
定位用 ....................................................................................................................33
视频算法
本书 CSDN 课程：
算法 C++版-CSDN 程序员研修院
视频、源码下载：
https://pan.baidu.com/s/1wMsUK4hZpdttFzOK66n3mQ?pwd=x7a7 提取码 x7a7
先进入《 视频教程及配套源码》，再进入《C++算法》。
在线看视频：
https://www.bilibili.com/video/BV1nL411Q7DY/
微博雪球力扣 CSDN 博客园 51CTO 账号“闻缺陷则喜何志丹”： C/C++/ VC QQ 群：2508429
1. 二分查找
1.1. 基础
1.1.1.最简单的情况
a. 情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数，返回任意一个。
b. 原理
如果中间数和目标数相等，返回中间数索引。
如果中间数小于目标数，则目标数一定不在前半部分。
如果中间数大于目标数，则目标数一定不在后半部分。
假定数组区域是左闭右开区间，中间索引=（左索引+右索引)/2。
c. 测试数据
从 0 到 4 中找 1。
轮次
待查数据
中间数
第一轮
0 1 2 3 4
2
第二轮
0 1
1
从 1 到 5 中查找 4。
轮次
待查数据
中间数
第一轮
1 2 3 4 5
3
第二轮
4 5
5
第三轮
4
4
1.1.2.重复数据返回第一个
a. 情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数，返回第一个。
b. 原理
如果中间数小于目标数，则目标数一定不在前半部分。
微博雪球力扣 CSDN 博客园 51CTO 账号“闻缺陷则喜何志丹”： C/C++/ VC QQ 群：2508429
如果中间数大于目标数，则目标数一定不在后半部分。
如果中间数等于目标数，则目标数一定不在后半部分。由于左半部分必须包括中间数，
所以左开右闭区间。
c. 测试数据
从 1,2 中寻找 2。
轮次
待查数据
索引
中间数
第一轮
1 2
(-1,1]
1
第二轮
2
(0,1]
2
从 2,2,3 中寻找 2。
轮次
待查数据
索引
中间数
第一轮
2 2 3
(-1,2]
2
第二轮
2 2
(-1,1]
2
第三轮
2
(-1,0]
2
从 2,3,4 中寻找 2。
轮次
待查数据
索引
中间数
第一轮
2 3 4
(-1,2]
3
第二轮
2 3
(-1,1]
2
第三轮
2
(-1,0]
2
1.1.3.重复数据返回最后一个
a. 情况简述
数组已经按升序排好序。
假定要找的数一定存在。
如果存在重复的数，返回最后一个。
b. 原理
一，如果中间数小于目标数，则目标数一定不在左边、中间，可能在右边。
二，如果中间数大于目标数，则目标数一定不在右边、中间，可能在左边。
三，如果中间数等于目标数，则目标数一定不在左边，可能在中间、右边。
数据
左
中
右
左闭右开
0,1,2,3
0,1
2((0+4)/2)
3
0,1,2
0
1
2
0,1
0
1
左开右闭
0,1,2,3
0
1（(-1+3)/2）
2,3
0,1,2
0
1,2
