当我们遇到一个实际问题时，首先需要解决两件事：

（1）如何将数据存储在计算机中；

（2）用什么方法和策略解决问题。

前者是数据结构，后者是算法。只有数据结构没有算法，相当于只把数据存储到计算机中，而没有有效的方法去处理，就像一幢只有框架的烂尾楼；若只有算法，没有数据结构，就像沙漠里的海市蜃楼，只不过是空中楼阁罢了。

数据是一切能输入计算机中的信息的总和，结构是指数据之间的关系。数据结构就是将数据及其之间的关系有效地存储在计算机中并进行基本操作。算法是对特定问题求解步骤的一种描述，通俗讲就是解决问题的方法和策略。

在遇到一个实际问题时，要充分利用自己所学的数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效地实现。这就是Niklaus Wirth教授所说的：“数据结构+算法＝程序”。

高校的计算机专业为本科生都开设了数据结构课程，它是计算机学科知识结构的核心和技术体系的基石，在研究生考试中也是必考科目。随着科学技术的飞速发展，数据结构的基础性地位不仅没有动摇，反而因近年来算法工程师的高薪形势，而得到了业内空前的重视。很多人认为基本的数据结构及操作已经在高级语言（如C++、Java语言）中封装，栈、队列、排序、优先队列等都可以直接调用库函数，学会怎么调用就好了，为什么要重复“造轮子”？那么到底有没有必要好好学习数据结构呢？

学习数据结构有什么用

（1）学习有效存储数据的方法。很多学生在学习数据结构时，问我要不要把单链表插入、删除背下来？要不合上书就不会写了。我非常诧异，为什么要背？理工科技术知识很少需要记忆的，是用的，用的！学习知识不能只靠死记硬背，更重要的是学习处理问题的方法。如何有效地存储数据，不同的数据结构产生什么样的算法复杂性，有没有更好的存储方法提高算法的效率？

（2）处理具有复杂关系的数据。现实中很多具有复杂关系的数据无法通过简单的库函数调用实现。如同现在很多芯片高度集成，完全不需要知道芯片内部如何，直接使用就行了。但是，如果在现实中遇到一个复杂问题，现有的芯片根本无法解决，或者一个芯片只能完成其中一个功能，而我们需要的是完成该复杂问题的一个集成芯片，这时就需要运用所学的数据结构知识来高效处理具有复杂关系的数据。

（3）提高算法效率。很多问题的基础数据结构运行效率较低，需要借助高级数据结构或通过改进数据结构来提高算法效率。

通过学习数据结构，更加准确和深刻地理解不同数据结构之间的共性和联系，学会选择和改进数据结构，高效地设计并实现各种算法，这才是数据结构的精髓。

数据结构为什么那么难

网络上太多的同学吐槽被“虐”，如“滔滔江水连绵不绝”，数据结构太难了！真的很难吗？其实数据结构只是讲了3部分内容：线性结构、树和图。到底难在哪里呢？我通过调查，了解到数据结构难学大概有以下4个原因。

（1）无法接受它的描述方式。数据结构的描述大多是抽象的形式，我们习惯了使用自然语言表达，难以接受数据结构的抽象表达。不止一个学生问我，书上的“ElemType”到底是什么类型？运行时怎么经常提示错误。它的意思就是“元素类型”，只是这样来描述，你需要什么类型就写什么类型，例如int。这样的表达方式会让不少人感到崩溃。

（2）不知道它有什么用处。尽管很多人学习数据结构，但目的各不相同。有的人是应付考试，有的人是参加算法竞赛需要，而很多人不太清楚学习数据结构有什么用处，迷迷糊糊看书、做题、考试。

（3）体会不到其中的妙处。由于教材、教师等各种因素影响，很多学生没有体会到数据结构处理数据的妙处，经常为学不会而焦头烂额，学习重在体会其中的乐趣，有乐趣才有兴趣，兴趣是最好的驱动力。

（4）语言基础不好。我一直强调先看图解，理清思路，再上机。可还是有很多同学已经理解了思路后，因为缺少main函数，输入/输出格式不对，缺少括号等各种语言问题卡壳，而这一切都被戴上了“数据结构太难了”的大帽子。

数据结构学习秘籍

在讲学习秘籍之前，我们首先了解一下数据结构学习的3种境界。

