查看: 4379|回复: 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 结点的第一条边。
4 @4 N1 I! o0 {' Q边的结构体声明如下：
7 `8 t+ `$ r5 {* g1 J$ istruct Edge {
1 P* L+ Z+ r0 r- E0 ?6 [7 q int u, v, w, next;
8 K- E8 m  V8 s- X Edge() {}
/ _  I2 o+ [  ?# E0 @- R Edge(int _u, int _v, int _w, int _next) :5 a- i* f7 G, A! X" X: Z
      u(_u), v(_v), w(_w), next(_next)
( ~  H; f( w$ x+ g3 \$ i {
9 a) u' p; u4 Q6 ^3 V4 Y( } }  N8 ~5 ?( i" E( L
}edge[maxm];$ R6 {5 H( h" C9 s4 O1 U$ _
1
% ?$ I4 A% y. o2 M- x: s. M2- M6 c. @  Z" ]
3. \3 }+ y3 Y7 y5 z
49 L- I, U! ~1 @& K
56 O3 L2 z; S. g, q6 O; h' Q9 E) f
6! F( `  N8 M' ]) v% {7 g
78 ]! X3 e$ ]( d3 Y
8
8 G3 }8 S& k  ~  o+ r: W初始化所有的head = -1，当前边总数 edgeCount = 0；) F$ R: z1 B' S7 F9 [
每读入一条 u → v u \to vu→v 的边，调用 addEdge(u, v, w)，具体函数的实现如下：
# z& }% c1 S# W+ V5 K/ Zvoid addEdge(int u, int v, int w) {
4 x# e6 L3 `) B( o6 S( u edge[edgeCount] = Edge(u, v, w, head);, p( U2 [$ R3 \7 w0 B9 i- N
head = edgeCount++;
; {9 \7 g, U: G0 P}- z) Y' j) ?+ H
1+ e9 F: L  B8 a" ?: L
2
1 n. N: s2 J" V9 X9 f33 P" v! _7 W8 G
4% _! Q0 X- G0 s/ S, s
这个函数的含义是每加入一条边 ( u , v , w ) (u, v, w)(u,v,w)，就在原有的链表结构的首部插入这条边，使得每次插入的时间复杂度为 O ( 1 ) O(1)O(1)，所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现，空间上没有浪费，时间上也是最小开销。
* T0 p' I) l; \2 }调用的时候只要通过head就能访问到由 i ii 出发的第一条边的编号，通过编号到edge数组进行索引可以得到边的具体信息，然后根据这条边的next域可以得到第二条边的编号，以此类推，直到 next域为 -1 为止。
* j5 D5 L6 F1 v& Ufor (int e = head; ~e; e = edges[e].next) {
/ y" d3 `2 V9 p! B9 c0 f9 F$ O int v = edges[e].v;
! }  @  `  v/ i, B& \) N3 \0 W ValueType w = edges[e].w;
7 j1 h" E4 j% Y3 q* C; t( ^- ? ...
- [, u- g* i. f& {7 Y: O1 Q}  }" S" a) D, u' ]$ u
1
7 u& J: d# i6 _6 X. a9 }" ^& P28 g/ }/ J0 w# h4 ^
3
' d6 |. z6 k& Q2 {6 X4* f0 e( Y3 |  C3 s
5
7 S- z, Q- k4 N文中的 ~e等价于 e != -1，是对e进行二进制取反的操作（-1 的的补码二进制全是 1，取反后变成全 0，这样就使得条件不满足跳出循环）。1 |7 L! F) d. Q
4、算法入门3 Q) k( c9 u0 D* c3 C2 L
算法入门，其实就是要开始我们的刷题之旅了。先给出思维导图，然后一一介绍入门十大算法。
8 C+ N: a5 Q3 c$ p) I( e
, Q/ M) Q" d6 n0 Q
2 r1 C1 B) ?! J6 _入门十大算法是枚举、排序、模拟、二分、双指针、差分法、位运算、贪心、迭代、分治。
对于这十大算法，我会逐步更新道这个专栏里面：《LeetCode算法全集》。
' t( o% D( w9 E1 O. [& r1、枚举
) c. n% a5 E" }, ]  w6 a& X# R6 ~枚举可以简单理解成for循环，从一个数组中遍历查找一个值，就是枚举；从一个数组中找到一个最大值，就是枚举；求数组所有数的和，也是枚举。, d# }. [9 V4 |4 o( t: P
对于枚举而言，基本就是循环语句的语法学会，这个算法就算学会了。
4 ~$ i  D# E0 t2、排序' l! Y* ?# @9 G2 y6 R% v; W
既然是入门，千万不要去看快排、希尔排序这种冷门排序。  Z5 p. P) u$ I
冒泡排序、选择排序、简单插入排序原理好懂，先看懂再说，其他不管。因为这三者都是基于枚举的。" l* f  S  r1 h; G& e
C中有现成qsort排序函数，C++中有现成 sort排序函数，直接拿来用，等算法进阶时再回头来看快速排序的算法实现。
  x, J. x6 {" \: w2 {: _, B0 p6 e3、模拟$ m/ s: a+ {2 S0 S' M
模拟就是要求做什么，你就做什么，完全不要去考虑效率问题。( _2 c- |# y+ U3 D& L
不管时间复杂度和空间复杂度，放手去做！& ]% R* D2 @" n3 H0 E3 @
但是，有时候模拟题需要一些复杂的数据结构，所以模拟题难起来也可以很男，难上加难。
/ F' V+ U# p! \! I9 O4、二分- m) j  O; U2 p  R7 K4 k( q
二分一般指二分查找，当然有时候也指代二分枚举。
8 P4 T* ~3 T* M! x( p+ [例如，在一个有序数组中查找值，我们一般这个干：
! `' Y; }7 c  @1）令初始情况下，数组下标从 0 开始，且数组长度为 n nn，则定义一个区间，它的左端点是 l = 0 l=0l=0，右端点是 r = n − 1 r = n-1r=n−1；
9 _# V8 j4 Q$ z( y+ J4 _8 {' ?2）生成一个区间中点 m i d = ( l + r ) / 2 mid = (l + r) / 2mid=(l+r)/2，并且判断 m i d midmid 对应的数组元素和给定的目标值的大小关系，主要有三种：4 m% @: i$ G4 Q8 ]
2.a）目标值等于数组元素，直接返回 m i d midmid；
' J! J2 ]7 s  R4 ~ 2.b）目标值大于数组元素，则代表目标值应该出现在区间 [ m i d + 1 , r ] [mid+1, r][mid+1,r]，迭代左区间端点：l = m i d + 1 l = mid + 1l=mid+1；
/ Z" e9 I. v, r 2.c）目标值小于数组元素，则代表目标值应该出现在区间 [ l , m i d − 1 ] [l, mid-1][l,mid−1]，迭代右区间端点：r = m i d − 1 r = mid - 1r=mid−1；
8 g  A& A5 {) Q/ i+ W3）如果这时候 l > r l > rl>r，则说明没有找到目标值，返回 − 1 -1−1；否则，回到 2）继续迭代。' U' M1 s* G9 q3 X$ \& j3 Q7 @
5、双指针
2 S( z( q! ]3 K5 [双指针，主要是利用两个下标在一个数组上，根据问题的单调性，进行指针偏移，由于每个指针只往后偏移，所以时间复杂度可以达到 O ( n ) O(n)O(n)，由于思想非常简单，所以出题时，热度不低。: u( D$ l3 n. K' u: h( d
2 A0 D3 T3 t" a2 H! C

. V$ w/ N* \7 `" u6、差分法. g, t1 }/ R- P1 F1 |
差分法一般配合前缀和。0 a6 d9 c/ k0 x* ^! Z6 z
对于区间 [ l , r ] [l, r][l,r] 内求满足数量的数，可以利用差分法分解问题；
) `, n& r: `; A/ G假设 [ 0 , x ] [0, x][0,x] 内的 g o o d n u m b e r good \ numbergood number 数量为 g x g_xg ! {( x1 o4 \4 G1 n$ e# [9 X
x
' D+ t6 n* C% ^ + f0 I" y: C7 N( U9 _( s  w4 Y
，那么区间 [ l , r ] [l, r][l,r] 内的数量就是 g r − g l − 1 g_r - g_{l-1}g 9 u* A3 u# t( R. _- L
r; p1 S# h4 S; ?3 T4 C

* M$ M: e* T; L5 ^4 n% q* ]$ q −g
% K- p; O7 I% y( b. Y- [l−1
. e. h+ t8 b2 U, s1 h ; O& h+ F: E2 D7 s* Y( A( g) |
；分别用同样的方法求出 g r g_rg
" |/ _6 @/ W1 V  pr
- n! c! x4 k. q: ?5 S, J
3 A+ i# Z# s. s' b# g: q  和 g l − 1 g_{l-1}g
6 |' O+ S# C4 A. Dl−19 O5 p6 C, Y. x/ H) S* l

6 R1 r" ?4 O6 S+ F6 t ，再相减即可；2 p& z0 g5 P4 t3 g
. D& }3 K3 V) K% A  v% d! p

0 c# d- L5 v" h' h2 k6 E7、位运算" w2 `* w3 R$ b' e6 D# J
位运算可以理解成对二进制数字上的每一个位进行操作的运算。
, l: c8 r- s/ b4 \( P位运算分为布尔位运算符和移位位运算符。
# F  p- Q+ n: i6 H. V: o. ~* ]布尔位运算符又分为位与(&)、位或(|)、异或(^)、按位取反(~)；移位位运算符分为左移(<<) 和右移(>>)。
3 a' R) ~9 H. ?8 {如图所示：
8 O8 `( l5 [9 W1 R  q/ @9 V8 t
4 i+ _2 [! P+ A2 s' {
* j3 t: I: D) S) R位运算的特点是语句短，但是可以干大事！4 M( L8 T1 P* i$ k
比如，请用一句话来判断一个数是否是2的幂，代码如下：0 d* `+ S6 @9 R
!(x & (x - 1))
0 y7 W" p+ Z$ u7 y3 v16 ?% S4 p4 I! [8 l- q
8、贪心
8 O3 h" X5 E5 ~; y贪心，一般就是按照当前最优解，去推算全局最优解。  g! }; C  T& b) z
所以，只有当当前最优解和全局最优解一致时才能用贪心算法。贪心算法的证明是比较难的，但是一些简单的贪心问题会比较直观，很容易看出来这个能够这么贪。
$ Q8 c1 r5 ?; }$ S. W$ n9、迭代: u; M2 g8 I& w8 p1 `* L
每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值，周而复始，直到问题全部解决。
# c0 q+ _' l" x6 a) U4 c# E( N$ @# w; M10、分治: T% V* }, M$ K, {" U' J$ I
分治，就是把问题分成若干子问题求解，子问题解决后，问题就解决了。一般利用递归实现。属于初学者比较头疼的内容。递归一开始学习的时候，一定要注意全局变量和局部变量的关系。
+ m2 F7 f) H0 A( j( @) z- ]1 n5、算法进阶
# k" |  ~$ k: T0 Y1 Y( Y1 ?! ]算法进阶这块是我打算规划自己未来十年去完成的一个项目，囊括了大学生ACM程序设计竞赛、高中生的OI竞赛、LeetCode 职场面试算法的算法全集，也就是之前网络上比较有名的《夜深人静写算法》系列，这可以说是我自己对自己的一个要求和目标吧。& f6 a& y- t5 M! r
如果只是想进大厂，那么算法入门已经足够了，不需要再来看算法进阶了，当然如果对算法有浓厚兴趣，也欢迎和我一起打卡。由于内容较难，工作也比较忙，所以学的也比较慢，一周基本也只能更新一篇。  {! k" x5 g3 a/ c
这个系列主要分为以下几个大块内容：
& @& ~; ~+ G/ K) y: ] 1）图论
+ g+ f3 i. K/ a 2）动态规划
: J' y2 n  N, z8 Z% P0 e" J' j 3）计算几何
# ?2 G$ b/ f1 G3 _! V 4）数论+ B6 S, H2 r  w" \
5）字符串匹配
% g, ~, Y, p8 n; v' p. V9 F% d 6）高级数据结构（课本上学不到的）
  Z4 c# F3 U) m/ o. Y" L5 Z8 | 7）杂项算法4 ~# Y0 w+ f/ Q, p
0 E# ]* M1 C2 W9 Z/ F. r7 e3 p: u

% a8 G" E* a# n6 G先来看下思维导图，然后我大致讲一下每一类算法各自的特点，以及学习方式：
; x1 l9 q* A" O9 f" l8 T  k0 p/ Y, w. [& B5 }

- Z! w" X4 o* c* E! Z
1 ~9 V1 r" A7 U1 y; Z+ b! z* W' E3 ]8 w
1）图论
. x+ {- w) _+ O4 K2 l5 h& I$ C3 o1、搜索概览) _" z" e9 a9 T; t3 S+ L3 y
图论主要围绕搜索算法进行展开。搜索算法的原理就是枚举。利用计算机的高性能，给出人类制定好的规则，枚举出所有可行的情况，找到可行解或者最优解。0 P. |  p, Y- I" U: p; k
/ u. C) y: G. V$ _6 a

2 q4 r; Q4 k3 }& u- J比较常见的搜索算法是深度优先搜索（又叫深度优先遍历）和广度优先搜索（又叫广度优先遍历或者宽度优先遍历）。各种图论的算法基本都是依靠这两者进行展开的。
6 l8 A" H  S- d8 C2、深度优先搜索
1 P# c/ [6 y; r深度优先搜索一般用来求可行解，利用剪枝进行优化，在树形结构的图上用处较多；而广度优先搜索一般用来求最优解，配合哈希表进行状态空间的标记，从而避免重复状态的计算；9 J! _: i% ?% a8 M% C7 v
原则上，天下万物皆可搜，只是时间已惘然。搜索会有大量的重复状态出现，这里的状态和动态规划的状态是同一个概念，所以有时候很难分清到底是用搜索还是动态规划。  H. Y  H" U; }& v8 ~  C
但是，大体上还是有迹可循的，如果这个状态不能映射到数组被缓存下来，那么大概率就是需要用搜索来求解的。8 L  Q: j+ ~; q1 |4 t& H$ ?  Q
如图所示，代表的是一个深度优先搜索的例子，红色实箭头表示搜索路径，蓝色虚箭头表示回溯路径。
9 ], Z  y$ o2 V" n2 j& Q& E8 t# _, P$ D5 g

- h! K! h2 x. t- \6 C红色块表示往下搜索，蓝色块表示往上回溯，遍历序列为：
, S9 t( T. K2 m# e0 @. f3 i 0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6
0 E1 ~4 Q5 z! x$ k' N! E! c, i1
- y3 }4 B( ?. X+ u同样，搜索的例子还有：( J' T4 Y& s' L7 M

, \3 S" [! c) ~0 R
, n" x  y1 a8 r, _+ w1 t5 g. P! r计算的是利用递归实现的 n nn 的阶乘。
( u2 ?' `% ]8 R3、记忆化搜索* |. n' M# x" A9 z2 L2 p
对于斐波那契函数的求解，如下所示：
( c* a. j1 A, Df ( n ) = { 1 ( n = 0 ) 1 ( n = 1 ) f ( n − 1 ) + f ( n − 2 ) ( n > 2 ) f(n) =' H. U4 M5 C! B& F( B
⎧⎩⎨11f(n−1)+f(n−2)(n=0)(n=1)(n>2)
$ ?& U& C# U" r5 G) ]0 P, k{1(n=0)1(n=1)f(n−1)+f(n−2)(n>2)
  l6 |$ Q3 t( w7 If(n)=
9 j5 P7 x6 S+ f* ?, I. S! L⎩; k& t4 `1 s( H  @
⎪6 \* O0 [6 E: O" ^0 m! n( m4 q
⎨# H" ?7 @: o2 B2 \
⎪! T7 _* O% k8 ^7 E& `
⎧
1 j$ m$ r$ E2 ?0 \2 e- Q: s- O
5 d$ Z7 K, A9 h/ A6 _
% M0 @6 f6 O" O1
4 Q/ ~2 t  U' g7 w' p$ l1
: I' r; P# c6 |' i% L/ E5 W4 af(n−1)+f(n−2)3 F1 c% n% ^6 f+ ]/ e6 c
( W% f- N  n" e$ j/ g! J1 F
  - }( C4 _0 {$ }/ W
(n=0)- n1 S9 ^6 z6 ^
(n=1)) \7 I% D8 Z' c
(n>2)5 Z! H3 {: l; r0 H0 d4 U

# \$ b" L( y! a" {! \ ' @  W# v+ w& k  A  S9 U. V; v
对于 f ( 5 ) f(5)f(5) 的求解，程序调用如下：
; o9 i; Y! q& d$ f7 _. u/ _# i- l; C+ L; o0 p' r2 P5 J

& t6 m% l% k$ c& H; K这个过程用到了很多重复状态的搜索，我们需要将它优化，一般将一些状态缓存起来。
1 r' J( D) z8 D/ M我们通过一个动图来感受一下：# y4 \2 Z/ O$ q) R, o9 Q
$ p5 B5 p3 {- B4 u. v- m) N& h

7 P* i, x9 k+ B% D" y2 p' _/ v当第二次需要计算 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表达式为真，直接返回，不再需要往下递归计算，这样就把原本的 “递归二叉树” 转换成了 “递归链”，从而将原本指数级的算法变成了多项式级别。
3 C, i( M1 \, K  Y5 Y3 @$ x: [这就是记忆化搜索，像这种把状态缓存起来的方法，就是动态规划的思想了。  d! M4 z/ F/ W8 D& I; |
4、广度优先搜索1 Z* [& ?. h& I. T0 r1 c
单向广搜就是最简化情况下的广度优先搜索（Breadth First Search），以下简称为广搜。游戏开发过程中用到的比较广泛的 A* 寻路，就是广搜的加强版。
+ P4 a' x% _* D( Q我们通过一个动图来对广搜有一个初步的印象。
. u2 Q1 w, b$ @7 v* Q* Y- K" j: B  |
; D' L8 y6 s2 k: u8 {

' l, C& \3 B, }8 E6 t
/ a: {& {, B9 V$ i" s从图中可以看出，广搜的本质还是暴力枚举。即对于每个当前位置，枚举四个相邻可以行走的方向进行不断尝试，直到找到目的地。有点像洪水爆发，从一个源头开始逐渐蔓延开来，直到所有可达的区域都被洪水灌溉，所以我们也把这种算法称为 FloodFill。
7 {9 g2 e& |' T9 W3 O那么，如何把它描述成程序的语言呢？这里需要用到一种数据结构 —— 队列。* T' M8 k, S. `. Z" f
这时候，算法和数据结构就完美结合了。
$ i) |3 X: E# |$ D, ]: d2）动态规划
# m$ `3 y; I5 |! q动态规划算法三要素：
$ Y1 g) w0 Y3 N0 I4 ?( N ①所有不同的子问题组成的表；3 w3 K4 s/ h. R2 b6 P
②解决问题的依赖关系可以看成是一个图；
5 a  T) ]6 @7 C- I4 M, w, X% B+ W ③填充子问题的顺序（即对②的图进行拓扑排序，填充的过程称为状态转移）；( V5 L( j- o1 |" |  r+ j
" N7 U8 x8 R5 r9 R" c2 y
' v! P+ }4 M4 m  y; r3 w1 l
如果子问题的数目为 O ( n t ) O(n^t)O(n # T0 J$ Y9 ], E+ i# o4 \
t
. D5 O+ s# a* V7 I9 y )，每个子问题需要用到 O ( n e ) O(n^e)O(n & i+ _3 U* m: U) R, c
e1 T0 o7 {4 R% u8 C& \: c2 j0 _
) 个子问题的结果，那么我们称它为 tD/eD 的问题，于是可以总结出四类常用的动态规划方程：（下面会把opt作为取最优值的函数（一般取 m i n minmin 或 m a x maxmax ）, w ( j , i ) w(j, i)w(j,i)为一个实函数，其它变量都可以在常数时间计算出来）。5 v* e3 @4 K3 y. a; n' O4 h
1、1D/1D- X# _9 g. Y) G" l& B- |2 c
d [ i ] = o p t ( d [ j ] + w ( j , i ) ∣ 0 < = i < j ) d = opt( d[j] + w(j, i) | 0 <= i < j ). m5 f9 R7 [8 T3 K
d=opt(d[j]+w(j,i)∣0<=i<j)/ R" F9 ]: u% I8 ^+ K4 ]- H* g
状态转移如图四所示（黄色块代表d [ i ] dd，绿色块代表d [ j ] d[j]d[j]）：4 _: T; f* B- U% d
* [& L( l& t* F% {9 k4 u& ~
* O+ ]8 t' W! I& A
这类状态转移方程一般出现在线性模型中。
3 v9 A6 e/ H. Y* b4 z3 Y2、2D/0D
" R: G/ G9 d3 o8 Hd [ 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} )
  G6 v6 g9 j" _/ L7 xd[j]=opt(d[i−1][j]+x
2 l/ b$ L4 i/ _5 M! {% ?5 U  ki
5 M* P( l" C( C0 ] ) e% v, K0 V2 n
,d[j−1]+y ) J6 K. v' P0 R+ Q5 Q2 f" [! U
j
3 V( _5 E5 ^4 A6 { ' e! d4 v$ y- W$ Q, }" T
,d[i−1][j−1]+z
- K; o7 O% y9 b7 S! q( Y: ~/ z1 sij: l0 |" B# A4 z* l

9 X: o$ r; p* \ )
! D1 X  _/ c# c  f2 Q状态转移如图四所示：
1 p* d! m$ G, ~8 _* Z0 `+ e' `
) J, Y( a$ M- @2 R. \* J
4 J9 Y; |. {6 _  ^. l. [+ E8 [/ Z比较经典的问题是最长公共子序列、最小编辑距离。
% z- z5 x6 v: c5 W! T: I0 v* e有关最长公共子序列的问题，可以参考以下文章：夜深人静写算法（二十一）- 最长公共子序列* n8 t, s$ e- o5 @) X
有关最小编辑距离的问题，可以参考以下文章：夜深人静写算法（二十二）- 最小编辑距离8 e! n' M! F( O
3、2D/1D
3 C( z" {- j# V, ~d [ 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] )3 Q; |* t& {0 n6 O7 F4 {8 w+ |
d[j]=w(i,j)+opt(d[k−1]+d[k][j])* D/ k4 Y5 T  ~
区间模型常用方程，如图所示：
7 W! H  T+ s. o! h% I. T, s% k7 Z' ]1 e; T, i1 P. s

0 ^! D( U% [$ y另外一种常用的 2D/1D 的方程为：6 r5 p( t# `- ]0 }
d [ 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 )5 K- p/ s' Z2 K- \3 w
d[j]=opt(d[i−1][k]+w(i,j,k)∣k<j)
( _7 S- [3 x( ?. h) m. P- E. w区间模型的详细内容可以参考以下这篇文章：夜深人静写算法（二十七）- 区间DP
# M' m. G  ]9 a/ A, b& k1 B/ X" s4、2D/2D" w9 E  x0 l, I. V
d [ 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)& z2 u* i: y' V5 f
d[j]=opt(d[i
" j; u# r( z/ l& g  {6 `′
$ m: `. z. C2 e! @ ][j
  F, d  o7 s2 `5 X2 `′
! n7 W/ |, [" {0 v" {0 S ]+w(i
7 Z' a) `" ~  Q% F) R6 F  F* X' m′
0 y4 J3 u2 Q! m/ \% K6 L ,j ' H* r  A6 c( h& s: X. _9 D
′$ f2 B; A2 k9 u) b( _
,i,j)∣0<=i ) z+ Q/ I8 F9 T; i( l5 _
′
/ [* l9 S  J) O  a$ F* l <i,0<=j
4 k6 S$ c) |2 H! w1 M' O9 Y′8 h" W9 B# F# B) \0 Z
<j)
$ H) s7 j" A, Y7 C) A" j5 r如图所示：
- K0 x  u" W& ~& h
& [! ^$ \+ t2 ?$ [& C9 t
- \9 a( x: _8 o8 M4 W- ?1 I常见于二维的迷宫问题，由于复杂度比较大，所以一般配合数据结构优化，如线段树、树状数组等。
6 C; I( y, h! r4 V3 J( V5 O对于一个tD/eD 的动态规划问题，在不经过任何优化的情况下，可以粗略得到一个时间复杂度是O ( n t + e ) O(n^ {t+e})O(n - \7 {  G* w) D
t+e& L( ?: ~; j9 U5 H" b0 f
)，空间复杂度是O ( n t ) O(n^t)O(n % m& ~! d  z( h. d
t
; w% e2 j6 z% P2 ]3 k- _- A" ^ ) 的算法，大多数情况下空间复杂度是很容易优化的，难点在于时间复杂度，后续章节将详细讲解各种情况下的动态规划优化算法。" O6 v6 `) @9 ]% b/ [5 C$ D; Q
3）计算几何: L' Q6 n- A" {) I/ V! N
计算几何的问题是代码量最大的。它是计算机科学的一个分支，以往的解析几何，是用代数的方法，建立坐标系去解决问题，但是很多时候需要付出一些代价，比如精度误差，而计算几何更多的是从几何角度，用向量的方法来尽量减少精度误差，例如：将除法转化为乘法、避免三角函数等近似运算等等。
9 l# ~# X9 M. _2 @$ V如果一个比赛中，有一道计算几何的题，那么至少，它不会是一道水题。
; Y& H0 G* y5 W2 I1、double 代替 float0 j0 N  i3 V! C0 A3 _3 S, E
c++ 中 double 的精度高于 float，对精度要求较高的问题，务必采用 double；
" L6 f! U1 l; Y- _: X* T2、浮点数判定. C/ J3 n; G1 n. A3 o: }
由于浮点数（小数）中是有无理数的，即无限不循环小数，也就是小数点后的位数是无限的，在计算机存储的时候不可能全部存下来，一定是近似的存储的，所以浮点数一定是存在精度误差的（实际上，就算是有理数，也是存在误差的，这和计算机存储机制有关，这里不再展开，有兴趣可以参见我博客的文章：C++ 浮点数精度判定）；
8 a$ D( X- `+ N2 U2 m3 _3 E+ D- C两个浮点数是否相等，可以采用两数相减的绝对值小于某个精度来实现：
6 J2 M, o) D! F$ dconst double eps = 1e-8;5 }9 Q5 P9 s& p& d1 z
bool EQ(double a, double b) {
. W. A7 y, k: a$ r return fabs(a - b) < eps;) |  p1 n# ^. X& v# v6 T* N
}6 z) a# k; _# p* R$ a
1
2 c0 Y# |5 t% x8 d- R2" E9 S+ R( v, ~: D7 N, P4 H. k
3
( V& K" L) {0 T7 U0 p; }4 {/ x' A41 @# n, Z: x$ _; f3 E2 y3 O
并且可以用一个三值函数来确定某个数是零、大于零还是小于零：- j, T4 i8 a* ]9 P" x8 P6 V
int threeValue(double d) {
+ O, `8 d, [" o( N8 L4 C4 u1 f3 B if (fabs(d) < eps)
4 ]4 U2 v" Q8 j; ?0 j- ^5 T& ?       return 0;  O6 ]+ c8 m; ^6 F+ i, o, w% q
return d > 0 ? 1 : -1;" b! F) [- r4 V- Y
}
. q1 Y) T: i% R15 [  M3 Q6 m+ K' K1 y
2
7 {. o' s5 p8 H% x2 x9 Q30 g! P8 j% E! `! ^
4
* V6 r- u* |( B+ s8 e$ {5
# Z6 I' M7 ?- @; |5 |0 U% ?3、负零判定
$ d' H" Q8 b! L( j" _因为精度误差的存在，所以在输出的时候一定要注意，避免输出 -0.00：
8 b* O6 k% @+ L; X4 }8 ^ double v = -0.0000000001;( K% w; y/ X, v2 y) r8 m
printf("%.2lf\n", v);
3 o* v5 t" A5 {* ^5 u1+ W: G+ U. q. ~5 z$ p" M, O0 b
2
: Q% e- c0 e  R% b( Z避免方法是先通过三值函数确定实际值是否为0，如果是0，则需要取完绝对值后再输出：8 a0 H' ]' U( g$ |, U5 L6 J
double v = -0.0000000001;
) j7 }) ~2 t) @6 h5 r& t+ E if(threeValue(v) == 0) {, U+ K) y8 {* L4 Z. {$ N+ M4 C
      v = fabs(v);8 n3 {9 H) ^2 G- z$ H7 \3 `
}
% Y$ k/ T2 i* z) i$ ?5 [$ k% n3 B printf("%.2lf\n", v);
$ {/ G( U/ v3 V6 Z7 r, Y" ?) t3 t, e1
& h3 ^! _  v, h# x. T* s; V5 {0 Q2
. Y7 \( I% ^' C3$ r8 M$ K" B, v0 O+ C4 G' a
4( [! L  k9 L( ?% ~/ f9 a# r
5
% D. W7 z  _* D9 u2 S3 f4、避免三角函数、对数、开方、除法等
! }. F; J5 d! y8 Oc++ 三角函数运算方法采用的是 CORDIC算法，一种利用迭代的方式进行求解的算法，其中还用到了开方运算，所以实际的算力消耗还是很大的，在实际求解问题的过程中，能够避免不用就尽量不用。( M8 m. G/ E  H8 v5 U: Q' f
除法运算会带来精度误差，所以能够转换成乘法的也尽量转换为乘法运算。! }5 R8 U7 W) H5 e" o3 l" n
5、系统性的学习$ D7 J" c% c; p* o$ ^
基础知识：点、向量、叉乘、点乘、旋转、线段、线段判交、三角形面积；
  G6 d% ]! t" A9 E进阶知识：多边形面积、凸多边形判定、点在多边形内判定；
9 e1 @: }* d& O2 U/ Z6 Z2 g! b3 W相关算法：二维凸包、三维凸包、旋转卡壳、多边形面积交、多边形面积并、多边形面积异或、多边形和圆的面积交、半平面交、最小覆盖圆、最小包围球、模拟退火。1 W- b/ u' ?) Y9 @- m: `

4 i" B) U) z* u. `/ ~$ q; V+ |% D# ^
4 R" k" X  {8 p9 O8 m: Q& p学习计算几何，最好是系统性的，刷题的过程中不断提炼出自己的模板。
" l# G, I5 L) ^2 f4）数论6 B1 ]2 v' J+ i1 E
刷题的时候遇到不会的数论题，真的是很揪心，从头学起吧，内容实在是太多了，每个知识点都要证明吃透，不然下次遇到还是不会；不学吧，又不甘心，就是单纯的想把这个题过了，真是进退两难！
5 n6 W' r6 \! s4 G数论对一个人的数学思维要求较高，但是一般也是一些固定的模式，所以把模板整理出来很重要。
* {- N: X( D: Q+ b当然，数论也有简单问题，一般先做一些入门题提升信心。8 [, ?7 [9 g! T. G* |3 g: Q" S( k# R
1、数论入门# Y: O+ t+ z3 B# U" _6 V" W8 Q
主要是一些基本概念，诸如：
1 [" S1 v4 R. o整除性、素数与合数、素数判定、素数筛选法、因数分解、算术基本定理、因子个数、因子和、最大公约数 (GCD) 和最小公倍数 (LCM)、辗转相除、同余、模运算、快速幂取模、循环节；
7 g0 A7 u- w+ F  T7 D3 r2、数论四大定理* g# ~$ \, v3 ~2 f) F+ O
这四个定理学完，可以KO很多题：8 Q6 c, L& F% h
欧拉定理、中国剩余定理、费马小定理、威尔逊定理( X7 ?& {3 h# y
3、数论进阶
: n) ]$ n& c! Z+ X) Y# o( A系统性的学习，基本也就这些内容了：7 v/ B: P2 m! w  i* x! W  _
扩展欧几里得、逆元、欧拉函数、同余方程组、扩展欧拉定理、RSA、卢卡斯定理、整数分块、狄利克雷卷积、莫比乌斯反演、大数判素、大数因子分解、大步小步离散对数等等。
+ |2 A9 @# I0 ?5）字符串匹配- o1 [5 z3 b% K8 q+ t  C% R
字符串匹配学习路线比较明确。7 |$ T5 L. a3 T3 p2 q# b& w
先学习前缀匹配：字典树。
/ q8 t  F' M) A( |( `2 o/ i然后可以简单看一下回文串判定算法：Manacher。7 Q- n. ]3 x9 M: _8 i
以及经典的单字符串匹配算法：KMP。/ e1 {. W2 D! P$ @1 b0 G+ s& G
实际上平时最常用的还是 BM 算法，而ACM中基本不考察。
+ K4 |2 L( I) {5 Y. _5 B然后就是较为高阶的前缀自动机、后缀数组、后缀树、后缀自动机了。
. a0 p  Y( l) L0 J0 l/ S7 c/ A关于算法学习路线的内容到这里就结束了。
, H3 C7 |$ `2 H1 n" U9 Q1 ]9 ^如果还有不懂的问题，可以想方设法找到作者的微信进行在线咨询。
4 q& D! p6 O5 h7 ^8 B参考资料* X: J0 d$ `/ N  N
【阶段一】C语言学习资料：《光天化日学C语言》（日更）
! w5 N& D2 n- w9 G% W6 V3 p" n, e【阶段二】C语言例题：《C语言入门100例》（日更）
; Z/ @4 {8 k7 |0 f- [【阶段三】算法入门题集：《LeetCode算法全集》（日更）
( Z$ {8 E; F: h( O8 E" C4 C+ y【阶段四】算法进阶：《夜深人静写算法》（周更）
) i" {& P! ~6 P7 D: H& S7 ?% K————————————————
) x+ Y" {- h+ H版权声明：本文为CSDN博主「英雄哪里出来」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" n9 N) h/ l9 S, a7 T: O  q' d/ m3 P原文链接：https://blog.csdn.net/WhereIsHeroFrom/article/details/118382228
" U2 j- L0 s0 m! [* U
: d1 v7 ?5 R1 R* }( c# i" n3 {" T" n& Q7 Y