https://zhuanlan.zhihu.com/p/126116878 排序算法系列目录说明 冒泡排序（Bubble Sort） 插入排序（Insertion Sort） 希尔排序（Shell Sort） 选择排序（Selection Sort） 快速排序（Quick Sort） 归并排序（Merge Sort） 堆排序（Heap Sort） 计数排序（Counting Sort） 桶排序（Bucket Sort） 基数排序（Radix Sort） 基数排序（RadixSort） 基数排序（Radix sor…

需要善于利用题目, 不要想太多, 比如这个题775. 全局倒置与局部倒置, 题目问题的是给定数组的全局倒置和局部倒置是否一样多? 问得是是否一样多, 并不一定要求出两个各自的数值, 只要能找出二者之间存在差异即可.

https://oi-wiki.org/basic/prefix-sum/ class NumArray { public: vector<int> prefixeSum = vector<int>(10001, 0); NumArray(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; ++i) { prefixeSum[i+1] = prefixeSum[i] + nums[i]; …

KMP 算法是应用了滑动窗口最典型的例子, 但此片文章不以 KMP 算法来做讲解例子, 因为这个算法里面已经容纳了很多前人的处理与思想, 难懂的同时可能自带劝退属性. 数组是一种基本的数据结构, 会写代码的人不会数组操作都不敢出门见人, 但是很多基于数据的操作会浪费大量的时间, 滑动窗口就是为了帮助我们提升效率的一种算法. 滑动窗口模板 // int n = 数组长度; for(int l = 0, r = 0; r < n; ++r) { // 右边滑入窗口; // while(不符合条件) // 左边滑出…

最小生成树的应用 最小生成树的应用场景很多, 小到我们要来个欧洲十国游, 怎么规划路径让交通费用最低, 大到国家的电力网, 公路网, 通信网, 怎么规划路径可以让建设成本最低, 学习了最小生成树后, 你就可以通过算法来计算出最佳路径了, 不仅如此, 所有涉及连接网络中所有节点的最优路径问题, 都可以通过最小生成树来处理. 概念 连通图: 在无向图中, 若任意两个顶点 $u$ 与 $v$ 都有路径相通, 则称该无向图为连通图. 强连通图: 在有向图中, 若任意两个顶点 $u$ 与 $v$ 都有路径相通, 则称该有向图…

作者:lucifer1004 链接:https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/solution/zui-duan-lu-jing-suan-fa-bfs0-1bfsdijkstra-by-luci/ 来源: 力扣 (LeetCode) 著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处. 大佬写的题解就是不一样, 基于这个题目: 1368. 使网格图至少有一条有效路径的最…

Tarjan 算法 Tarjan 算法是基于深度优先搜索的算法, 用于求解图的连通性问题. Tarjan 算法可以在线性时间内求出无向图的割点与桥, 进一步地可以求解无向图的双连通分量; 同时, 也可以求解有向图的强连通分量, 必经点与必经边. Tarjan 是谁? 提到 Tarjan, 不得不提的就是算法的作者 Robert Tarjan. 他是一名著名的计算机科学家, 我们耳熟能详的最近公共祖先 (LCA) 问题, 强连通分量问题, 双连通分量问题的高效算法都是由他发现并解决的, 同时他还参与了开发斐波那契堆,…

定义 在有向图的数学理论中, 如果一个图的每一个顶点都可从该图其他任意一点到达, 则称该图是强连通的. 在任意有向图中能够实现强连通的部分我们称其为强连通分量. 判断一个图是否为强连通以及找到一个图强连通分量只需要线性时间 $O(V + E)$. 如果有向图的每一对顶点之间在每个方向上都有一条路径, 则称该有向图为强连通图. 也就是说, 顶点对中的第一个顶点到第二个顶点存在一条路径, 从第二个顶点到第一个顶点存在另一条路径. 在本身可能不是强连通的有向图 $G$ 中, 如果一对顶点 $u$ 和 $v$ 之间在每个方…