（1）会数据结构的基本操作。学会各种数据结构的基本操作，即取值、查找、插入、删除等，是最基础的要求。先看图解，理解各种数据结构的定义，操作方法，然后看代码，尝试自己动手上机运行，逐渐掌握基本操作。在初学时，要想理解数据结构，一定要学会画图。通过画图形象表达，能更好地体会其中的数据结构关系。因此，初学阶段学习利器是：画图、理解、画图。

（2）会利用数据结构解决实际问题。在掌握了书中的基本操作之后，就可以尝试利用数据结构解决一些实际问题了。先学经典应用问题的解决方法，体会数据结构的使用方法，再做题，独立设计数据结构解决问题。要想熟练应用就必须做大量的题，在做题的过程中体会其中的方法。最好进行专项练习，比如线性表问题、二叉树问题、图问题。这一阶段的学习利器是：做题、反思、做题。

（3）熟练使用和改进数据结构，优化算法。这是最高境界了，也是学习数据结构的精髓所在，单独学习数据结构是无法达到这种境界的。数据结构与算法相辅相成，需要在学习算法的过程中慢慢修炼。在学习算法的同时，逐步熟练应用、改进数据结构，慢慢体会不同数据结构和算法策略的算法复杂性，最终学会利用数据结构改进和优化算法。这一阶段已经在数据结构之上，可以通过在ACM测试系统上刷各种算法题，体会数据结构在算法设计中的应用。这一阶段的学习利器是：刷题、总结、刷题。

数据结构与算法书籍推荐

数据结构与算法之美（全彩印刷）

一些经典的数据结构和算法图书，偏重理论，读者学起来可能感觉比较枯燥。一些趣谈类的数据结构和算法图书，虽然容易读懂，但往往内容不够全面。另外，很多数据结构和算法图书缺少真实的开发场景，读者很难将理论和实践相结合。

为了解决上述问题，本书全面、系统地讲解了常用、常考的数据结构和算法，并结合 300多幅图和上百段代码，让内容变得更加通俗易懂。同时，对于每个知识点，本书结合真实的应用场景进行讲解，采用一问一答的讲解模式，让读者不仅可以掌握理论知识，还可以掌握如何将数据结构和算法应用到实际的开发工作中。

本书分为11章。第1章介绍复杂度分析方法。第2章介绍数组、链表、栈和队列这些基础的线性表数据结构。第3章介绍递归编程技巧、8种经典排序、二分查找及二分查找的变体问题。第4章介绍哈希表、位图、哈希算法和布隆过滤器。第5章介绍树相关的数据结构，包括二叉树、二叉查找树、平衡二叉查找树、递归树和B+树。第6章介绍堆，以及堆的各种应用，包括堆排序、优先级队列、求Top K、求中位数和求百分位数。第7章介绍跳表、并查集、线段树和树状数组这些比较高级的数据结构。第8章介绍字符串匹配算法，包括BF算法、RK算法、BM算法、KMP算法、Trie树和AC自动机。第9章介绍图及相关算法，包括深度优先搜索、广度优先搜索、拓扑排序、Dijkstra算法、Floyd算法、A*算法、Z小生成树算法、Z大流算法和Z大二分匹配等。第10章介绍4种算法思想，包括贪心、分治、回溯和动态规划。第11章介绍4个经典项目中的数据结构和算法的应用，包括Redis、搜索引擎、鉴权限流和短网址服务。另外，附录A为书中的思考题的解答。

数据结构 Python语言描述 第2版

本书主要介绍计算机编程中如下4个主要方面的内容。

（1）编程基础——数据类型、控制结构、算法开发以及通过函数进行程序设计，是解决计算机问题所需要掌握的基本思想。本书用Python编程语言介绍这些核心主题，旨在帮助你通过理解这些主题解决更广泛的问题。

（2）面向对象编程——面向对象编程是用于开发大型软件系统的主要编程范式。本书介绍OOP的基本原理，旨在让你能够熟练地应用它们。和其他教科书不同，本书会引导你开发一个专业的多项集类的框架，以说明这些原理。

