大家好，又见面了，我是你们的朋友全栈君。

?饭不食，水不饮，题必须刷?




C语言免费动漫教程，和我一起打卡！


?《光天化日学C语言》?




LeetCode 太难？先看简单题！


?《C语言入门100例》?




数据结构难？不存在的！


?《画解数据结构》?




闭关刷 LeetCode，剑指大厂Offer！


?《LeetCode 刷题指引》?




LeetCode 太简单？算法学起来！


?《夜深人静写算法》?

前言

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

1、基础语法学习

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

1）HelloWorld

• 无论是 Java、Python、C/C++，想要上手一门语言，第一步一定是 HelloWorld，先不要急着去配环境。如果环境配了几个小时，可能一开始的雄心壮志就被配环境的过程消磨殆尽，更加不要谈日后的丰功伟业了。

2）让自己产生兴趣

• 所以，我们需要让这件事情从一开始就变得 有趣，这样才能坚持下去。比如找一个相对较为有趣的教程，这里我会推荐这个：《光天化日学C语言》。听名字就比较搞笑，可能作者本身也不是什么正经人，哈哈哈！虽然不能作为一个严谨的教程去学，起码可以对搞笑的内容先产生兴趣。从而对于语言本身有学习下去的动力。
• 刚才提到的这个系列，可以先收藏起来。回头再去看，它讲述的是 对白式 的 C语言教学，从最简单的输出 HelloWorld 这个字符串开始讲起，逐渐让读者产生对C语言的兴趣。这个系列的作者是前 WorldFinal 退役选手，一直致力于 将困难的问题讲明白 。我看了他的大部分教程，基本都能一遍看懂。算了，不装了，摊牌了，因为我就是这个作者。

3）目录是精髓

• 然后，我们大致看下你选择的教程的前几个章节，那些标题是否有你认知以外的名词出现，比如以这个思维导图为例。
• 如果你觉得这些名词中有 3 / 4 以上是没有什么概念的。那么，可能需要补齐一些数学、计算机方面的基础知识。反之，我们就可以继续下一步了。

4）习惯思考并爱上它

• 只要对一件事情养成习惯以后，你就会发现，再难的事情，都只是一点一点积累的过程。重要的是，每天学习的过程一定要吃透，养成主动思考的好习惯。因为，越到后面肯定是越难的，如果前期不养成习惯，后面很可能心有余而力不足。
• 就像刷题，一旦不会做就去找解题报告，最后就养成了看解题报告才会做题的习惯。当然这也是一种习惯，只不过不是一种好习惯罢了。

5）实践是检验真理的唯一标准

• 光看教程肯定是不行的，写代码肯定还是要动手的，因为有些语法你看一遍，必定忘记。但是写了几遍，永世难忘。这或许就是写代码的魅力所在吧。
• 所以，记得多写代码实践哟 (＾Ｕ＾)ノ~ＹＯ

6）坚持其实并没有那么难

• 每天把教程上的内容，自己在键盘上敲一遍，坚持一天，两天，三天。你会发现，第四天就变成了习惯。所以坚持就是今天做了这件事情，明天继续做。

7）适当给予正反馈

• 然而，就算再有趣的教程，看多了都会乏味，这是人性决定的，你我都逃不了。能够让你坚持下去的只有你自己，这时候，适当给予自己一些正反馈就显得尤为重要。比如，可以用一张表格将自己的学习计划记录下来，然后每天都去分析一下自己的数据。
• 当然，你也可以和我一样，创建一个博客，然后每天更新博文，就算没有内容，也坚持日更，久而久之，你会发现，下笔如有神，键盘任我行！更新的内容，可以是自己的学习笔记，心路历程 等等。
• 看着每天的粉丝量呈指数级增长，这是全网对你的认可，应该没有什么会是比这个更好的正反馈了。
• 那么，至此，不知道屏幕前的你感想如何，反正正在打字的我已经激情澎湃了。已经全然忘记这一章是要讲C语言基础的了！
• 介于篇幅，我会把C语言基础的内容，放在这个专栏 《光天化日学C语言》 里面去讲，一天更新一篇，对啊，既然说了要坚持，要养成习惯，我当然也要做到啦~如果你学到了哪一章，可以在评论区评论 “打卡” ，也算是一种全网见证嘛！
• 我也很希望大家的学习速度能够超越我的更新速度。

