查看: 3741|回复: 1

❤️两万字《算法 + 数据结构》全套路线❤️（建议收藏）

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2021-7-8 15:06 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

❤️两万字《算法 + 数据结构》全套路线❤️（建议收藏）

前言
所谓活到老，学到老，虽然我感觉自己已经学了很多算法了，但是昨天熬夜整理完以后发现，自己还是个弟弟，实在忍不住了，打算把算法学习路线发出来，我把整个算法学习的阶段总结成了五个步骤，分别为：基础语法学习（重要）、语法配套练习、数据结构、算法入门、算法进阶。本文梳理了这五个大项的思维导图，在下文会有详细介绍。
希望各位能够找到自己的定位，通过自己的努力在算法这条路上越走越远。
刚开始切勿心浮气躁，千万不要给自己立 flag，说一定要把这么多东西都学会。就算你的精力旺盛，日夜操劳，时间也是有限的。所以，首先是明确我们要做什么，然后制定好一个合理的目标，再一点一点将要学习的内容逐步付诸实践才是最重要的。
每日一篇C语言打卡，目前更新到：光天化日学C语言（20）- 赋值运算符与赋值表达式 | 让代码变得更加简介（建议收藏）。

图片较大，文章中有拆解，需要原图可以留言找我要哈
1、基础语法学习
算法是以编程语言为基础的，所以选择一门编程语言来学习是必须的。
因为作者本身是C/C++技术栈的，所以就拿C语言来举例子吧。如果是 Java、Python 技术栈，可以跳过 C语言相关的内容。这一小节，先给出学习路线图，然后我再来讲，每部分应该如何去学。

1）HelloWorld
无论是 Java、Python、C/C++，想要上手一门语言，第一步一定是 HelloWorld，先不要急着去配环境。如果环境配了几个小时，可能一开始的雄心壮志就被配环境的过程消磨殆尽，更加不要谈日后的丰功伟业了。
2）让自己产生兴趣
所以，我们需要让这件事情从一开始就变得有趣，这样才能坚持下去。比如找一个相对较为有趣的教程，这里我会推荐这个：《光天化日学C语言》。听名字就比较搞笑，可能作者本身也不是什么正经人，哈哈哈！虽然不能作为一个严谨的教程去学，起码可以对搞笑的内容先产生兴趣。从而对于语言本身有学习下去的动力。
刚才提到的这个系列，可以先收藏起来。回头再去看，它讲述的是对白式的 C语言教学，从最简单的输出 HelloWorld 这个字符串开始讲起，逐渐让读者产生对C语言的兴趣。这个系列的作者是前 WorldFinal 退役选手，一直致力于将困难的问题讲明白。我看了他的大部分教程，基本都能一遍看懂。算了，不装了，摊牌了，因为我就是这个作者。
3）目录是精髓
然后，我们大致看下你选择的教程的前几个章节，那些标题是否有你认知以外的名词出现，比如以这个思维导图为例，前几个章节为：
1、第一个C语言程序
2、搭建本地环境
3、变量
4、标准输出
5、标准输入
6、进制转换入门
7、ASCII字符
8、常量

如果你觉得这些名词中有 3 / 4 以上是没有什么概念的。那么，可能需要补齐一些数学、计算机方面的基础知识。反之，我们就可以继续下一步了。
4）习惯思考并爱上它
只要对一件事情养成习惯以后，你就会发现，再难的事情，都只是一点一点积累的过程。重要的是，每天学习的过程一定要吃透，养成主动思考的好习惯。因为，越到后面肯定是越难的，如果前期不养成习惯，后面很可能心有余而力不足。
就像刷题，一旦不会做就去找解题报告，最后就养成了看解题报告才会做题的习惯。当然这也是一种习惯，只不过不是一种好习惯罢了。
5）实践是检验真理的唯一标准
光看教程肯定是不行的，写代码肯定还是要动手的，因为有些语法你看一遍，必定忘记。但是写了几遍，永世难忘。这或许就是写代码的魅力所在吧。
所以，记得多写代码实践哟 (＾Ｕ＾)ノ~ＹＯ
6）坚持其实并没有那么难
每天把教程上的内容，自己在键盘上敲一遍，坚持一天，两天，三天。你会发现，第四天就变成了习惯。所以坚持就是今天做了这件事情，明天继续做。
7）适当给予正反馈
然而，就算再有趣的教程，看多了都会乏味，这是人性决定的，你我都逃不了。能够让你坚持下去的只有你自己，这时候，适当给予自己一些正反馈就显得尤为重要。比如，可以用一张表格将自己的学习计划记录下来，然后每天都去分析一下自己的数据。
当然，你也可以和我一样，创建一个博客，然后每天更新博文，就算没有内容，也坚持日更，久而久之，你会发现，下笔如有神，键盘任我行！更新的内容，可以是自己的学习笔记，心路历程等等。
看着每天的粉丝量呈指数级增长，这是全网对你的认可，应该没有什么会是比这个更好的正反馈了。
8）学习需要有仪式感
那么，至此，不知道屏幕前的你感想如何，反正正在打字的我已经激情澎湃了。已经全然忘记这一章是要讲C语言基础的了！
介于篇幅，我会把C语言基础的内容，放在这个专栏《光天化日学C语言》里面去讲，一天更新一篇，对啊，既然说了要坚持，要养成习惯，我当然也要做到啦~如果你学到了哪一章，可以在评论区评论 “打卡” ，也算是一种全网见证嘛！
我也很希望大家的学习速度能够超越我的更新速度。
2、语法配套练习
学习的过程中，做题当然也是免不了的，还是应征那句话：实践是检验真理的唯一标准。
而这里的题库，是我花了大量时间，搜罗了网上各大C语言教程里的例题，总结出来的思维导图，可以先大致看一眼：

从数学基础、输入输出、数据类型、循环、数组、指针、函数、位运算、结构体、排序等几个方面，总结出的具有概括性的例题 100 道《C语言入门100例》，目前还在更新中。
这里可以列举几个例子：
1、例题1：交换变量的值
一、题目描述
循环输入，每输入两个数 a aa 和 b bb，交换两者的值后输出 a aa 和 b bb。当没有任何输入时，结束程序。

二、解题思路
难度：🔴⚪⚪⚪⚪

这个题的核心是考察如何交换两个变量的值，不像 python，我们可以直接写出下面这样的代码就实现了变量的交换。
a, b = b, a
1
在C语言里，这个语法是错误的。
我们可以这么理解，你有两个杯子 a aa 和 b bb，两个杯子里都盛满了水，现在想把两个杯子里的水交换一下，那么第一个想到的方法是什么？
当然是再找来一个临时杯子：
1）先把 a aa 杯子的水倒进这个临时的杯子里；
2）再把 b bb 杯子的水倒进 a aa 杯子里；
3）最后把临时杯子里的水倒进 b bb 杯子；

这种就是临时变量法，那么当然，还有很多很多的方法，接下来就让我们来见识一下吧。

