分类: 算法

3 篇文章

最短路径算法重新整理
太久没写算法了,最短路径都全忘了,开个坑,今天晚点再整理。主要算法应该是Dijkstra,Bellman-Ford以及SPFA算法。 最短路径算法是图论中的基础算法之一,其中分为单源最短路径算法以及所有点之间的最短路径算法。其中单源最短路径算法是求图中任意两个顶点之间的最短路径。 单源最短路径算法比较常用的算法包括Dijkstra算法,Bellma…
单调栈(monotonic stack)
单调栈的定义是指一个栈,其中从栈顶往栈底看,其中所有的元素都是只有一个单调的关系。而其中又包括严格单调栈以及非严格单调栈 单调栈的入栈 单调栈的入栈需要持续检查栈顶的元素。以单调递增(从栈底到栈顶的元素依次递增的栈为例)如果栈顶元素比即将入栈的元素小的时候,就应该执行出栈操作,直到栈顶元素大于入栈元素,再进行入栈操作。例如对于已经存在的栈:5,4,…
最大子序列Kadane算法
该算法由Jay Kadane 于1984年最先提出,其中使用了动态规划的思想,时间复杂度为$O(n)$。其中的证明应该是显而易见的。 其算法的主要是计算以结尾为$i$的字符串中的最大的字串。当不能够存在空的字串的时候存在以下的递推方程:$$\begin{equation} f(i)=\begin{cases} f(i-1)+a[i]& \t…