算法汇总

常用算法汇总

回想起大学学过的算法，可谓数不尽数。但是有些算法总是让我又爱又恨。比如KMP、再比如Dijkstra最短路径，这些算法其实都很精彩，奈何我一学就忘，每次忘记了都要花费大量的时间去看教程，比如知乎上面的各种算法。一看就是半天，所以我打算开一个帖子博文，专门记录那些「稍微有些复杂」、「不好理解容易忘记」、「经常会考到」的算法吧！

KMP算法

SE高级数据结构里面讲到的，核心在于j = next[j]

1）KMP核心思想

1
2
3
4
index     0 1 2 3 4 5 6
目标串(ss) a b a b a b c
          | | | |
模式串(mm) a b a b c

如上图，匹配两个字符串abababc和ababc。定义：我们要在这个目标串(ss)里面找我们想要的模式串(mm)，建议记一下缩写（目标串ss，模式串mm），

先比较发现index 0-3的字母都一样，都是abab。index为4的时候就不一样了，这时候怎么办？我悄悄的把模式串往后移动2位，可以发现，除开被移走的部分，已经匹配的区域还是一样匹配。

1
2
3
4
index     0 1 2 3 4 5 6
目标串(ss) a b a b a b c
              | |
模式串(mm)     a b a b c

进而我们发现后面的4-6的也一样，匹配成功。KMP的核心思想就是：当发现不匹配的时候，向后挪动「模式串」若干位，然后继续匹配，跑完为止。问题：

  • 挪动多少位？
  • 为什么挪动若干位之后还是一样？

两问题本质一致，原因很简单，对于模式串的mm[0]-mm[3]，也就是abab，从mm[0]往后数2两位，与mm[3]往前数两位一样，这就是为什么挪动两位，挪了还一样原因

1
2
3
4
5
6
模式串(mm)  a b a b c
              / /
             / /
            / /
           / /
模式串(mm) a b a b c

补充：有人说那我从mm[0]往后数4两位，与mm[3]往前数4位也一样，我这里规定：如果出现这种情况，以最小的为准！所以还是以2为准。我们记next[4] = 2。含义：

  • 4：mm串从0-3的字符串，记为str
  • 2：str从头部往后数2个的字符串str1，到str后部往前数2个str2，str1==str2。
  • 上面所述，如果比2小，比0大，不可能出现str1==str2

核心思想点到为止，再纠结自己拿笔画图、看其他资料。我只觉得如果死纠结只会让自己一天都沉迷在KMP怎么写的原理里面。（所以劝大家不要纠结）

2）KMP算法

要写对KMP，只需要知道几个关键东西

  • 首先要写对buildNext数组的过程
  • 然后要写对匹配的原理

