lisl1233

分类

字符串(6) 最小生成树(2) 最短路径(5)

/ 注册

全部文章（共13篇）

最大回文子串--Manacher

最大回文子串----Manacher 思路：先把原字符串扩充然后遍历扩充后的数组用maxx存放最大回文长度 len数组存放他每个下标的的会问长度时间复杂度O(n) Code： #include<iostream> #include<cmath> #include<...

2021-07-16

1 482

最大连续子段和

最大连续子段和思路：用两个变量一个存放累计最大值一个存放当前和如果当前和小于0 则在这之前的数都pass掉给当前和重新赋值时间复杂度O(n) code: #include<iostream> #include<cmath> using namespace st...

2021-07-16

1 442

最长公共子序列--LCS

最长公共子序列----LCS 思路：普普通通动态规划并且判断他当前的取值是上方还是左方，并做好标记，再利用回溯，输出字符串时间复杂度O(nlogn) Code: #include<iostream> #include<cmath> #include<string....

2021-07-16

1 466

最大上升子序列--LIS

最大上升子序列思路：建立一个low数组，用于存放上升的子序列，并记录长度，如果一个数大于low的最后一个数，则将他添加到low数组最后面，如果不大于，则将那个数利用二分放在low合适的位置，以便下次比较。时间复杂度O(nlogn) Code： #include<iostream> ...

2021-07-16

1 499

字符串匹配--hash

字符串匹配--hash 思路：先算出母串的hash值，再算出子串的hash值，利用差分的思想，计算出母串长度与子串长度相等的hash值，并进行判断，如果hash值相等，即可判断他们为相同的字符串，如果担心hash值冲突，即可加以一层判断来保证结果的准确性时间复杂度O(n) Code： #inc...

2021-07-14

1 596

字符串匹配--KMP

字符串匹配思路： nxt[j]=k的意思是，下标为j的字符前字符串的最长相等前后缀为k nxt数组的值只与子串有关 nxtv则是优化nxt 使得处理时间更加短时间复杂度O(n) Code: #include<iostream> #include<memory.h> ...

2021-07-14

1 488

最短路径--Dijstra堆优化

最短路径----Dijstra堆优化单源最短路径(是速度最快且最稳定的算法，但不过只能求带有非负权图) 思路： Dijstra每次需要遍历所有的点，找到一个最小值，而堆优化则是利用小顶堆的优势，每次都将距离最短的点都放在队列的顶部，则无需每次遍历所有的点，这样所需的时间就更短。时间复杂度O(m...

2021-07-14

1 471

最短路径--spfa

最短路径----spfa 单源最短路径思路: spfa算法是bellman_ford的队列优化算法，bellman是枚举所有的边，所以其时间复杂度为O(nm)，而spfa则是只枚举之前改变了值的边，如果当前点被改变了值，则讲这个点放到队列当中去，如果已经在队列当中了，就不需要再次放入队列当中，然后...

2021-07-14

1 503

最短路径--Bellman_ford

最短路径Bellman_ford 单源最短路径思路：循环n-1次,每次寻找出经过k条边到达其余点的最短路径，每次都遍历更新其余所有点。时间复杂度O（nm）Code: #include<iostream> #include<memory.h> #include<cm...

2021-07-13

1 429

最短路径--Dijstra

最短路径----Dijstra 单源最短路径思路: 寻找一个确定离起点最近的点，并给他打上标记，再用这个点当为中间点去更新其余的点。用vis标记i点是否为已经确定的点用dis存放起点到每i点的最短距离时间复杂度O(n²)Code: #include<iostream> #includ...

2021-07-13

1 451