（3）数据结构——大多数程序会依赖数据结构解决问题。在最具体的层级，数据结构包含数组以及各种类型的链接结构。本书介绍如何使用这些数据结构来实现各种类型的多项集结构（如栈、队列、列表、树、包、集合、字典和图），还会介绍如何使用复杂度分析来评估这些多项集的不同，进而实现在时间与空间上的权衡。

（4）软件开发生命周期——本书不会设单独的一两章去介绍软件开发技术，而是通过大量的案例全面概述这方面的内容。本书还会强调，编写程序通常并不是解决问题或软件开发里最困难或最具挑战性的部分。

趣学数据结构

本书包括10章。

• 第1章是基础知识，介绍数据结构基础和算法复杂性的计算方法。
• 第2～5章是线性结构，讲解线性表、栈和队列、字符串、数组等的基本操作和应用。
• 第6章是树形结构，讲解树、二叉树、线索二叉树、树和森林以及树的经典应用。
• 第7章是图形结构，讲解图的存储、遍历以及图的经典应用。
• 第8～9章是数据结构的基本应用，讲解查找、排序的方法和算法复杂性比较。
• 第10章是高级数据结构及其应用，讲解优先队列、并查集、B-树、B+树、红黑树等。

本书的每一章中都有大量图解，并给出数据结构的基本操作，最后结合实例帮助读者巩固相关知识点，力求学以致用、举一反三。

本文已收录于专栏 🌳《画解数据结构》🌳

🙉饭不食，水不饮，题必须刷🙉
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	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)$ 这两句话，相当于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$ 是幂运算；

数学	C语言
$2^n$	1<<n

• 需要注意的是，由于 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中基本不考察。
• 然后就是较为高阶的 前缀自动机、后缀数组、后缀树、后缀自动机了。

---

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

---

1️⃣前言：追忆我的刷题经历

  学习算法最好的方法就是刷题了，上大学的时候刷过一些，最近开始转战 LeetCode。

🔥让天下没有难学的算法🔥
C语言免费动漫教程，和我一起打卡！ 🌞《光天化日学C语言》🌞
入门级C语言真题汇总 🧡《C语言入门100例》🧡
几张动图学会一种数据结构 🌳《画解数据结构》🌳
组团学习，抱团生长 🌌《算法入门指引》🌌
竞赛选手金典图文教程 💜《夜深人静写算法》💜

2️⃣算法和数据结构的重要性

👪1、适用人群

• 这篇文章会从 「算法和数据结构」 零基础开始讲，所以，如果你是算法大神，可以尽情在评论区嘲讽我哈哈，目的当然是帮助想要涉足算法领域，或者正在找工作的朋友，以及将要找工作的大学生，更加有效快速的掌握算法思维，能够在职场面试和笔试中一展身手。
• 这篇文章中，我会着重讲解一些常见的 「算法和数据结构」 的设计思想，并且配上动图。主要针对面试中常见的问题和新手朋友们比较难理解的点进行解析。当然，后面也会给出面向算法竞赛的提纲，如果有兴趣深入学习的欢迎在评论区留言，一起成长交流。
• 零基础学算法的最好方法，莫过于刷题了。任何事情都是需要坚持的，刷题也一样，没有刷够足够的题，就很难做出系统性的总结。所以上大学的时候，我花了三年的时间来刷题， 工作以后还是会抽点时间出来刷题。

千万不要用工作忙来找借口，时间挤一挤总是有的。

• 我现在上班地铁上一个小时，下班地铁又是一个小时。比如这篇文章的起草，就是在 地铁 上完成的。如何利用这两个小时的时间，做一些有建设性的事情，才是最重要的。刷抖音一个小时过得很快，刷题也是同样的道理。
• 当然，每天不需要花太多时间在这个上面，把这个事情做成一个规划，按照长期去推进。反正也没有 KPI 压力，就当成是工作之余的一种消遣，还能够提升思维能力。何乐而不为！

所以，无论你是 小学生，中学生，高中OIer，大学ACMer，职场人士，只要想开始，一切都不会太晚！

🎾2、有何作用