SPFA 算法介绍 适用范围: 给定的图存在负权边, 这时类似 Dijkstra 等算法便没有了用武之地, 而 Bellman-Ford 算法的复杂度又过高, SPFA 算法便派上用场了. 我们约定有向加权图 G 不存在负权回路, 即最短路径一定存在. 当然, 我们可以在执行该算法前做一次拓扑排序, 以判断是否存在负权回路, 但这不是我们讨论的重点. SPFA 算法是求解单源最短路径问题的一种算法, 由理查德·贝尔曼 (Richard Bellman) 和 莱斯特·福特 创立的. 有时候这种算法也被称为 Moore…

Bellman Ford(类 & 邻接表) 虽然题目规定了不存在「负权边」, 但我们仍然可以使用可以在「负权图中求最短路」的 Bellman Ford 进行求解, 该算法也是「单源最短路」算法, 复杂度为 O(n * m)O(n∗m). class Solution { class Edge { int a, b, c; Edge(int _a, int _b, int _c) { a = _a; b = _b; c = _c; } } int N = 110, M = 6010; // dist[x] =…

class Solution { int N = 110, M = 6010; // 邻接矩阵数组:w[a][b] = c 代表从 a 到 b 有权重为 c 的边 int[][] w = new int[N][N]; int INF = 0x3f3f3f3f; int n, k; public int networkDelayTime(int[][] ts, int _n, int _k) { n = _n; k = _k; // 初始化邻接矩阵 for (int i = 1; i <= n; i++) { …

核心思想 所有的点分类两类 $\text{A}$ (已经根据此集合中的点去更新其他点的距离), $\text{B}$ (未根据此集合中的点去更新其他点的距离) $\text{A}$ 和 $\text{B}$ 虽然是两个集合, 代码中可以用一个 vector<bool> 数组实现 每次从 $\text{B}$ 中取一个最小的, 取更新其他点的距离 $\text{B}$ 中的点为空, 遍历结束 局限性 在 $\text{Dijkstra}$ 算法的应用过程中, 某些有权图的边可能为负, 也就是说, 即使有权…

整理自: https://blog.csdn.net/qq_35501306/article/details/106276964 链式前向星概括 以同起点为一条链, 数组 $head[a]$ 存储起点 $a$ 的最新录入的一条边的索引, 每条边以结构体的形式存储该边信息 (该边终点, 权值, 同起点的边中的上一条边即上一次录入的边的位置), 所有边构成一个结构体数组. 很多帖子说到的是存储的是下一条边, 这种理解很容易给人误导, 应该是每一条边都能通过自身结构体存储的信息回溯到上一条边, 所以叫前向星. 假如我们要…

参考 OI Wiki 并查集, 这个网站是个宝库哦 引言 399. 除法求值 这个是 leetcode 上的一个求除法运算的题目, 我直接用的深度遍历做的, 然后看了下时间最短的那个, 用的是并查集, 我当时脑子懵了, 这都可以用并查集, 焯. 搜了下我的博客, 发现之前没有写并查集先关的文档, 这回补充一个算法介绍, 算法模板, 常见题目. 并查集的实现 struct UnionFind { vector <int> ancestor; UnionFind(int n) { ancestor.resi…

带着问题读 什么是拓扑排序 如何实现拓扑排序, 拓扑排序时能否发现图满足不了拓扑排序 如果判断一个有向图能否拓扑排序 深度优先怎么做? 心得 顶点的个数并不是个的边的个数 从队列中pop顶点的时候才加入到结果集中 顶点的依赖顺序不能弄反了 作者: 灰睛眼蓝 链接:https://www.jianshu.com/p/b59db381561a 来源: 简书 著作权归作者所有. 商业转载请联系作者获得授权, 非商业转载请注明出处. 什么是拓扑排序 在图论中, 拓扑排序 (Topological Sorting) 是一个有…