2、语法配套练习

• 学习的过程中，做题当然也是免不了的，还是应征那句话：实践是检验真理的唯一标准。
• 而这里的题库，是我花了大量时间，搜罗了网上各大C语言教程里的例题，总结出来的思维导图，可以先大致看一眼：

• 从数学基础、输入输出、数据类型、循环、数组、指针、函数、位运算、结构体、排序 等几个方面，总结出的具有概括性的例题 100 道 《C语言入门100例》，目前还在更新中。
• 这里可以列举几个例子：

1、例题1：交换变量的值

一、题目描述

  循环输入，每输入两个数 $a$ 和 $b$，交换两者的值后输出 $a$ 和 $b$。当没有任何输入时，结束程序。

二、解题思路

难度：?⚪⚪⚪⚪

• 这个题的核心是考察如何交换两个变量的值，不像 python，我们可以直接写出下面这样的代码就实现了变量的交换。

a, b = b, a

• 在C语言里，这个语法是错误的。
• 我们可以这么理解，你有两个杯子 $a$ 和 $b$，两个杯子里都盛满了水，现在想把两个杯子里的水交换一下，那么第一个想到的方法是什么？

当然是再找来一个临时杯子：
  1）先把 $a$ 杯子的水倒进这个临时的杯子里；
  2）再把 $b$ 杯子的水倒进 $a$ 杯子里；
  3）最后把临时杯子里的水倒进 $b$ 杯子；

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

三、代码详解

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)$ tmp = a;表示把 $a$ 杯子的水倒进这个临时的杯子里；
• $(2)$ a = b;表示把 $b$ 杯子的水倒进 $a$ 杯子里；
• $(3)$ b = tmp;表示把临时杯子里的水倒进 $b$ 杯子里；
• 这三步，就实现了变量 $a$ 和 $b$ 的交换。

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)$ a = a + b;执行完毕后，现在最新的a的值变成原先的a + b的值；
• $(2)$ b = a - b;执行完毕后，相当于b的值变成了a + b - b，即原先a的值；
• $(3)$ a = a - b;执行完毕后，相当于a的值变成了a + b - a，即原先b的值；
• 从而实现了变量a和b的交换。

3、正确解法3：引入异或运算

• 首先，介绍一下C语言中的^符号，代表的是异或。
• 二进制的异或，就是两个数转换成二进制表示后，按照位进行以下运算：

• 也就是对于 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)$ 这两句话，相当于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;
}

• 你学废了吗 ?？

2、例题2：整数溢出

一、题目描述

  先输入一个 $t(t\le 100)$，然后输入 $t$ 组数据。每组输入为 4 个正整数 $a,b,c,d(0\le a,b,c,d\le 2^{62})$，输出 $a+b+c+d$ 的值。

二、解题思路

难度：??⚪⚪⚪

• 这个问题考察的是对补码的理解。
• 仔细观察题目给出的四个数的范围：$[0,2^{62}]$，这四个数加起来的和最大值为 $2^{64}$。而C语言中，long long的最大值为：$2^{63}-1$，就算是unsigned long long，最大值也只有$2^{64}-1$。
• 但是我们发现，只有当四个数都取得最大值 $2^{62}$ 时，结果才为 $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)$ 由于这题数据量较大，所有数据都需要用64位无符号整型。ull作为unsigned long long的别名；
• $(2)$ 用常量MAX表示 $2^{62}$，这里采用左移运算符直接实现 $2$ 是幂运算；

• 需要注意的是，由于 1 是int类型，所以需要对 1 进行强制转换。(ull)1等价于(unsigned long long)1；
• $(3)$ %llu是无符号64位整型的输入方式；
• $(4)$ 这里是对所有数都等于最大值的特殊判断，&&运算符的优先级低于==，所以这里不加括号也没事；
• $(5)$ 由于 $2^{64}$ 是无法用数字的形式输出的，所以我们提前计算机算好以后，用字符串的形式进行输出；
• $(6)$ 其它情况都在 $[0,2^{64}-1]$ 范围内，直接相加输出即可。

3、数据结构

• 《C语言入门100例》上的例题，如果能理解前面 25 道，那基本C语言的学习就可以告一段落了，接下来就要开始我们的数据结构的学习了。

