Dijkstra算法是一种基于贪心的算法， 详情推导： 算法的基本思路： 首先初始化每个点的距离是正无穷， 起点为0 进行 n - 1 次循环 每次找距离的最小值 然后用距离的最小值去更新剩余点到起点的距离 如果终点的距离为正无穷说明没有最短路 Acwing 849. Dijkstra求最...

树是一种特殊的图，所以利用图的深度优先遍历就可以进行树的深度优先遍历。流程也和图的遍历类似。 AcWing 846. 树的重心 来源： https://www.acwing.com/problem/content/848/ 给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。 请你找到...

bellman-ford 算法主要是用于对有边数限制的最短路问题。 基本思路： 首先循环k次代表K条边 然后枚举每条边， 更新每条边的最短距离 Acwing: 853. 有边数限制的最短路 来源： https://www.acwing.com/problem/content/855/ 给定...

题目： 八数码 来源: https://www.acwing.com/problem/content/847/ 在一个3×3的网格中，1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。 例如： 1231 2 3x 4 67 5 8 在游戏过程中，可以把“x”与其上、下、左、右四...

深度优先搜索(DFS)： 从某个节点往下开始搜索，走头，走到不能走的时候再回去(回溯)。 宽度优先搜索(BFS): 一层一层往下搜索，每次扩展一层。 数据结构 空间 DFS stack $O(h)$ BFS queue $O(2^h)$ BFS 有一个最短路的概念...

堆，又叫优先队列。堆是一颗完全二叉树结构（除了最后一层节点之外，上面所有节点都是为满的，最后一层，从左到右排列）。 手写堆的基本要求： 插入一个数 求集合中的最小值 删除最小值 删除任意一个元素 修改任意一个元素 小根堆： 根节点小于左右两边的节点。 大根堆： 根节点大于左右两边的节...

并查集是一种以集合的合并和查询的一种结构。 并查集： 将两个集合合并 询问两个元素是否在一个集合当中 基本原理： 每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点储存它的父节点，p[x]表示x的父节点。 问题1： 如何判断树根： if(p[x] == x) 问题2： 如何求x...

Trie 树又称为字典树，前缀树， 是一种用于高效存储和查找的字符串集合的数据结构。 结构如上图，头节点都为空，表示开始的节点。然后依次往下走，如果当前有以某一个字母为开头的继续往下走。如果没有创建出来，继续往下走。然后在以字母结尾的位置做出一个标记。记录有多少个字母是以它结尾的。 题目：...

和单调栈很相似，满足一定的单调性质，这些性质可以是单调递增，单调递减等等，使用的是队列结构。 具体操作就是： 确定某种单调性 按照这种单调性，从对头往队尾进行弹出数据 如果不满足这种单调性就一直弹出数据，直到满足性质或者弹空 压入数据 滑动窗口 题目来源： https://www.acw...

栈结构实现，但是存入的数据具有某种性质的单调性。这个单调性可以是递增也可以是递减。 具体操作就是： 确定某种单调性 按照这种单调性，从栈顶往栈底依次弹出数据 如果不满足这种单调性就一直弹出数据，直到满足性质或者弹空栈 压入数据 题目来源: https://www.acwing.com/p...