• 我们平常使用的 智能手机、搜索引擎、网站、操作系统、游戏、软件、人工智能，都大量地应用了 「算法与数据结构」 的知识，以及平时你用到的各种库的底层实现，也是通过各种算法和数据结构组合出来的，所以可以说，有程序的地方，就有江湖 算法，有算法就一定会有对应的数据结构。
• 如果你只是想学会写代码，或许 「算法与数据结构」 并不是那么重要，但是想要往更深一步发展，「算法与数据结构」 是必不可少的。

  现在一些主流的大厂，在面试快结束的时候都会 奉上一道算法题，如果你敲不出来，可能你的 offer 年包就打了 七折，或者直接与 offer 失之交臂，都是有可能的（因为我自己也是万恶的面试官，看到候选人的算法题写不出来我也是操碎了心，但是我一般会给足容错，比如给三个算法题，挑一个写，任意写出一个都行）。

• 当然，它不能完全代表你的编码能力，因为有些算法确实是很巧妙，加上紧张的面试氛围，想不出来其实也是正常的，但是你能确保面试官是这么想的吗？我们要做的是十足的准备，既然决定出来，offer 当然是越高越好，毕竟大家都要养家糊口，房价又这么贵，如果能够在算法这一块取得先机，也不失为一个捷径。

所以，你问我算法和数据结构有什么用？我可以很明确的说，和你的年薪息息相关。

• 当然，面试中 「算法与数据结构」 知识的考察只是面试内容的一部分。其它还有很多面试要考察的内容，当然不是本文主要核心内容，这里就不做展开了。

📜3、算法简介

• 算法是什么东西？
• 它是一种方法，一种解决问题的方案。
• 举个例子，你现在要去上班，可以选择 走路、跑步、坐公交、坐地铁、自己开车 等等，这些都是解决方案。但是它们都会有一些衡量指标，让你有一个权衡，最后选择你认为最优的策略去做。
• 而衡量的指标诸如：时间消耗、金钱消耗、是否需要转车、是否可达 等等。

时间消耗就对应了：时间复杂度
金钱消耗就对应了：空间复杂度
是否可达就对应了：算法可行性

• 当然，是否需要转车，从某种程度上都会影响 时间复杂度 或者 空间复杂度。

🌲4、数据结构

• 对于实现某个算法，我们往往会用到一些数据结构。
• 因为我们通常不能一下子把数据处理完，更多的时候需要先把它们放在一个容器或者说缓存里面，等到一定的时刻再把它们拿出来。
• 这其实是一种 「空间换时间」 思想的体现， 恰当使用数据结构可以帮助我们高效地处理数据。
• 常用的一些数据结构如下：

数据结构	应用场景
数组	线性存储、元素为任意相同类型、随机访问
字符串	线性存储、元素为字符、结尾字符、随机访问
链表	链式存储、快速删除
栈	先进后出
队列	先进先出
哈希表	随机存储、快速增删改查
二叉树	对数时间增删改查，二叉查找树、线段树
多叉树	B/B+树 硬盘树、字典树 字符串前缀匹配
森林	并查集 快速合并数据
树状数组	单点更新，成段求和

• 为什么需要引入这么多数据结构呢？

  答案是：任何一种数据结构是不是 完美的。所以我们需要根据对应的场景，来采用对应的数据结构，具体用哪种数据结构，需要通过刷题不断刷新经验，才能总结出来。

3️⃣如何开始持续的刷题

• 有朋友告诉我，题目太难了，根本不会做，每次都是看别人的解题报告。

📑1、立军令状

• 所谓 「军令状」，其实就是给自己定一个目标，给自己树立一个目标是非常重要的，有 「目标才会有方向，有目标才会有动力，有目标才会有人生的意义」 。而军令状是贬义的，如果不达成就会有各种惩罚，所以其实你是心不甘情不愿的，于是这件事情其实是无法持久下去的。

事实证明，立军令状是不可取的。

• 啊这……所以我们还是要采用一些能够持久下去的方法。

👩‍❤️‍👩2、培养兴趣

• 为了让这件事情能够持久下去，一定要培养出兴趣，适时的给自己一些正反馈。正反馈的作用就是每过一个周期，如果效果好，就要有奖励，这个奖励机制可以自己设定，但是 「不能作弊」 ，一旦作弊就像单机游戏修改数值，流失是迟早的事。
• 举个例子，我们可以给每天制定一些 「不一样的目标和奖励」 ，比如下图所示：