这里顺带提一嘴buildNext函数，记住两个：

  • 目标串不带通配符，模式串带-1作为index的通配符
  • i永远对应目标串，j永远对应模式串
  • 优先判断：j < 0代表通配
  • 错配时：j = next[j]
  • 初始化：next[i] = j
  • 匹配：先ij自增，再考虑next[i] = j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> buildNext(string mm){
    //              i=0
    // 目标串：     mm[0]  mm[1]  mm[2]
    // 模式串： *   mm[0]  mm[1]  mm[2]
    //       j=-1
    int i = 0;
    int j = -1;
    int mmSize = mm.size();
    vector<int> next = vector(mm.size(), 0);
    next[i] = j;

    while(i + 1 < mmSize){
        if(j < 0 || mm[i] == mm[j]){
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

再来说KMP的算法

  • 初始化时i = j = 0
  • 错配j = next[j]
  • 最终，如果j没有跑满，那就是不匹配，如果匹配，下标为i-j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ss 搜索的范围 mm搜索的内容
int KMP(string ss, string mm){
    int i = 0;
    int j = 0;
    int ssSize = ss.size();
    int mmSize = mm.size();
    vector<int> next = buildNext(mm);

    while(i < ssSize && j < mmSize){
        if(j < 0 || ss[i] == mm[j]){
            i++;j++;
        } else{
            j = next[j];
        }
    }

    int index  = i - j;
    if(j < (int)mm.size())
        return -1;
    return i - j;
}

Dijsktra算法

Dijsktra是一个最短路径的算法。有两个版本的实现！我这里给出两个模版，都返回一个数组，代表从src出发，到所有节点的最短距离。

1）版本一

版本一比较好理解，推荐记忆这个！

我这里只用最简单的语言描述这个算法，具体证明感兴趣者研究。算法步骤：

  • graph[i][j]graph[i][j]表示从 i→ji \rightarrow j 的距离，地图数据，srcsrc 代表出发的节点编号
  • 维护一个dist数组，记录src出发到各个节点的距离，初始化inf表示无穷远
  • 维护一个used数组，记录是否曾经到过这里，初始化false，全部没有走过
  • 从出发点到出发点距离显然是 00，所以dist[src] = 0
  • 遍历nn次(nn 是节点的数量)：
    • 每次在dist数组里面找到dist数组里面，之前没走过的，且值最小的下标 xx：即当前距离src最小的节点是 xx
    • 找到后标记used[x]=trueused[x] = true，这个节点已经走过啦！
    • 考虑从 xx 节点出发可以到达的地方，用 yy 遍历并更新 dist[]dist[] 数组，dist[y]=min(dist[y],dist[x]+graph[x][y])dist[y] = min(dist[y], dist[x] + graph[x][y])
    • （解释：从 src→ysrc \rightarrow y 的最短路径，如果发现路过 src→x→ysrc \rightarrow x \rightarrow y 更短，就更新）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 说实话这是个模版题目，竞赛的技巧性很强，写代码的时候很多时候简介为主
// 所以看的很容易看不明白
// graph 二维数组; src 出发节点; return dist数组(表示src到各个节点最短距离)
vector<int> dijkstra_v1(vector<vector<int>>& graph, int src) {
    // inf: 不能到达，就用inf表示
    // - 为什么不用INT_MAX? 因为后面加法可能越界，如果爆炸自行改long long
    // - 为什么不用 -1 不想后面给你增加额外的debug时间
    const int inf = INT_MAX / 2;
    // n: 节点的数量
    const int n = graph.size();
    // dist数组(表示src到各个节点最短距离)
    vector<int> dist(n, inf);
    // 初始化的时候 src地方为0
    dist[src] = 0;
    // 走过的节点
    vector<bool> used(n, false);
    
    // 刚开始，默认所有的节点都没有走过
    // 遍历n次，每次找到dist数组里面，没走过的，距离最小的
    for (int i = 0; i < n; ++i) {
        int x = -1;
        // 让x指向dist数组里面(没有走过的!used)、并且最小的
        for (int y = 0; y < n; ++y) {
            // 技巧性有点强，x == -1 是为了妥协，一旦找到一个!used,立马赋值
            // 后面的是为了严格要求，如果发现更小的，及时更新x的值
            // 这么写说实话我都想打人，写的是啥可读性太差
            if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                x = y;
            }
        }

        // 有人可能会怀疑这个x会不会是-1啊
        // 不可能，最外层for循环n次，每次标记一个used[x] = true
        // 所以肯定不会-1
        // cout << x << endl;
        used[x] = true;
        
        // 遍历dist数组，然后更新所有能够通过x到达的节点y，对应的dist[y]
        for (int y = 0; y < n; ++y) {
            dist[y] = min(dist[y], dist[x] + graph[x][y]);
        }
    }
    return dist;
}

2）版本二

第二个版本是用的优先级队列实现的。因为前面我每次都要遍历一次数组，才能找到数组 dist[x]dist[x] 中值最小的：即之前没走过的，且 dist[x]dist[x] 值最小的下标 xx。

所以我可以用一个pair<int, int>的优先级队列存储，pair的第一个元素是节点 ii 的 distdist 距离，第二个元素是节点的下标 ii 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
vector<int> dijkstra_v2(vector<vector<int>>& graph, int src) {
    // inf: 不能到达，就用inf表示
    const int inf = INT_MAX / 2;
    // n:节点的数量
    const int n = graph.size();
    // dist数组
    vector<int> dist(n, inf);
    // 初始化的时候 src地方为0
    dist[src] = 0;

    // 之前我们用used表示走过的节点，现在我们用优先级队列，走过出队，所以不需要
    // vector<bool> used(n, false);
    // q表示走过的节点的队列
    // pair的第一个元素 i 是: 从src到j，最短的距离
    // pair的第二个元素 j 是: 节点的编号(0-base)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    
    // 从src到src，距离为0，显然
    q.push({0, src});


    // 遍历n次，每次找到dist数组里面，没走过的，距离最小的
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        
        // 拿出队列里面，最近的一个可以到达的节点
        int distance = p.first; 
        int curNodeID = p.second;

        // 如果发现拿出来的节点，反而比已经记录的最短路径还长
        // 丢弃，不用走了，已经走过了
        if(dist[curNodeID] < distance){
            continue;
        }

        for(int next = 0; next < graph[curNodeID].size(); next++){
            // i表示可以走的下一个
            if(graph[curNodeID][next] == inf)
                continue;
            
            // dist[next] = min(dist[next], dist[curNodeID] + graph[curNodeID][next]);
            int newDistance = dist[curNodeID] + graph[curNodeID][next];
            if(newDistance < dist[next]){
                dist[next] = newDistance;
                q.push({newDistance, next});
            }
        }
    }
    // 后面方法一中的遍历这些，显然就不需要啦
    return dist;
}

Floyd算法

Floyd算法主要用来解决复杂度为 O(n3)O(n3) 的「多源最短路径」问题

1）写法

函数如下，简称三for循环算法，但是需要注意的是三个for的顺序。依次枚举中转点->枚举起点->枚举终点->松弛操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<vector<int>> floyd(vector<vector<int>>& graph) {
    // 节点的数量
    int num = graph.size();
    // 无穷远，graph无穷远也需要是这个数值
    const int inf = INT_MAX / 2;
    vector<vector<int>> dist = graph;

    // floyd 基本流程为三层循环：
    // 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
    for (int p = 0; p < num; p++) {
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                dist[i][j] = min(dist[i][j], dist[i][p] + dist[p][j]);
            }
        }
    }

    return dist;
}