三、代码详解
1、正确解法1：引入临时变量
#include <stdio.h>
int main() {
int a, b, tmp;
while (scanf("%d %d", &a, &b) != EOF) {
      tmp = a; // (1)
      a = b;    // (2)
      b = tmp; // (3)
      printf("%d %d\n", a, b);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
( 1 ) (1)(1) tmp = a;表示把 a aa 杯子的水倒进这个临时的杯子里；
( 2 ) (2)(2) a = b;表示把 b bb 杯子的水倒进 a aa 杯子里；
( 3 ) (3)(3) b = tmp;表示把临时杯子里的水倒进 b bb 杯子里；
这三步，就实现了变量 a aa 和 b bb 的交换。
2、正确解法2：引入算术运算
#include <stdio.h>
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
      a = a + b; // (1)
      b = a - b; // (2)
      a = a - b; // (3)
      printf("%d %d\n", a, b);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
( 1 ) (1)(1) a = a + b;执行完毕后，现在最新的a的值变成原先的a + b的值；
( 2 ) (2)(2) b = a - b;执行完毕后，相当于b的值变成了a + b - b，即原先a的值；
( 3 ) (3)(3) a = a - b;执行完毕后，相当于a的值变成了a + b - a，即原先b的值；
从而实现了变量a和b的交换。
3、正确解法3：引入异或运算
首先，介绍一下C语言中的^符号，代表的是异或。
二进制的异或，就是两个数转换成二进制表示后，按照位进行以下运算：
左操作数右操作数异或结果
0 0 0
1 1 0
0 1 1
1 0 1
也就是对于 0 和 1，相同的数异或为 0，不同的数异或为 1。
这样就有了三个比较清晰的性质：
1）两个相同的十进制数异或的结果一定位零。
2）任何一个数和 0 的异或结果一定是它本身。
3）异或运算满足结合律和交换律。
#include <stdio.h>
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
      a = a ^ b; // (1)
      b = a ^ b; // (2)
      a = a ^ b; // (3)
      printf("%d %d\n", a, b);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
我们直接来看 ( 1 ) (1)(1) 和 ( 2 ) (2)(2) 这两句话，相当于b等于a ^ b ^ b，根据异或的几个性质，我们知道，这时候的b的值已经变成原先a的值了。
而再来看最后一句话，相当于a等于a ^ b ^ a，还是根据异或的几个性质，这时候，a的值已经变成了原先b的值。
从而实现了变量a和b的交换。

4、正确解法4：奇淫技巧
当然，由于这个题目问的是交换变量后的输出，所以它是没办法知道我程序中是否真的进行了交换，所以可以干一些神奇的事情。比如这么写：
#include <stdio.h>
int main() {
int a, b;
while (scanf("%d %d", &a, &b) != EOF) {
      printf("%d %d\n", b, a);
}
return 0;
}
1
2
3
4
5
6
7
8
你学废了吗 🤣？
2、例题2：整数溢出
一、题目描述
先输入一个 t ( t ≤ 100 ) t (t \le 100)t(t≤100)，然后输入 t tt 组数据。每组输入为 4 个正整数 a , b , c , d ( 0 ≤ a , b , c , d ≤ 2 62 ) a,b,c,d(0 \le a,b,c,d \le 2^{62})a,b,c,d(0≤a,b,c,d≤2
62
)，输出 a + b + c + d a+b+c+da+b+c+d 的值。

二、解题思路
难度：🔴🔴⚪⚪⚪

这个问题考察的是对补码的理解。
仔细观察题目给出的四个数的范围：[ 0 , 2 62 ] [0, 2^{62}][0,2
62
]，这四个数加起来的和最大值为 2 64 2^{64}2
64
。而C语言中，long long的最大值为：2 63 − 1 2^{63}-12
63
−1，就算是unsigned long long，最大值也只有2 64 − 1 2^{64}-12
64
−1。
但是我们发现，只有当四个数都取得最大值 2 62 2^{62}2
62
  时，结果才为 2 64 2^{64}2
64
，所以可以对这一种情况进行特殊判断，具体参考代码详解。
三、代码详解
#include <stdio.h>
typedef unsigned long long ull;                         // (1)
const ull MAX = (((ull)1)<<62);                         // (2)

int main() {
int t;
ull a, b, c, d;
scanf("%d", &t);
while (t--) {
scanf("%llu %llu %llu %llu", &a, &b, &c, &d);    // (3)
if (a == MAX && b == MAX && c == MAX && d == MAX) // (4)
printf("18446744073709551616\n");          // (5)
else
printf("%llu\n", a + b + c + d);             // (6)
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
( 1 ) (1)(1) 由于这题数据量较大，所有数据都需要用64位无符号整型。ull作为unsigned long long的别名；
( 2 ) (2)(2) 用常量MAX表示 2 62 2^{62}2
62
，这里采用左移运算符直接实现 2 22 是幂运算；
数学 C语言
2 n 2^n2
n
1<<n
需要注意的是，由于 1 是int类型，所以需要对 1 进行强制转换。(ull)1等价于(unsigned long long)1；
( 3 ) (3)(3) %llu是无符号64位整型的输入方式；
( 4 ) (4)(4) 这里是对所有数都等于最大值的特殊判断，&&运算符的优先级低于==，所以这里不加括号也没事；
( 5 ) (5)(5) 由于 2 64 2^{64}2
64
  是无法用数字的形式输出的，所以我们提前计算机算好以后，用字符串的形式进行输出；
( 6 ) (6)(6) 其它情况都在 [ 0 , 2 64 − 1 ] [0, 2^{64}-1][0,2
64
−1] 范围内，直接相加输出即可。
由于这个专栏是付费专栏，可能对学生党不是很友好，所以作者经过再三思考，打算放出 300 张一折优惠券，先到先得。只要拿这个图片来找作者即可享受，仅限前 300 名。
为了适当提高一定门槛，你至少需要学会如何下载图片或者截图并且发送到微信里 🤣。

3、数据结构
《C语言入门100例》上的例题，如果能理解前面 25 道，那基本C语言的学习就可以告一段落了，接下来就要开始我们的数据结构的学习了。
1、什么是数据结构
你可能听说过数组、链表、队列、栈、堆、二叉树、图，没错，这些都是数据结构，但是你要问我什么是数据结构，我突然就一脸懵逼了。
如果一定要给出一个官方的解释，那么它就是：
计算机存储、组织数据的方式。相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。往往同高效的检索算法和索引技术有关。

是不是还不如说它是堆，是栈，是队列呢？
是这样的，我们学习的过程中，跳过一些不必要的概念，能够节省我们更多的时间，从而达到更好的效果，当你还在理解数据结构是什么的时候，可能人家已经知道了栈有哪些操作了。
2、数据结构和算法的关系
很多同学搞不明白，数据结构与算法有哪些千丝万缕的关系？甚至有些同学以为算法里本身就包含了数据结构。
数据结构主要讲解数据的组织形式，比如链表，堆，栈，队列。
而算法，则注重的是思想，比如链表的元素怎么插入、删除、查找？堆的元素怎么弹出来的？栈为什么是先进后出？队列又为什么是先进先出？
讲得直白一点，数据结构是有实体的，算法是虚拟的；数据结构是物质上的，算法是精神上的。当然，物质和精神缺一不可。
3、数据结构概览
周末花了一个下午整理的思维导图，数据结构：

常用的一些数据结构，各自有各自的优缺点，总结如下：
a、数组
内存结构：内存空间连续
实现难度：简单
下标访问：支持
分类：静态数组、动态数组
插入时间复杂度：O ( n ) O(n)O(n)
查找时间复杂度：O ( n ) O(n)O(n)
删除时间复杂度：O ( n ) O(n)O(n)

b、字符串
内存结构：内存空间连续，类似字符数组
实现难度：简单，一般系统会提供一些方便的字符串操作函数
下标访问：支持
插入时间复杂度：O ( n ) O(n)O(n)
查找时间复杂度：O ( n ) O(n)O(n)
删除时间复杂度：O ( n ) O(n)O(n)

c、链表
内存结构：内存空间连续不连续，看具体实现
实现难度：一般
下标访问：不支持
分类：单向链表、双向链表、循环链表、DancingLinks
插入时间复杂度：O ( 1 ) O(1)O(1)
查找时间复杂度：O ( n ) O(n)O(n)
删除时间复杂度：O ( 1 ) O(1)O(1)

d、哈希表
内存结构：哈希表本身连续，但是衍生出来的结点逻辑上不连续
实现难度：一般
下标访问：不支持
分类：正数哈希、字符串哈希、滚动哈希
插入时间复杂度：O ( 1 ) O(1)O(1)
查找时间复杂度：O ( 1 ) O(1)O(1)
删除时间复杂度：O ( 1 ) O(1)O(1)

e、队列
内存结构：看用数组实现，还是链表实现
实现难度：一般
下标访问：不支持
分类：FIFO、单调队列、双端队列
插入时间复杂度：O ( 1 ) O(1)O(1)
查找时间复杂度：理论上不支持
删除时间复杂度：O ( 1 ) O(1)O(1)

f、栈
内存结构：看用数组实现，还是链表实现
实现难度：一般
下标访问：不支持
分类：FILO、单调栈
插入时间复杂度：O ( 1 ) O(1)O(1)
查找时间复杂度：理论上不支持
删除时间复杂度：O ( 1 ) O(1)O(1)

g、树
内存结构：内存结构一般不连续，但是有时候实现的时候，为了方便，一般是物理连续，逻辑不连续
实现难度：较难
下标访问：不支持
分类：二叉树和多叉树
插入时间复杂度：看情况而定
查找时间复杂度：理论上 O ( l o g 2 n ) O(log_2n)O(log
2

n)
删除时间复杂度：看情况而定

1、二叉树
二叉树的种类较多，比如：二叉搜索树、平衡树。平衡树又可以分为 AVL 树、红黑树、线段树、堆。最平衡的树莫过于满二叉树了。
其中，堆也是一种二叉树，也就是我们常说的优先队列。
2、多叉树
B树和B+树是多叉树，当然我们平时学到的并查集其实也是个多叉树，更加严谨一点，应该称之为森林。
h、图
内存结构：不一定
实现难度：难
下标访问：不支持
分类：有向图、无向图
插入时间复杂度：根据算法而定
查找时间复杂度：根据算法而定
删除时间复杂度：根据算法而定

1、图的概念
在讲解最短路问题之前，首先需要介绍一下计算机中图（图论）的概念，如下：
图 G GG 是一个有序二元组 ( V , E ) (V,E)(V,E)，其中 V VV 称为顶点集合，E EE 称为边集合，E EE 与 V VV 不相交。顶点集合的元素被称为顶点，边集合的元素被称为边。
对于无权图，边由二元组 ( u , v ) (u,v)(u,v) 表示，其中 u , v ∈ V u, v \in Vu,v∈V。对于带权图，边由三元组 ( u , v , w ) (u,v, w)(u,v,w) 表示，其中 u , v ∈ V u, v \in Vu,v∈V，w ww 为权值，可以是任意类型。
图分为有向图和无向图，对于有向图， ( u , v ) (u, v)(u,v) 表示的是从顶点 u uu 到顶点 v vv 的边，即 u → v u \to vu→v；对于无向图，( u , v ) (u, v)(u,v) 可以理解成两条边，一条是从顶点 u uu 到顶点 v vv 的边，即 u → v u \to vu→v，另一条是从顶点 v vv 到顶点 u uu 的边，即 v → u v \to uv→u；
2、图的存储
对于图的存储，程序实现上也有多种方案，根据不同情况采用不同的方案。接下来以图二-3-1所表示的图为例，讲解四种存储图的方案。

1）邻接矩阵
邻接矩阵是直接利用一个二维数组对边的关系进行存储，矩阵的第 i ii 行第 j jj 列的值表示 i → j i \to ji→j 这条边的权值；特殊的，如果不存在这条边，用一个特殊标记 ∞ \infty∞ 来表示；如果 i = j i = ji=j，则权值为 0 00。
它的优点是：实现非常简单，而且很容易理解；缺点也很明显，如果这个图是一个非常稀疏的图，图中边很少，但是点很多，就会造成非常大的内存浪费，点数过大的时候根本就无法存储。
[ 0 ∞ 3 ∞ 1 0 2 ∞ ∞ ∞ 0 3 9 8 ∞ 0 ] \left[
01∞9∞0∞8320∞∞∞30
0∞3∞102∞∞∞0398∞0
\right]
⎣
⎢
⎢
⎡


0
1
∞
9


∞
0
∞
8


3
2
0
∞


∞
∞
3
0


⎦
⎥
⎥
⎤

2）邻接表
邻接表是图中常用的存储结构之一，采用链表来存储，每个顶点都有一个链表，链表的数据表示和当前顶点直接相邻的顶点的数据( v , w ) (v, w)(v,w)，即顶点和边权。
它的优点是：对于稀疏图不会有数据浪费；缺点就是实现相对邻接矩阵来说较麻烦，需要自己实现链表，动态分配内存。
如图所示，d a t a datadata 即 ( v , w ) (v, w)(v,w) 二元组，代表和对应顶点 u uu 直接相连的顶点数据，w ww 代表 u → v u \to vu→v 的边权，n e x t nextnext 是一个指针，指向下一个 ( v , w ) (v, w)(v,w) 二元组。

在 C++ 中，还可以使用 vector 这个容器来代替链表的功能；
vector<Edge> edges[maxn];
1
3）前向星
前向星是以存储边的方式来存储图，先将边读入并存储在连续的数组中，然后按照边的起点进行排序，这样数组中起点相等的边就能够在数组中进行连续访问了。
它的优点是实现简单，容易理解；缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序，带来了时间开销，实用性也较差，只适合离线算法。
如图所示，表示的是三元组 ( u , v , w ) (u, v, w)(u,v,w) 的数组，i d x idxidx 代表数组下标。

那么用哪种数据结构才能满足所有图的需求呢？
接下来介绍一种新的数据结构 —— 链式前向星。
4）链式前向星
链式前向星和邻接表类似，也是链式结构和数组结构的结合，每个结点 i ii 都有一个链表，链表的所有数据是从 i ii 出发的所有边的集合（对比邻接表存的是顶点集合），边的表示为一个四元组 ( u , v , w , n e x t ) (u, v, w, next)(u,v,w,next)，其中 ( u , v ) (u, v)(u,v) 代表该条边的有向顶点对 u → v u \to vu→v，w ww 代表边上的权值，n e x t nextnext 指向下一条边。
具体的，我们需要一个边的结构体数组 edge[maxm]，maxm表示边的总数，所有边都存储在这个结构体数组中，并且用head来指向 i ii 结点的第一条边。# Q  w8 ~9 F6 P$ A0 }0 c2 ]
边的结构体声明如下：  l7 p( k% g5 \( q/ G& T8 m! c6 a
struct Edge {' s; j/ J2 j1 @0 `2 D* [- h
int u, v, w, next;
9 l% B% d( q" W- I. _( _ Edge() {}, J, z" u: P( r! j
Edge(int _u, int _v, int _w, int _next) :( [" D  v6 L' @5 }0 O4 ?+ `' ?' j0 N
      u(_u), v(_v), w(_w), next(_next)
* C- J4 o% z+ }- L% y8 h0 f {2 k$ w& ]# a9 t. r
}% ~, P6 ~( Z- {& c% X3 q
}edge[maxm];
3 m$ x; w+ ~! C, s0 Z6 {2 u1
5 a% M) A& {! b; G" q) o# S2
9 Q7 y! W1 L% L) M! B: ?$ Y3  }- Q7 @0 l: T) I& X
4# q6 M" J' P* t$ y6 b
5
2 S2 p1 }6 g- q0 b$ E4 N6
/ h& S9 b0 Y- L) t/ T) H73 m4 q  M: [4 D9 F2 D
8
- |" x' o1 X+ I- q7 s; R) _8 f初始化所有的head = -1，当前边总数 edgeCount = 0；0 {9 U+ W% ^0 Z7 i0 Q1 Q
每读入一条 u → v u \to vu→v 的边，调用 addEdge(u, v, w)，具体函数的实现如下：
) }- E0 ?& e% a# Z/ d' X8 d4 [- K1 ~void addEdge(int u, int v, int w) {
/ Q$ M$ ]/ C# z( H3 _! e0 t" K) \ edge[edgeCount] = Edge(u, v, w, head);! v% g8 L0 }. @. i0 y8 w. r* E, T; `! V
head = edgeCount++;; ~% h0 H! Z" k7 B* R; R- r
}7 Z9 |: w. c, C0 ^
1" ~  I; h) O3 K8 N3 a
2
/ q' h7 N0 B& m$ o3 b' p33 A6 I; V& k+ q/ k# q* H' v
4
! n4 h  J- I7 N% w; t: I, T' M3 [这个函数的含义是每加入一条边 ( u , v , w ) (u, v, w)(u,v,w)，就在原有的链表结构的首部插入这条边，使得每次插入的时间复杂度为 O ( 1 ) O(1)O(1)，所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现，空间上没有浪费，时间上也是最小开销。
7 }5 {6 p4 [5 Y: |. g& u6 D调用的时候只要通过head就能访问到由 i ii 出发的第一条边的编号，通过编号到edge数组进行索引可以得到边的具体信息，然后根据这条边的next域可以得到第二条边的编号，以此类推，直到 next域为 -1 为止。; j8 n. Y. R) t0 b
for (int e = head; ~e; e = edges[e].next) {/ W- w- E" u; u6 z. i3 ]# R
int v = edges[e].v;: s: O& y8 f; Y7 K
ValueType w = edges[e].w;
2 k, _! S& m" s: r .../ X4 g( k6 }/ H4 f$ W
}
+ q( H  B& J1 \1
2 C& P* ?% n9 F( L2
5 m) E" ?& s2 q" h  ?3; O* r' `, X" @6 }
4
& V# E8 K) n& n; J5 `5# I( m9 o0 x2 E* d) x
文中的 ~e等价于 e != -1，是对e进行二进制取反的操作（-1 的的补码二进制全是 1，取反后变成全 0，这样就使得条件不满足跳出循环）。$ G* S6 o3 Z. Q0 o1 M. `
4、算法入门% }" c% J* R! R
算法入门，其实就是要开始我们的刷题之旅了。先给出思维导图，然后一一介绍入门十大算法。
, R+ W* c$ y8 O% p4 i% g8 ^8 i. C; S4 ^4 N  p( ?

6 M  L8 y' U( A: n5 [; |, `% o! c入门十大算法是枚举、排序、模拟、二分、双指针、差分法、位运算、贪心、迭代、分治。
8 H6 z* \, V  o对于这十大算法，我会逐步更新道这个专栏里面：《LeetCode算法全集》。) s$ f4 I) B2 a4 |# i4 w$ V
1、枚举
5 H3 w0 ?; S7 {  y8 {) L枚举可以简单理解成for循环，从一个数组中遍历查找一个值，就是枚举；从一个数组中找到一个最大值，就是枚举；求数组所有数的和，也是枚举。3 {% I( c$ ~6 T3 C3 H7 j9 t7 `
对于枚举而言，基本就是循环语句的语法学会，这个算法就算学会了。4 c$ T) K& C: T) [
2、排序
! z' ?1 g' q; r3 M9 `$ Q7 N既然是入门，千万不要去看快排、希尔排序这种冷门排序。
0 @; H4 Y6 C( H  p冒泡排序、选择排序、简单插入排序原理好懂，先看懂再说，其他不管。因为这三者都是基于枚举的。
. h; O& X# H$ i- \* C, c( WC中有现成qsort排序函数，C++中有现成 sort排序函数，直接拿来用，等算法进阶时再回头来看快速排序的算法实现。' T4 M, w& c- D" D
3、模拟$ @1 h* E# G2 y+ U
模拟就是要求做什么，你就做什么，完全不要去考虑效率问题。6 z* n" I8 Z6 S, u2 d% W. G
不管时间复杂度和空间复杂度，放手去做！
$ i' V$ A' e! e/ s! W# }) y/ t但是，有时候模拟题需要一些复杂的数据结构，所以模拟题难起来也可以很男，难上加难。, C7 E! f0 Z" h7 V# N1 ~
4、二分5 C' n; t& d  G* k) ~" Z$ C
二分一般指二分查找，当然有时候也指代二分枚举。
$ J' D6 d9 a* e3 U# @* J8 G- s例如，在一个有序数组中查找值，我们一般这个干：
: r  b1 R  s6 `6 ^) _1）令初始情况下，数组下标从 0 开始，且数组长度为 n nn，则定义一个区间，它的左端点是 l = 0 l=0l=0，右端点是 r = n − 1 r = n-1r=n−1；) r- c$ r5 ?" V$ `
2）生成一个区间中点 m i d = ( l + r ) / 2 mid = (l + r) / 2mid=(l+r)/2，并且判断 m i d midmid 对应的数组元素和给定的目标值的大小关系，主要有三种：
$ {7 Q# x& j; a' }9 h: X( p 2.a）目标值等于数组元素，直接返回 m i d midmid；1 Z$ `* Y8 {5 `1 Z
2.b）目标值大于数组元素，则代表目标值应该出现在区间 [ m i d + 1 , r ] [mid+1, r][mid+1,r]，迭代左区间端点：l = m i d + 1 l = mid + 1l=mid+1；1 I+ {2 D: Y% T" W( {8 y
2.c）目标值小于数组元素，则代表目标值应该出现在区间 [ l , m i d − 1 ] [l, mid-1][l,mid−1]，迭代右区间端点：r = m i d − 1 r = mid - 1r=mid−1；% r2 R0 X: F2 f- j. i5 I
3）如果这时候 l > r l > rl>r，则说明没有找到目标值，返回 − 1 -1−1；否则，回到 2）继续迭代。
  M( l* s2 `) A: [) G, X. g5、双指针
9 w7 C$ C- r* C3 Q9 d$ Y, I+ j. E* b( k双指针，主要是利用两个下标在一个数组上，根据问题的单调性，进行指针偏移，由于每个指针只往后偏移，所以时间复杂度可以达到 O ( n ) O(n)O(n)，由于思想非常简单，所以出题时，热度不低。) j6 @2 U$ a+ J4 a3 @% Q" L

7 L# J' a9 i1 m% s) V: n; d' @. b
6、差分法2 g! F, N0 ]0 i6 F
差分法一般配合前缀和。
' r1 Q' \% {  E0 |- k对于区间 [ l , r ] [l, r][l,r] 内求满足数量的数，可以利用差分法分解问题；
( W4 g1 D' L+ `( R$ T假设 [ 0 , x ] [0, x][0,x] 内的 g o o d n u m b e r good \ numbergood number 数量为 g x g_xg
1 c  f0 w+ c) P! {3 ^: Yx$ F: K3 }7 t4 n5 }, ~. y
: B) N7 i6 G# J! a' @6 d( p$ \: W7 g9 B
，那么区间 [ l , r ] [l, r][l,r] 内的数量就是 g r − g l − 1 g_r - g_{l-1}g
- V3 y* K; n( A/ Y# p3 or
9 g% y( _# _9 f3 C+ H, z3 @ ; q# r1 X- w: F9 V- ]
−g % }- ]) ^/ B2 `- o6 r+ p
l−1/ {7 a5 R2 `; v! ^+ b* s

2 P- n$ b  z- _' q3 }" g ；分别用同样的方法求出 g r g_rg
& i5 J- t7 s7 C, P: ^" J; i, Kr
  B7 y$ ^; k( d. v # g& X4 P- w  @
  和 g l − 1 g_{l-1}g 5 u+ T, X4 j- G, L+ G
l−1  }# \, W* F# C+ J; \: N0 n- S
! z5 r+ p; K( S  G4 F
，再相减即可；
& L; _2 G- r6 _3 K! x7 n7 e2 Q: T4 t' ?1 F$ E
! i1 Q! o; I2 w# {  n
7、位运算
, ?: R+ ?6 x# j. N6 O- F, u位运算可以理解成对二进制数字上的每一个位进行操作的运算。
/ g' U6 o0 e  C7 b) r, k3 t) a+ j位运算分为布尔位运算符和移位位运算符。. m7 Q7 p! g9 p1 B4 R
布尔位运算符又分为位与(&)、位或(|)、异或(^)、按位取反(~)；移位位运算符分为左移(<<) 和右移(>>)。
% y! c. f6 v7 H* L0 E; N+ S' X0 r, Q如图所示：
5 z5 r: V. p" ~. b4 d# H
6 G6 u+ \3 @9 l) W
7 ^  b# T8 m- W; g位运算的特点是语句短，但是可以干大事！
% r  h. j8 x( J$ g- U* A  H7 f比如，请用一句话来判断一个数是否是2的幂，代码如下：
1 K8 o' ~* Q, D3 S8 K!(x & (x - 1))' S2 X4 D! Z& Y8 s
1
6 J' R1 I/ V& R) b' b4 A) y3 L, J8、贪心
/ H, b7 T. [8 S$ Y8 r" m, x* {贪心，一般就是按照当前最优解，去推算全局最优解。3 e. ^& Z# B8 c+ ?3 ?6 O' ^
所以，只有当当前最优解和全局最优解一致时才能用贪心算法。贪心算法的证明是比较难的，但是一些简单的贪心问题会比较直观，很容易看出来这个能够这么贪。) A7 E6 Y! E7 A
9、迭代# I3 i* W& e! k5 K0 S2 _
每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值，周而复始，直到问题全部解决。
* d+ O2 h4 N* {10、分治
' q. S1 j* b+ n* J$ ]# b分治，就是把问题分成若干子问题求解，子问题解决后，问题就解决了。一般利用递归实现。属于初学者比较头疼的内容。递归一开始学习的时候，一定要注意全局变量和局部变量的关系。
7 s3 w# O' ]6 k* k/ A' M5、算法进阶3 E+ d& Y/ c8 D7 `2 E
算法进阶这块是我打算规划自己未来十年去完成的一个项目，囊括了大学生ACM程序设计竞赛、高中生的OI竞赛、LeetCode 职场面试算法的算法全集，也就是之前网络上比较有名的《夜深人静写算法》系列，这可以说是我自己对自己的一个要求和目标吧。
- \: G5 e+ j' f6 |4 B如果只是想进大厂，那么算法入门已经足够了，不需要再来看算法进阶了，当然如果对算法有浓厚兴趣，也欢迎和我一起打卡。由于内容较难，工作也比较忙，所以学的也比较慢，一周基本也只能更新一篇。
1 _  \5 p6 n( ^( {6 `& q这个系列主要分为以下几个大块内容：' U7 I3 I2 b5 P
1）图论
- N0 q3 O& Y' T1 ^3 ~% v' q) {4 O: { 2）动态规划6 S& a7 X7 x- ~4 C" k9 o
3）计算几何/ X- ?; B* U& I, C+ ]# w
4）数论; |4 P1 U6 P4 u/ V( y( h% t
5）字符串匹配3 _" l6 D0 n; k& ]' Y
6）高级数据结构（课本上学不到的）. A4 C& N) b" J# E  r0 \
7）杂项算法% f' z: e2 H3 J0 J+ F0 B
$ G& n+ T/ t! Y

5 d/ u" i4 f7 Z5 j2 D3 \# o8 s" V5 N先来看下思维导图，然后我大致讲一下每一类算法各自的特点，以及学习方式：' E+ F: V' F8 z  X3 P3 [& C

, b- |+ [) Z0 c- I* k, t
* j+ k+ A2 z& k0 x0 F- `' z# f  y6 ^  `+ \+ {4 v) g7 @) Y; @

3 B: L) B; J% J1）图论& u; l2 m5 W- [* k2 ^
1、搜索概览" g9 z8 m4 q$ H8 i$ n
图论主要围绕搜索算法进行展开。搜索算法的原理就是枚举。利用计算机的高性能，给出人类制定好的规则，枚举出所有可行的情况，找到可行解或者最优解。5 J; m5 W  s! S: |
9 `: i9 d( K. B
& A% h! ?, X* @% `+ J3 ~
比较常见的搜索算法是深度优先搜索（又叫深度优先遍历）和广度优先搜索（又叫广度优先遍历或者宽度优先遍历）。各种图论的算法基本都是依靠这两者进行展开的。
- l# ~6 f  Z; y8 c" _2 ^9 i2、深度优先搜索3 h1 a3 X, t# o! L' W
深度优先搜索一般用来求可行解，利用剪枝进行优化，在树形结构的图上用处较多；而广度优先搜索一般用来求最优解，配合哈希表进行状态空间的标记，从而避免重复状态的计算；( M" Y7 [) {+ Q$ Q- v
原则上，天下万物皆可搜，只是时间已惘然。搜索会有大量的重复状态出现，这里的状态和动态规划的状态是同一个概念，所以有时候很难分清到底是用搜索还是动态规划。
5 f/ q: k6 o* A3 ~5 d$ O1 v但是，大体上还是有迹可循的，如果这个状态不能映射到数组被缓存下来，那么大概率就是需要用搜索来求解的。# m% Q4 h! d5 P: [
如图所示，代表的是一个深度优先搜索的例子，红色实箭头表示搜索路径，蓝色虚箭头表示回溯路径。/ L; I3 E! x, C6 l

$ b' @% T8 y' P) }& Z' P, @, [& t9 Z# Q' l
红色块表示往下搜索，蓝色块表示往上回溯，遍历序列为：. g/ T% d6 f) ?1 P* }
0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6
! g/ ^* F7 H2 v% S! ~% t9 Z& ~19 s: G) ]' U- N9 t7 r
同样，搜索的例子还有：
) R) I1 R5 o0 O- U
6 K/ D; ~: u1 d$ ~2 P
1 l  @. Y6 N: b4 f6 D/ c" q) ~! u计算的是利用递归实现的 n nn 的阶乘。  S1 H; f3 R" J, ~
3、记忆化搜索1 M* n6 ^3 c& A1 A
对于斐波那契函数的求解，如下所示：% A- Z# E2 Z, I! o; Q
f ( n ) = { 1 ( n = 0 ) 1 ( n = 1 ) f ( n − 1 ) + f ( n − 2 ) ( n > 2 ) f(n) =7 N; j( ^' T4 \7 b. B- w
⎧⎩⎨11f(n−1)+f(n−2)(n=0)(n=1)(n>2)
4 A% _- n$ M; F6 u{1(n=0)1(n=1)f(n−1)+f(n−2)(n>2)" |! `2 j+ @% f& j2 F2 L0 j
f(n)=
* E3 @7 K/ ~6 E% [+ l! v+ J% h1 A⎩
* ~) }: F1 U1 Y- i⎪# W8 `2 Z' A- T3 K
⎨
/ k6 `4 Z, M6 P# f  U& m6 e⎪
8 N9 t# F# R$ {4 U3 U5 k+ o/ A⎧
: C3 Z7 U5 p( H5 {: W : M% Q, X  u  P! O* T
  : D+ M7 e6 S8 F( _
1
2 h* N0 T+ l" o' J8 ~' d! ~& w1; ~1 u( s3 X0 f3 J) B+ _- L5 Z
f(n−1)+f(n−2)
) J% j0 s/ ?2 e  J2 O
5 W) W5 U+ K3 Y( x
5 G- w  S+ C* S! i(n=0)' g" P3 S: q2 ^" N: z, i% S" L% h
(n=1)
+ t' \1 W  Y) ^8 T$ j# t(n>2)
! a+ ?' B; q. b/ p/ j   l: p! S! P$ B8 \9 ]

! l4 Z3 p$ U% N/ K3 N" \! _  ?对于 f ( 5 ) f(5)f(5) 的求解，程序调用如下：# {- G) t, [% p0 K9 S4 @

' v$ W5 ~# H3 Z$ Z6 A! N, d" ?
" S. R# [& S5 i6 ^) Q- G8 Y! c, A这个过程用到了很多重复状态的搜索，我们需要将它优化，一般将一些状态缓存起来。
0 K% z. u# o2 `7 K) o, \* X我们通过一个动图来感受一下：& O, n" _. {6 p6 q1 c% U. i+ e

* \8 v1 k: }5 K
$ J: y6 P. x. H. [/ G5 I当第二次需要计算 f ( 2 ) f(2)f(2) 和 f ( 3 ) f(3)f(3) 时，由于结果已经计算出来并且存储在 h [ 2 ] h[2]h[2] 和 h [ 3 ] h[3]h[3] 中，所以上面这段代码的fib != inf表达式为真，直接返回，不再需要往下递归计算，这样就把原本的 “递归二叉树” 转换成了 “递归链”，从而将原本指数级的算法变成了多项式级别。8 z2 z0 T* \3 {% m3 M
这就是记忆化搜索，像这种把状态缓存起来的方法，就是动态规划的思想了。- l1 P  p; T& P8 X9 J
4、广度优先搜索
( S' L1 q" J6 `单向广搜就是最简化情况下的广度优先搜索（Breadth First Search），以下简称为广搜。游戏开发过程中用到的比较广泛的 A* 寻路，就是广搜的加强版。( G. \" P5 ~6 X! w+ o( z
我们通过一个动图来对广搜有一个初步的印象。
8 E: p  I7 s% E8 j& z8 U( W; |
* M3 f. S$ r) p" L. {
8 u  U' Q" K" @2 E" e1 |3 ^
$ W* I. E+ I1 W) a" `8 F$ f# g. e! M: W% t1 e, J0 \1 y- Y
从图中可以看出，广搜的本质还是暴力枚举。即对于每个当前位置，枚举四个相邻可以行走的方向进行不断尝试，直到找到目的地。有点像洪水爆发，从一个源头开始逐渐蔓延开来，直到所有可达的区域都被洪水灌溉，所以我们也把这种算法称为 FloodFill。
  Y$ a( g4 Q1 M# C* f那么，如何把它描述成程序的语言呢？这里需要用到一种数据结构 —— 队列。7 z6 |* T! {7 `, C3 ~0 r4 }/ j- q
这时候，算法和数据结构就完美结合了。6 B$ T5 U( Q' R" C, @/ w0 K9 n  y
2）动态规划% k$ u  ?* y! g  {& [4 j" ?+ g
动态规划算法三要素：- P  j/ b# j+ o  B# s) b: U
①所有不同的子问题组成的表；
/ ?2 G4 t$ X: q* ?0 u7 l ②解决问题的依赖关系可以看成是一个图；
  n% h" y0 P  m% Z5 ^ ③填充子问题的顺序（即对②的图进行拓扑排序，填充的过程称为状态转移）；6 s3 v) d2 ?+ R8 @4 R; n

2 ]% j. {* j/ ?7 ~" y! l' ]- _& I- S& ^7 A- E& U4 n- b; a6 r
如果子问题的数目为 O ( n t ) O(n^t)O(n : P* }0 ?# t. Y
t
& y) Y% I$ W" d$ g5 g) X$ z5 m' ]: P )，每个子问题需要用到 O ( n e ) O(n^e)O(n
# Q( }9 [7 A, T4 Oe
7 G. ?& f. H1 O/ g* ` ) 个子问题的结果，那么我们称它为 tD/eD 的问题，于是可以总结出四类常用的动态规划方程：（下面会把opt作为取最优值的函数（一般取 m i n minmin 或 m a x maxmax ）, w ( j , i ) w(j, i)w(j,i)为一个实函数，其它变量都可以在常数时间计算出来）。
9 |$ V/ ^& U. L% ^( l. A9 Q3 L1、1D/1D7 `5 X: |1 z" |8 S
d [ i ] = o p t ( d [ j ] + w ( j , i ) ∣ 0 < = i < j ) d = opt( d[j] + w(j, i) | 0 <= i < j )! `( c8 ^6 d! E9 [
d=opt(d[j]+w(j,i)∣0<=i<j)
+ i( d: v; Z! v' b状态转移如图四所示（黄色块代表d [ i ] dd，绿色块代表d [ j ] d[j]d[j]）：
) h* y2 \$ U# B# M) t: I7 }9 H# F* U. ?  M
- e/ d  x0 h6 t' u5 @3 @/ y
这类状态转移方程一般出现在线性模型中。, \" z6 J* l( f+ p, C' R3 f9 S2 u
2、2D/0D
8 ?' P: W1 p8 F% w) v6 u1 q  t! bd [ i ] [ j ] = o p t ( d [ i − 1 ] [ j ] + x i , d [ i ] [ j − 1 ] + y j , d [ i − 1 ] [ j − 1 ] + z i j ) d[j] = opt( d[i-1][j] + x_i, d[j-1] + y_j, d[i-1][j-1] + z_{ij} )
6 I) @" }' l+ U) @5 x; ]d[j]=opt(d[i−1][j]+x
$ p4 V- J$ \/ Y) [i+ A7 T, U$ G5 n4 ~$ W: l' \5 X

  l/ N, x( C5 a# n; e1 g ,d[j−1]+y 7 K: y( p! @" K% E8 ^2 h3 {
j5 N0 R9 l& X, y3 E

4 [! i& ]6 }- \/ G% j8 c5 i3 ? ,d[i−1][j−1]+z ' w& h1 ^2 w1 E1 H0 I
ij- T) J$ G# C# h, J: \; X) ]

' z7 y0 g1 v) z9 l# d% {8 W ), Q' J9 k9 t, v; M: g3 y
状态转移如图四所示：
* {- A/ z4 P6 \: q4 D8 B
7 R( D) \: m5 u7 S* l( N& f# c8 R% Y2 B" I( |
比较经典的问题是最长公共子序列、最小编辑距离。
" x; _1 A) L# y有关最长公共子序列的问题，可以参考以下文章：夜深人静写算法（二十一）- 最长公共子序列
) b9 G5 Z' Q1 k( k  O% e& B有关最小编辑距离的问题，可以参考以下文章：夜深人静写算法（二十二）- 最小编辑距离3 J! q+ g1 ]* H
3、2D/1D
$ b7 B8 ^# s! w$ ^3 n* u: Fd [ i ] [ j ] = w ( i , j ) + o p t ( d [ i ] [ k − 1 ] + d [ k ] [ j ] ) d[j] = w(i, j) + opt( d[k-1] + d[k][j] )0 P+ N# A2 A+ }+ P
d[j]=w(i,j)+opt(d[k−1]+d[k][j])) F4 I# e5 z8 G8 g9 O2 y
区间模型常用方程，如图所示：/ _4 ^& A% U0 e7 H! G

8 ?, _. u7 d' H0 @9 R/ X# b$ {1 h) B. \6 @% `. {2 \# n2 e; [
另外一种常用的 2D/1D 的方程为：
% X9 W8 G3 U6 G$ g4 Ed [ i ] [ j ] = o p t ( d [ i − 1 ] [ k ] + w ( i , j , k ) ∣ k < j ) d[j] = opt( d[i-1][k] + w(i, j, k) | k < j )
) G/ c# O$ q5 M; L% p3 Kd[j]=opt(d[i−1][k]+w(i,j,k)∣k<j); g! X" S/ Z$ O
区间模型的详细内容可以参考以下这篇文章：夜深人静写算法（二十七）- 区间DP
4 E$ {2 J7 E+ S9 n( \5 t6 V0 o4、2D/2D
% U5 c% Q* B" ?- `& ^& @, k3 s% C2 Jd [ i ] [ j ] = o p t ( d [ i ′ ] [ j ′ ] + w ( i ′ , j ′ , i , j ) ∣ 0 < = i ′ < i , 0 < = j ′ < j ) d[j] = opt( d[i'][j'] + w(i', j', i, j) | 0 <= i' < i, 0 <= j' < j)
6 n' J( h  N+ j5 J3 }2 V/ Kd[j]=opt(d[i
1 x0 C# @5 K6 o) V. d" O( u8 h′
5 n: f( {/ X6 f; L& R' F ][j
  Z9 H! i1 d) J$ L3 K* g′, P8 b0 I. Q* J$ F; n2 B' z. [; m7 M
]+w(i
  C: v; U$ O! M1 c0 w8 n′
+ y/ }0 T, f% N6 T" ~6 r. d  g$ b ,j 3 j1 l( f# B& e; p8 P7 v' A
′
# o( O, B4 [  T: q* Q* m2 ]) D: b ,i,j)∣0<=i
1 R: {( R! h7 y( q( m′
7 B) M. _4 f* b8 Q* x <i,0<=j
! L8 }; |- u2 N9 ]; y) S, x' ?# Q′
- B$ a  Y+ n' Y <j)5 @9 r$ K2 b* ]
如图所示：* Q% l3 I2 e8 E# o3 S5 w' d" A8 P
$ `8 v, ~' R2 c$ T! y

  R% b, I; K7 E+ E9 x! r常见于二维的迷宫问题，由于复杂度比较大，所以一般配合数据结构优化，如线段树、树状数组等。% `" A' |6 M& U
对于一个tD/eD 的动态规划问题，在不经过任何优化的情况下，可以粗略得到一个时间复杂度是O ( n t + e ) O(n^ {t+e})O(n
# o. E3 U; M$ A9 g) T2 w( b& Wt+e
' a5 V. z9 ?9 p" g' l1 S )，空间复杂度是O ( n t ) O(n^t)O(n 8 h9 P3 R  O+ J" P2 t2 d8 x
t
! h6 {4 T. H+ ~ ) 的算法，大多数情况下空间复杂度是很容易优化的，难点在于时间复杂度，后续章节将详细讲解各种情况下的动态规划优化算法。5 a  n" l: R  l- g( A0 g
3）计算几何
8 T, @7 X; t  X" j& z$ |, p( _7 h计算几何的问题是代码量最大的。它是计算机科学的一个分支，以往的解析几何，是用代数的方法，建立坐标系去解决问题，但是很多时候需要付出一些代价，比如精度误差，而计算几何更多的是从几何角度，用向量的方法来尽量减少精度误差，例如：将除法转化为乘法、避免三角函数等近似运算等等。) w* L' O/ w" P3 J( W+ @( |
如果一个比赛中，有一道计算几何的题，那么至少，它不会是一道水题。
8 j1 L: l( l0 g6 v1、double 代替 float+ G! {5 c  O  `! h: X
c++ 中 double 的精度高于 float，对精度要求较高的问题，务必采用 double；
3 }! @6 g* m. g7 p* R3 z2、浮点数判定1 G# w7 n4 A& x
由于浮点数（小数）中是有无理数的，即无限不循环小数，也就是小数点后的位数是无限的，在计算机存储的时候不可能全部存下来，一定是近似的存储的，所以浮点数一定是存在精度误差的（实际上，就算是有理数，也是存在误差的，这和计算机存储机制有关，这里不再展开，有兴趣可以参见我博客的文章：C++ 浮点数精度判定）；
7 H8 G8 ~2 C- t& j* e两个浮点数是否相等，可以采用两数相减的绝对值小于某个精度来实现：
6 a) f8 x* z8 t) z. pconst double eps = 1e-8;3 p4 J/ |6 {$ K- C& v9 E1 o5 |
bool EQ(double a, double b) {6 ]) \. A! t, o+ c- F
return fabs(a - b) < eps;
  g/ c; e; x% H& h! o. W7 Z% n}/ i9 C  [/ h; l! W9 x# O
11 G. z( A" ]1 d) R& c) e9 _. u
2
  L# X2 [# E6 F2 h. W! r3
' ~, y1 z; b6 j9 S) W4
7 Q6 R# Z. H$ j5 k' t5 x并且可以用一个三值函数来确定某个数是零、大于零还是小于零：
5 J$ ]7 N8 n  i4 Y2 ]  Xint threeValue(double d) {
0 k  T$ Y( c* }9 e) T7 h: R% P  e if (fabs(d) < eps)3 i- ^7 O: S" ~0 T( y7 w
      return 0;
) v$ N6 ~" Y. N; [: J return d > 0 ? 1 : -1;/ I& N4 p8 p2 e1 I! q: T
}
1 z1 b% v# C. [8 [: I8 A4 q5 V16 @4 E; d, t* b0 |7 o
22 m! o- ]! ~2 O/ t  v/ o" @
3
  ^1 M# ~% ~3 }# R* l$ h/ O& u. w; B4. P8 I. ^* q6 R1 ]
5
! s8 Q1 ?+ m: s9 I$ U% F3、负零判定
" |2 ~+ F4 z5 c  {" U! U因为精度误差的存在，所以在输出的时候一定要注意，避免输出 -0.00：; Q1 r3 H+ X" }7 @8 N% m  g' \) @
double v = -0.0000000001;
1 Z1 I: @: q* _7 Z. g0 n/ V printf("%.2lf\n", v);' x& ]; S# K* l) I! A4 I, f0 \
18 r" Z* ^/ I% Q6 Y) X2 Z. U( C! F
2' N( [9 }0 E! e+ U* D3 }; X
避免方法是先通过三值函数确定实际值是否为0，如果是0，则需要取完绝对值后再输出：. c# x0 [. k, ]3 z
double v = -0.0000000001;3 J% n& z! i2 a5 M  L( R( x5 _& k2 k* M
if(threeValue(v) == 0) {
7 H8 ]* e1 y$ G$ M" N       v = fabs(v);5 D' e! v1 \7 m9 }
}+ c/ w' p$ E1 S7 V0 M+ v9 h
printf("%.2lf\n", v);- z. Y9 J; {& Q
1, L4 t, E# K+ t. f
2
7 e1 C9 }/ Z  f3
6 t) |! M2 h! n2 p$ @$ [# K4
/ |, ?" e9 e, Y$ b' f( m3 ]7 A+ C' {5
7 Y9 q9 S9 s& F! U" {4、避免三角函数、对数、开方、除法等; r. ^' _+ e, B8 C. ?  j. L
c++ 三角函数运算方法采用的是 CORDIC算法，一种利用迭代的方式进行求解的算法，其中还用到了开方运算，所以实际的算力消耗还是很大的，在实际求解问题的过程中，能够避免不用就尽量不用。$ W8 h# b" g2 a5 s8 N
除法运算会带来精度误差，所以能够转换成乘法的也尽量转换为乘法运算。
- I9 k( x4 y% d9 }5、系统性的学习) j0 M- U: P) ?4 v( @6 l/ q5 c
基础知识：点、向量、叉乘、点乘、旋转、线段、线段判交、三角形面积；* P' X$ w/ G9 m/ f
进阶知识：多边形面积、凸多边形判定、点在多边形内判定；
9 G2 n# D) ]# g* k7 e* M" B! v相关算法：二维凸包、三维凸包、旋转卡壳、多边形面积交、多边形面积并、多边形面积异或、多边形和圆的面积交、半平面交、最小覆盖圆、最小包围球、模拟退火。
* x/ {0 \/ V. u8 j6 U$ r( y
& I) @4 ~7 C- d3 \
% h) y! t) Z+ a$ s2 Q; l学习计算几何，最好是系统性的，刷题的过程中不断提炼出自己的模板。+ j8 c- N9 Z( t7 z6 Q+ J
4）数论
6 m, t: f5 \0 Q刷题的时候遇到不会的数论题，真的是很揪心，从头学起吧，内容实在是太多了，每个知识点都要证明吃透，不然下次遇到还是不会；不学吧，又不甘心，就是单纯的想把这个题过了，真是进退两难！
7 r0 _* m1 b9 T! n4 p" v数论对一个人的数学思维要求较高，但是一般也是一些固定的模式，所以把模板整理出来很重要。
; j8 K. X3 |8 n, a当然，数论也有简单问题，一般先做一些入门题提升信心。
( Z. H. `4 b. n+ f8 Y1、数论入门
0 R7 I2 C% G: @, p, {/ [0 h( R: g主要是一些基本概念，诸如：
( Y% x$ T$ j7 T1 x2 }9 O5 o* ?整除性、素数与合数、素数判定、素数筛选法、因数分解、算术基本定理、因子个数、因子和、最大公约数 (GCD) 和最小公倍数 (LCM)、辗转相除、同余、模运算、快速幂取模、循环节；" E0 R4 T" x- H: s8 L
2、数论四大定理
9 L! C  ]$ }# E( n这四个定理学完，可以KO很多题：
/ I2 |7 y8 d+ h/ U0 Q5 V' F/ K6 O欧拉定理、中国剩余定理、费马小定理、威尔逊定理9 y- J# t$ {9 p5 k/ p
3、数论进阶
4 M+ i3 [$ v- w% {4 @3 x系统性的学习，基本也就这些内容了：
2 h: Y% f4 S8 @& S0 G' r扩展欧几里得、逆元、欧拉函数、同余方程组、扩展欧拉定理、RSA、卢卡斯定理、整数分块、狄利克雷卷积、莫比乌斯反演、大数判素、大数因子分解、大步小步离散对数等等。, M8 }. [& @0 H) z( C8 h1 \
5）字符串匹配
/ k: Y4 ^$ K* H3 A9 H字符串匹配学习路线比较明确。6 H$ h, z5 ^4 I6 Q* [" x
先学习前缀匹配：字典树。9 ~/ o: V4 a: r* q
然后可以简单看一下回文串判定算法：Manacher。
& I) _. I+ l. Y4 _$ i% X. u9 x0 U. r以及经典的单字符串匹配算法：KMP。' G2 ?% N/ a* r4 j% N6 u' P+ V
实际上平时最常用的还是 BM 算法，而ACM中基本不考察。
# m) M1 }7 O  m: P! I$ [, j2 G3 e然后就是较为高阶的前缀自动机、后缀数组、后缀树、后缀自动机了。& p* B% R& P$ k" s+ {% c) O
关于算法学习路线的内容到这里就结束了。7 N3 V+ _) t- p3 v: n
如果还有不懂的问题，可以想方设法找到作者的微信进行在线咨询。2 l. u8 m4 {; j* o  g1 l
参考资料$ X/ }8 m/ `, `  x. Y4 w- o
【阶段一】C语言学习资料：《光天化日学C语言》（日更）
) r/ K* [3 N9 N5 h& F  u3 N【阶段二】C语言例题：《C语言入门100例》（日更）; J7 ]8 a9 I  L' e% z4 L6 F$ w& b
【阶段三】算法入门题集：《LeetCode算法全集》（日更）
( b) U$ R0 R7 S6 u) P5 ?【阶段四】算法进阶：《夜深人静写算法》（周更）6 P8 p2 v5 k3 e7 V# R, U& @2 ^
————————————————
3 d. U* M% c/ ~; `8 b版权声明：本文为CSDN博主「英雄哪里出来」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。/ M* g, C! K) |( H9 T- N
原文链接：https://blog.csdn.net/WhereIsHeroFrom/article/details/118382228- g9 ?1 l  C% |- d5 [) W

5 l. d% c3 |4 s: W. Q- O# l0 t. Y3 p/ m5 K1 Q