1、什么是数据结构

• 你可能听说过 数组、链表、队列、栈、堆、二叉树、图，没错，这些都是数据结构，但是你要问我什么是数据结构，我突然就一脸懵逼了。
• 如果一定要给出一个官方的解释，那么它就是：

计算机存储、组织数据的方式。相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。往往同高效的检索算法和索引技术有关。

• 是不是还不如说它是堆，是栈，是队列呢？
• 是这样的，我们学习的过程中，跳过一些不必要的概念，能够节省我们更多的时间，从而达到更好的效果，当你还在理解数据结构是什么的时候，可能人家已经知道了栈有哪些操作了。

2、数据结构和算法的关系

• 很多同学搞不明白，数据结构与算法有哪些千丝万缕的关系？甚至有些同学以为算法里本身就包含了数据结构。
• 数据结构主要讲解数据的组织形式，比如链表，堆，栈，队列。
• 而算法，则注重的是思想，比如链表的元素怎么插入、删除、查找？堆的元素怎么弹出来的？栈为什么是先进后出？队列又为什么是先进先出？
• 讲得直白一点，数据结构是有实体的，算法是虚拟的；数据结构是物质上的，算法是精神上的。当然，物质和精神 缺一不可。

3、数据结构概览

• 周末花了一个下午整理的思维导图，数据结构：
  
• 数据结构相关入门可以参考以下文章：数据结构入门

4、算法入门

• 算法入门，其实就是要开始我们的刷题之旅了。先给出思维导图，然后一一介绍入门十大算法。
  
• 十个最基础的算法可以参考以下文章：算法入门精选

5、算法进阶

• 算法进阶这块是我打算规划自己未来十年去完成的一个项目，囊括了 大学生ACM程序设计竞赛、高中生的OI竞赛、LeetCode 职场面试算法 的算法全集，也就是之前网络上比较有名的 《夜深人静写算法》 系列，这可以说是我自己对自己的一个要求和目标吧。
• 如果只是想进大厂，那么 算法入门 已经足够了，不需要再来看算法进阶了，当然如果对算法有浓厚兴趣，也欢迎和我一起打卡。由于内容较难，工作也比较忙，所以学的也比较慢，一周基本也只能更新一篇。

这个系列主要分为以下几个大块内容：
  1）图论
  2）动态规划
  3）计算几何
  4）数论
  5）字符串匹配
  6）高级数据结构（课本上学不到的）
  7）杂项算法

• 先来看下思维导图，然后我大致讲一下每一类算法各自的特点，以及学习方式：

1）图论

1、搜索概览

• 图论主要围绕搜索算法进行展开。搜索算法的原理就是枚举。利用计算机的高性能，给出人类制定好的规则，枚举出所有可行的情况，找到可行解或者最优解。
  
• 比较常见的搜索算法是 深度优先搜索（又叫深度优先遍历） 和 广度优先搜索（又叫广度优先遍历 或者 宽度优先遍历）。各种图论的算法基本都是依靠这两者进行展开的。

2、深度优先搜索

• 深度优先搜索一般用来求可行解，利用剪枝进行优化，在树形结构的图上用处较多；而广度优先搜索一般用来求最优解，配合哈希表进行状态空间的标记，从而避免重复状态的计算；
• 原则上，天下万物皆可搜，只是时间已惘然。搜索会有大量的重复状态出现，这里的状态和动态规划的状态是同一个概念，所以有时候很难分清到底是用搜索还是动态规划。
• 但是，大体上还是有迹可循的，如果这个状态不能映射到数组被缓存下来，那么大概率就是需要用搜索来求解的。
• 如图所示，代表的是一个深度优先搜索的例子，红色实箭头表示搜索路径，蓝色虚箭头表示回溯路径。
  
• 红色块表示往下搜索，蓝色块表示往上回溯，遍历序列为：

	0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6

• 同样，搜索的例子还有：
  
• 计算的是利用递归实现的 $n$ 的阶乘。

3、记忆化搜索