刷题的第?天	目标题数	是否完成	完成奖励
1	1	？	攻击力 + 10
2	1	？	防御力 + 10
3	2	？	出去吃顿好的
4	2	？	攻击力 + 29
5	3	？	防御力 + 60
6	1	？	攻击力 + 20
7	4	？	出去吃顿好的
8	1	？	防御力 + 50

• 当然，这个完成奖励你可以自己定，总而言之，要是对你有诱惑的奖励才是有意义的。

🚿3、狂切水题

• 刚开始刷的 300 题一定都是 「水题」 ，刷 「水题」 的目的是让你养成一个每天刷题的习惯。久而久之，不刷题的日子会变得无比煎熬。当然，刷着刷着，你会发现，水题会越来越多，因为刷题的过程中，你已经无形中不断成长起来了。
• 至少这个方法我用过，非常灵验！推荐刷题从水题开始。

如果不知道哪里有水题，推荐：
   C语言入门水题：《C语言入门100例》
  C语言算法水题：《LeetCode算法全集》

💪🏻4、养成习惯

• 相信如果切了 300 个 「水题」 以后，刷题自然而然就成了习惯，想放弃都难。这个专业上讲，其实叫 沉没成本。有兴趣的可以自行百度，这里就不再累述了。

🈵5、一周出师

• 基本上如果能够按照这样的计划去执行，一周以后，一定会有收获，没有收获的话，可以来找我。

4️⃣简单数据结构的掌握

🚂1、数组

内存结构：内存空间连续
实现难度：简单
下标访问：支持
分类：静态数组、动态数组
插入时间复杂度：$O(n)$
查找时间复杂度：$O(n)$
删除时间复杂度：$O(n)$

🎫2、字符串

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

🎇3、链表

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

🌝4、哈希表

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

• 哈希表相关的内容，可以参考我的这篇文章：
• 夜深人静写算法（九）- 哈希表

👨‍👩‍👧5、队列

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

• 队列相关的内容，可以参考我的这篇文章：
• 夜深人静写算法（十）- 单向广搜

👩‍👩‍👦‍👦6、栈

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

• 栈相关的内容，可以参考我的这篇文章：
• 夜深人静写算法（十一）- 单调栈

🌵7、二叉树

优先队列 是 堆实现的，所以也属于 二叉树 范畴。它和队列不同，不属于线性表。
内存结构：内存结构一般不连续，但是有时候实现的时候，为了方便，一般是物理连续，逻辑不连续
实现难度：较难
下标访问：不支持
分类：二叉树 和 多叉树
插入时间复杂度：看情况而定
查找时间复杂度：理论上 $O(lo{g}_{2}n)$
删除时间复杂度：看情况而定

🌳8、多叉树

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

• 一种经典的多叉树是字典树，可以参考我的这篇文章：
• 夜深人静写算法（七）- 字典树

🌲9、森林

• 比较经典的森林是：并查集，可以参考我的这篇文章：
• 夜深人静写算法（五）- 并查集

🍀10、树状数组

• 树状数组是用来做 单点更新，成端求和 的问题的，有关于它的内容，可以参考：
• 夜深人静写算法（十三）- 树状数组

🌍11、图

内存结构：不一定
实现难度：难
下标访问：不支持
分类：有向图、无向图
插入时间复杂度：根据算法而定
查找时间复杂度：根据算法而定
删除时间复杂度：根据算法而定

1、图的概念

• 在讲解最短路问题之前，首先需要介绍一下计算机中图（图论）的概念，如下：
• 图 $G$ 是一个有序二元组 $(V,E)$，其中 $V$ 称为顶点集合，$E$ 称为边集合，$E$ 与 $V$ 不相交。顶点集合的元素被称为顶点，边集合的元素被称为边。
• 对于无权图，边由二元组 $(u,v)$ 表示，其中 $u,v\in V$。对于带权图，边由三元组 $(u,v,w)$ 表示，其中 $u,v\in V$，$w$ 为权值，可以是任意类型。
• 图分为有向图和无向图，对于有向图， $(u,v)$ 表示的是 从顶点 $u$ 到 顶点 $v$ 的边，即 $u\to v$；对于无向图，$(u,v)$ 可以理解成两条边，一条是 从顶点 $u$ 到 顶点 $v$ 的边，即 $u\to v$，另一条是从顶点 $v$ 到 顶点 $u$ 的边，即 $v\to u$；