2）原理

Floyd算法本质上是DP，即对于每个（可能的）新增的节点pp，来更新（可能的）节点 ii 到 jj 的最短距离。为什么新增节点 pp 的循环要放在最外层呢？这是由其算法本身所决定的，其每一步求出任意一对顶点之间仅通过中间节点1,2,…,k1,2,…,k的最短距离，当1,2,…,k1,2,…,k扩展到1,2,…,k,k+11,2,…,k,k+1时候，我们需要计算路过 k+1k+1​ 的最短距离，以此类推。

假设有下图：

graph LR;
    1((节点1))-->|1|4((节点4));
    4-->|3|2((节点2));
    4-->|1|3((节点3));
    3-->|1|2((节点2));

对应的数组：

1
map[1][4] = 1; map[4][2] = 3; map[4][3] = 1; map[3][2] = 1;
  • 如果我们按 pp 循环在最内层来计算，那么1，2节点的最短路径为min(map[1][2], map[1][3]+map[3][2],map[1][4]+map[4][2]) = 4;，此后是不会更新的 1→21 \rightarrow 2 的最短路径
  • 实际上min(map[1][2]) = map[1][4] + map[4][3] + map[3][2] = 3;
#Leetcode #算法 #C++
编辑链接
算法汇总
http://blog.ayaka.space/2024/03/common-algorithm/
作者
Musicminion
发布于
2024年3月20日
许可协议