• 对于斐波那契函数的求解，如下所示：
• $$f(n)=\{\begin{array}{ll}1& (n=0)\\ 1& (n=1)\\ f(n-1)+f(n-2)& (n>2)\end{array}$$
• 对于 $f(5)$ 的求解，程序调用如下：
  
• 这个过程用到了很多重复状态的搜索，我们需要将它优化，一般将一些状态缓存起来。
• 我们通过一个动图来感受一下：
  
• 当第二次需要计算 $f(2)$ 和 $f(3)$ 时，由于结果已经计算出来并且存储在 $h[2]$ 和 $h[3]$ 中，所以上面这段代码的fib != inf表达式为真，直接返回，不再需要往下递归计算，这样就把原本的 “递归二叉树” 转换成了 “递归链”， 从而将原本指数级的算法变成了多项式级别。
• 这就是记忆化搜索，像这种把状态缓存起来的方法，就是动态规划的思想了。

4、广度优先搜索

• 单向广搜就是最简化情况下的广度优先搜索（Breadth First Search），以下简称为广搜。游戏开发过程中用到的比较广泛的 A* 寻路，就是广搜的加强版。
• 我们通过一个动图来对广搜有一个初步的印象。

• 从图中可以看出，广搜的本质还是暴力枚举。即对于每个当前位置，枚举四个相邻可以行走的方向进行不断尝试，直到找到目的地。有点像洪水爆发，从一个源头开始逐渐蔓延开来，直到所有可达的区域都被洪水灌溉，所以我们也把这种算法称为 FloodFill。
• 那么，如何把它描述成程序的语言呢？这里需要用到一种数据结构 —— 队列。
• 这时候，算法和数据结构就完美结合了。

2）动态规划

动态规划算法三要素：
  ①所有不同的子问题组成的表；
  ②解决问题的依赖关系可以看成是一个图；
  ③填充子问题的顺序（即对②的图进行拓扑排序，填充的过程称为状态转移）；

• 如果子问题的数目为 $O(n^t)$，每个子问题需要用到 $O(n^e)$ 个子问题的结果，那么我们称它为 tD/eD 的问题，于是可以总结出四类常用的动态规划方程：（下面会把opt作为取最优值的函数（一般取 $min$ 或 $max$ ）, $w(j,i)$为一个实函数，其它变量都可以在常数时间计算出来）。

1、1D/1D

• $$d[i]=opt(d[j]+w(j,i)|0<=i<j)$$
• 状态转移如图四所示（黄色块代表$d[i]$，绿色块代表$d[j]$）：
  
• 这类状态转移方程一般出现在线性模型中。

2、2D/0D

• $$d[i][j]=opt(d[i-1][j]+x_i,d[i][j-1]+y_j,d[i-1][j-1]+z_{ij})$$
• 状态转移如图四所示：
  
• 比较经典的问题是最长公共子序列、最小编辑距离。
• 有关最长公共子序列的问题，可以参考以下文章：夜深人静写算法（二十一）- 最长公共子序列
  
• 有关最小编辑距离的问题，可以参考以下文章：夜深人静写算法（二十二）- 最小编辑距离

3、2D/1D

• $$d[i][j]=w(i,j)+opt(d[i][k-1]+d[k][j])$$
• 区间模型常用方程，如图所示：
  
• 另外一种常用的 2D/1D 的方程为：
• $$d[i][j]=opt(d[i-1][k]+w(i,j,k)|k<j)$$
• • 区间模型的详细内容可以参考以下这篇文章：夜深人静写算法（二十七）- 区间DP

4、2D/2D

• $$d[i][j]=opt(d[i^{\prime }][j^{\prime }]+w(i^{\prime },j^{\prime },i,j)|0<=i^{\prime }<i,0<=j^{\prime }<j)$$
• 如图所示：
  
• 常见于二维的迷宫问题，由于复杂度比较大，所以一般配合数据结构优化，如线段树、树状数组等。
• 对于一个tD/eD 的动态规划问题，在不经过任何优化的情况下，可以粗略得到一个时间复杂度是$O(n^{t+e})$，空间复杂度是$O(n^t)$ 的算法，大多数情况下空间复杂度是很容易优化的，难点在于时间复杂度，后续章节将详细讲解各种情况下的动态规划优化算法。

3）计算几何

• 计算几何的问题是代码量最大的。它是计算机科学的一个分支，以往的解析几何，是用代数的方法，建立坐标系去解决问题，但是很多时候需要付出一些代价，比如精度误差，而计算几何更多的是从几何角度，用向量的方法来尽量减少精度误差，例如：将除法转化为乘法、避免三角函数等近似运算 等等。
• 如果一个比赛中，有一道计算几何的题，那么至少，它不会是一道水题。

1、double 代替 float

• c++ 中 double 的精度高于 float，对精度要求较高的问题，务必采用 double；

2、浮点数判定

• 由于浮点数（小数）中是有无理数的，即无限不循环小数，也就是小数点后的位数是无限的，在计算机存储的时候不可能全部存下来，一定是近似的存储的，所以浮点数一定是存在精度误差的（实际上，就算是有理数，也是存在误差的，这和计算机存储机制有关，这里不再展开，有兴趣可以参见我博客的文章：C++ 浮点数精度判定）；
• 两个浮点数是否相等，可以采用两数相减的绝对值小于某个精度来实现：

const double eps = 1e-8;
bool EQ(double a, double b) { 
   
    return fabs(a - b) < eps;
}

• 并且可以用一个三值函数来确定某个数是零、大于零还是小于零：

int threeValue(double d) { 
   
    if (fabs(d) < eps)
        return 0;
    return d > 0 ? 1 : -1;
}

3、负零判定

• 因为精度误差的存在，所以在输出的时候一定要注意，避免输出 -0.00：

    double v = -0.0000000001;
    printf("%.2lf\n", v);

• 避免方法是先通过三值函数确定实际值是否为0，如果是0，则需要取完绝对值后再输出：

    double v = -0.0000000001;
    if(threeValue(v) == 0) { 
   
        v = fabs(v);
    }
    printf("%.2lf\n", v);

4、避免三角函数、对数、开方、除法等

• c++ 三角函数运算方法采用的是 CORDIC算法，一种利用迭代的方式进行求解的算法，其中还用到了开方运算，所以实际的算力消耗还是很大的，在实际求解问题的过程中，能够避免不用就尽量不用。
• 除法运算会带来精度误差，所以能够转换成乘法的也尽量转换为乘法运算。

5、系统性的学习

基础知识：点、向量、叉乘、点乘、旋转、线段、线段判交、三角形面积；
进阶知识：多边形面积、凸多边形判定、点在多边形内判定；
相关算法：二维凸包、三维凸包、旋转卡壳、多边形面积交、多边形面积并、多边形面积异或、多边形和圆的面积交、半平面交、最小覆盖圆、最小包围球、模拟退火。

• 学习计算几何，最好是系统性的，刷题的过程中不断提炼出自己的模板。

4）数论

• 刷题的时候遇到不会的数论题，真的是很揪心，从头学起吧，内容实在是太多了，每个知识点都要证明吃透，不然下次遇到还是不会；不学吧，又不甘心，就是单纯的想把这个题过了，真是进退两难！
• 数论对一个人的数学思维要求较高，但是一般也是一些固定的模式，所以把模板整理出来很重要。
• 当然，数论也有简单问题，一般先做一些入门题提升信心。

1、数论入门

• 主要是一些基本概念，诸如：
• 整除性、素数与合数、素数判定、素数筛选法、因数分解、算术基本定理、因子个数、因子和、最大公约数 (GCD) 和 最小公倍数 (LCM)、辗转相除、同余、模运算、快速幂取模、循环节；

2、数论四大定理

• 这四个定理学完，可以KO很多题：
• 欧拉定理、中国剩余定理、费马小定理、威尔逊定理

3、数论进阶

• 系统性的学习，基本也就这些内容了：
• 扩展欧几里得、逆元、欧拉函数、同余方程组、扩展欧拉定理、RSA、卢卡斯定理、整数分块、狄利克雷卷积、莫比乌斯反演、大数判素、大数因子分解、大步小步离散对数等等。

5）字符串匹配

• 字符串匹配学习路线比较明确。
• 先学习前缀匹配：字典树。
• 然后可以简单看一下回文串判定算法：Manacher。
• 以及经典的单字符串匹配算法：KMP。
• 实际上平时最常用的还是 BM 算法，而ACM中基本不考察。
• 然后就是较为高阶的 前缀自动机、后缀数组、后缀树、后缀自动机了。

• 关于 《画解数据结构》学习路线 的内容到这里就结束了。
• 如果还有不懂的问题，可以 「 想方设法 」找到作者的「 联系方式 」 ，随时线上沟通。