一、简介 SPFA算法是Bellman-Ford算法的队列优化。它可以求出单源最短路，也可检测到负环，实现起来也比较容易。但是现在很多题目会卡SPFA，所以要看情况使用。 二、中心思想 可以证明，只有上一次迭代中松弛过的点才有可能参与下一次迭代的松弛操作。朴素的Bellman-Ford算法中对于每一
发布于 2023-07-01
一、简介 Bellman-Ford算法是由Richard Bellman和Leicester Ford创立的，求解单源最短路径问题的一种算法。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(V*
发布于 2023-06-30
一、简介 Dijkstra算法是由荷兰计算机科学家Edsger Wybe Dijkstra于1959年提出的，是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。Dijkstra算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩
发布于 2023-06-29
一、DFS与BFS的原理 有请我们的五毛钱特效！ DFS BFS 二、DFS的实现 AcWing842 排列数字 #include <iostream> using namespace std; const int N =
发布于 2022-02-17
一、什么是哈希表？ 通过一个散列函数，将任意元素映射在数组下标中。它提供了快速的插入操作和查找操作，无论哈希表中有多少条数据，插入和查找的时间复杂度都是为$O(1)$。 二、哈希表的存储结构（冲突的处理方式） 开放寻址法 拉链法：在冲突位置引出链表 三、数字哈希
发布于 2022-02-12
一、堆是什么？ 堆是一棵完全二叉树 完全二叉树：除了最后一层节点，全部非空的二叉树，且最后一层节点从左往右排布 小根堆：每个节点都小于两个子节点 存储方式：一维数组，下标从1开始，下标x的左子节点是下标2x，右子节点是下标2x+1 二、如何手写一个堆？ 初始化，读入堆 for (int i = 1;
发布于 2022-02-11
一、Trie树的基本作用： 高效地存储和查找字符串集合的数据结构 例如，我们要存储以下字符串：abcdef,abdef,aced,bcdf,bcff,cdaa,abc，我们可以以树的形式存储： 在这里，我们以标红的形式来标记每个字符串的末尾。 二、代码实现 初始化 #include <iostrea
发布于 2022-02-10
一、并查集的作用 将两个集合合并 询问两个元素是否在同一个集合当中 二、并查集的基本原理 每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点 如何判断树根：if(p[x]==x) 如何求x的集合编号：while(p[x]!=x) x=p[x]; 如何
发布于 2022-02-10
一、暴力求解！ string s, p; //长度为n的模式串s和长度为m的模版串p for (int i = 1; i <= n; i++) { bool flag = true; for (int j = 1; j <= m; j++) { if (s[i - j + 1] != p
发布于 2022-01-23
一、基本概念 栈：先进后出。越后插入的元素，越先弹出来（有底的圆桶） 队列：先进先出。越先插入的元素，越先弹出来（无底的圆桶） 二、实现 栈： #include <iostream> using namespace std; const int N = 100010; int stk[N], tt
发布于 2022-01-14
一、用数组模拟单链表 邻接表：单链表的集合 单链表 #include <iostream> using namespace std; const int N = 100010; //head表示头节点的下标 //e[i]表示节点i的值 //ne[i]表示节点i的next指针是多少 //idx表示当前
发布于 2022-01-13