2、图的存储

• 对于图的存储，程序实现上也有多种方案，根据不同情况采用不同的方案。接下来以图二-3-1所表示的图为例，讲解四种存储图的方案。
  

1）邻接矩阵

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

2）邻接表

• 邻接表是图中常用的存储结构之一，采用链表来存储，每个顶点都有一个链表，链表的数据表示和当前顶点直接相邻的顶点的数据$(v,w)$，即 顶点 和 边权。
• 它的优点是：对于稀疏图不会有数据浪费；缺点就是实现相对邻接矩阵来说较麻烦，需要自己实现链表，动态分配内存。
• 如图所示，$data$ 即 $(v,w)$ 二元组，代表和对应顶点 $u$ 直接相连的顶点数据，$w$ 代表 $u\to v$ 的边权，$next$ 是一个指针，指向下一个 $(v,w)$ 二元组。
  
• 在 C++ 中，还可以使用 vector 这个容器来代替链表的功能；

    vector<Edge> edges[maxn];

3）前向星

• 前向星是以存储边的方式来存储图，先将边读入并存储在连续的数组中，然后按照边的起点进行排序，这样数组中起点相等的边就能够在数组中进行连续访问了。
• 它的优点是实现简单，容易理解；缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序，带来了时间开销，实用性也较差，只适合离线算法。
• 如图所示，表示的是三元组 $(u,v,w)$ 的数组，$idx$ 代表数组下标。
  
• 那么用哪种数据结构才能满足所有图的需求呢？
• 接下来介绍一种新的数据结构 —— 链式前向星。

4）链式前向星

• 链式前向星和邻接表类似，也是链式结构和数组结构的结合，每个结点 $i$ 都有一个链表，链表的所有数据是从 $i$ 出发的所有边的集合（对比邻接表存的是顶点集合），边的表示为一个四元组 $(u,v,w,next)$，其中 $(u,v)$ 代表该条边的有向顶点对 $u\to v$，$w$ 代表边上的权值，$next$ 指向下一条边。
• 具体的，我们需要一个边的结构体数组 edge[maxm]，maxm表示边的总数，所有边都存储在这个结构体数组中，并且用head[i]来指向 $i$ 结点的第一条边。
• 边的结构体声明如下：

struct Edge {
    int u, v, w, next;
    Edge() {}
    Edge(int _u, int _v, int _w, int _next) :
        u(_u), v(_v), w(_w), next(_next) 
    {
    }
}edge[maxm];

• 初始化所有的head[i] = -1，当前边总数 edgeCount = 0；
• 每读入一条 $u\to v$ 的边，调用 addEdge(u, v, w)，具体函数的实现如下：

void addEdge(int u, int v, int w) {
    edge[edgeCount] = Edge(u, v, w, head[u]);
    head[u] = edgeCount++;
}

• 这个函数的含义是每加入一条边 $(u,v,w)$，就在原有的链表结构的首部插入这条边，使得每次插入的时间复杂度为 $O(1)$，所以链表的边的顺序和读入顺序正好是逆序的。这种结构在无论是稠密的还是稀疏的图上都有非常好的表现，空间上没有浪费，时间上也是最小开销。
• 调用的时候只要通过head[i]就能访问到由 $i$ 出发的第一条边的编号，通过编号到edge数组进行索引可以得到边的具体信息，然后根据这条边的next域可以得到第二条边的编号，以此类推，直到 next域为 -1 为止。

for (int e = head[u]; ~e; e = edges[e].next) {
    int v = edges[e].v;
    ValueType w = edges[e].w;
    ...
}

• 文中的 ~e等价于 e != -1，是对e进行二进制取反的操作（-1 的的补码二进制全是 1，取反后变成全 0，这样就使得条件不满足跳出循环）。

5️⃣简单算法的入门

• 入门十大算法是 线性枚举、线性迭代、简单排序、二分枚举、双指针、差分法、位运算、贪心、分治递归、简单动态规划。
• 对于这十大算法，我会逐步更新道这个专栏里面：《LeetCode算法全集》。
• 浓缩版可参考如下文章：《十大入门算法》

---

🚊10、简单动态规划

LeetCode 746. 使用最小花费爬楼梯

  数组的每个下标作为一个阶梯，第 $i$ 个阶梯对应着一个非负数的体力花费值 $cost[i]$（下标从 0 开始）。每当爬上一个阶梯，都要花费对应的体力值，一旦支付了相应的体力值，就可以选择 向上爬一个阶梯 或者 爬两个阶梯。求找出达到楼层顶部的最低花费。在开始时，可以选择从下标为 0 或 1 的元素作为初始阶梯。
  样例输入： $cost=[1,99,1,1,1,99,1,1,99,1]$
  样例输出： $6$
如图所以，蓝色的代表消耗为 1 的楼梯，红色的代表消耗 99 的楼梯。

a、思路分析

• 令走到第 $i$ 层的最小消耗为 $f[i]$
• 假设当前的位置在 $i$ 层楼梯，那么只可能从 $i-1$ 层过来，或者 $i-2$ 层过来；
• 如果从 $i-1$ 层过来，则需要消耗体力值：$f[i-1]+cost[i-1]$；
• 如果从 $i-2$ 层过来，则需要消耗体力值：$f[i-2]+cost[i-2]$；
• 起点可以在第 0 或者 第 1 层，于是有状态转移方程：
• $$f[i]=\{\begin{array}{ll}0& i=0,1\\ \min (f[i-1]+cost[i-1],f[i-2]+cost[i-2])& i>1\end{array}$$
  

b. 时间复杂度

• 状态数：$O(n)$
• 状态转移：$O(1)$
• 时间复杂度：$O(n)$

c. 代码详解

class Solution {
    int f[1100];                                                   // (1)
public:
    int minCostClimbingStairs(vector<int>& cost) {
        f[0] = 0, f[1] = 0;                                        // (2)
        for(int i = 2; i <= cost.size(); ++i) {
            f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);    // (3)
        }
        return f[cost.size()];
    }
};

• $(1)$ 用f[i]代表到达第 $i$ 层的消耗的最小体力值。
• $(2)$ 初始化；
• $(3)$ 状态转移；

有没有发现，这个问题和斐波那契数列很像，只不过斐波那契数列是求和，这里是求最小值。

---

6️⃣刷题顺序的建议

  然后介绍一下刷题顺序的问题，我们刷题的时候千万不要想着一步到位，一开始，没有刷满三百题，姿态放低，都把自己当成小白来处理。
  这里以刷 LeetCode 为例，我目前只刷了不到 50 题，所以我是小白。
  当我是小白时，我只刷入门题，也就是下面这几个专题。先把上面所有的题目刷完，在考虑下一步要做什么。

👨‍👦1、入门算法

种类	链接
算法	算法入门
数据结构	数据结构入门
数组字符串专题	数组和字符串
动态规划专题	动态规划入门、DP路径问题

  当入门的题刷完了，并且都能讲述出来自己刷题的过程以后，我们再来看初级的一些算法和简单的数据结构，简单的数据结构就是线性表了，包含：数组、字符串、链表、栈、队列 等等，即下面这些专题。

👩‍👧‍👦2、初级算法

种类	链接
算法	初级算法
栈和队列专题	队列 & 栈

  上面的题刷完以后，其实已经算是基本入门了，然后就可以开始系统性的学习了。
  当然，基本如果真的到了这一步，说明你的确已经爱上了刷题了，那么我们可以尝试挑战一下 LeetCode 上的一些热门题，毕竟热门题才是现在面试的主流，能够有更好的结果，这样刷题的时候也会有更加强劲的动力不是吗！

👩‍👩‍👧‍👦3、中级算法

种类	链接
算法	中极算法
二叉树专题	二叉树
热门题	热门题 TOP 100

7️⃣系统学习算法和数据结构

🚍1、进阶动态规划

文章链接	难度等级	推荐阅读
夜深人静写算法（二）- 动态规划入门	★☆☆☆☆	★★★★★
夜深人静写算法（二十六）- 记忆化搜索	★☆☆☆☆	★★★★★
夜深人静写算法（十九）- 背包总览	★☆☆☆☆	★★★★★
夜深人静写算法（二十）- 最长单调子序列	★☆☆☆☆	★★★★★
夜深人静写算法（二十一）- 最长公共子序列	★☆☆☆☆	★★★★★
夜深人静写算法（二十二）- 最小编辑距离	★★☆☆☆	★★★★☆
夜深人静写算法（十四）- 0/1 背包	★☆☆☆☆	★★★★☆
夜深人静写算法（十五）- 完全背包	★★☆☆☆	★★★★☆
夜深人静写算法（十六）- 多重背包	★★☆☆☆	★★★★☆
夜深人静写算法（二十七）- 区间DP	★★★☆☆	★★★★☆
夜深人静写算法（二十九）- 数位DP	★★★☆☆	★★★★★
夜深人静写算法（十七）- 分组背包	★★★☆☆	★★★☆☆
夜深人静写算法（十八）- 依赖背包	★★★★☆	★★☆☆☆
夜深人静写算法（六）- RMQ	★★★☆☆	★★☆☆☆
树形DP	待更新	…
组合博弈	待更新	…
组合计数DP	待更新	…
四边形不等式	待更新	…
状态压缩DP/TSP	待更新	…
斜率优化的动态规划	待更新	…
插头DP	待更新	…

🪐2、强劲图论搜索

1、深度优先搜索

文章链接	难度等级	推荐阅读
夜深人静写算法（一）- 搜索入门	★☆☆☆☆	★★★☆☆
夜深人静写算法（八）- 二分图最大匹配	★★☆☆☆	★★☆☆☆
最大团	待更新	…
最小生成树	待更新	…
树的分治	待更新	…
迭代加深 IDA*	待更新	…
有向图强连通分量和2-sat	待更新	…
无向图割边割点	待更新	…
带权图的二分图匹配	待更新	…
哈密尔顿回路	待更新	…
最近公共祖先	待更新	…
欧拉回路圈套圈	待更新	…
最小费用最大流	待更新	…
最小树形图	待更新	…

2、广度优先搜索

文章链接	难度等级	推荐阅读
夜深人静写算法（十）- 单向广搜	★★☆☆☆	★★★★☆
夜深人静写算法（二十三）- 最短路	★★★☆☆	★★★★☆
夜深人静写算法（二十五）- 稳定婚姻	★★☆☆☆	★★☆☆☆
夜深人静写算法（二十四）- 最短路径树	★★★☆☆	★☆☆☆☆
K 短路	待更新	…
差分约束	待更新	…
拓扑排序	待更新	…
A*	待更新	…
双向广搜	待更新	…
最大流 最小割	待更新	…

0️⃣3、进阶初等数论

文章链接	难度等级	推荐阅读
夜深人静写算法（三）- 初等数论入门	★★☆☆☆	★★★★☆
夜深人静写算法（三十）- 二分快速幂	★☆☆☆☆	★★★★★
夜深人静写算法（三十一）- 欧拉函数	★★★☆☆	★★★★★
夜深人静写算法（三十二）- 费马小定理	★★☆☆☆	★★★☆☆
夜深人静写算法（三十三）- 扩展欧拉定理	★★★☆☆	★★★★☆
夜深人静写算法（三十四）- 逆元	★★★☆☆	★★★★☆
夜深人静写算法（三十五）- RSA 加密解密	★★★☆☆	★★★★★
夜深人静写算法（三十六）- 中国剩余定理	★★☆☆☆	★★★☆☆
夜深人静写算法（三十七）- 威尔逊定理	★★☆☆☆	★★★☆☆
夜深人静写算法（三十八）- 整数分块	★★☆☆☆	★★★★☆
卢卡斯定理	待更新	…
狄利克雷卷积	待更新	…
莫比乌斯反演	待更新	…
容斥原理	待更新	…
拉宾米勒	待更新	…
Pollard rho	待更新	…
莫队	待更新	…
原根	待更新	…
大步小步算法	待更新	…
二次剩余	待更新	…
矩阵二分快速幂	待更新	…
Polya环形计数	待更新	…

🛑4、进阶计算几何

📏5、字符串的匹配

🎄6、高級数据结构

---

🙉饭不食，水不饮，题必须刷🙉
C语言免费动漫教程，和我一起打卡！ 🌞《光天化日学C语言》🌞
LeetCode 太难？先看简单题！ 🧡《C语言入门100例》🧡
数据结构难？不存在的！ 🌳《画解数据结构》🌳
LeetCode 太简单？算法学起来！ 🌌《夜深人静写算法》🌌

---