算法汇总

1.双指针

典例题：力扣 26. 删除有序数组中的重复项

一、概述

双指针算法是一种常见的算法，它通常用于解决数组或链表的问题。它的基本思想是使用两个指针来遍历数组或链表，从而解决问题。

双指针是一种思想或一种技巧并不是特别具体的算法。

具体就是用两个变量动态存储两个结点，来方便我们进行一些操作。通常用在线性的数据结构中。

特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。

二、常见的双指针方式

双指针分为快慢指针和左右指针（同速指针），左右指针通常在数组有序的情况下使用，快慢指针通常在单向遍历需要消耗大量时间，或者有特定要求限制的情况下使用。

同速指针：链表上两个指针，一个先出发，另一个后出发并以相同的速度跟随。

求链表的逆：通过临时指针让双指针同步前行

求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起

向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素

快慢指针：链表上两个指针从同一节点出发，其中一个指针前进速度比另一个指针快（比

如，是另一个指针的两倍）

计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢

指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点

判断链表是否有环：快慢指针从头节点出发，如果链表中存在环，两个指针最终会在环

中相遇

求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就。

三、常见应用

双指针算法包括以下几种常见的应用：

  1. 两数之和：给定一个数组和一个目标值，找到两个数的和等于目标值，返回这两个数的下标。这个问题可以使用双指针算法来解决。我们可以使用一个指针指向数组的第一个元素，另一个指针指向数组的最后一个元素。如果两个指针所指的元素之和等于目标值，那么我们就找到了答案，否则根据和与目标值的大小关系移动指针。

  2. 三数之和：给定一个数组，找到所有三个数的和等于0的不重复组合。这个问题可以使用双指针算法来解决。我们可以先将数组排序，然后使用一个指针指向数组的第一个元素，另外两个指针分别指向第一个元素的后面一个元素和最后一个元素。如果三个指针所指的元素之和等于0，那么我们就找到了一个答案，否则根据和与0的大小关系移动指针。

  3. 链表中倒数第k个节点：给定一个链表，找到链表中倒数第k个节点。这个问题可以使用双指针算法来解决。我们可以使用两个指针，一个指向链表的头节点，另一个指向链表的第k个节点。然后同时移动这两个指针，直到第二个指针指向链表的末尾，此时第一个指针就指向了倒数第k个节点。

  4. 链表的中间节点：给定一个链表，找到链表的中间节点。这个问题可以使用双指针算法来解决。我们可以使用两个指针，一个指向链表的头节点，另一个指向链表的中间节点。然后同时移动这两个指针，直到第二个指针指向链表的末尾，此时第一个指针就指向了链表的中间节点。

总之，双指针算法是一种常用的算法，它可以帮助我们解决许多数组和链表的问题。

2.二分法|二分查找法|二分搜索法

典例：力扣 704.二分查找

视频讲解：手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

一、概念

二分法是一种常用的算法思想，也称为二分查找或折半查找。其基本思想是将一个有序的数组或区间按照一定规则分成两部分，通过比较目标值与中间值的大小关系，确定目标值在哪一部分中，然后将搜索范围缩小到目标值可能存在的那一半，以此类推，直到找到目标值或搜索范围为空为止。

二分法的时间复杂度为O(log n)，比线性搜索的时间复杂度O(n)更快，适用于有序数组或区间的查找、求解最大值最小值等问题。

二分法的实现方法有多种，常见的有递归和非递归两种。递归实现的二分法代码简洁易懂，但是可能会产生栈溢出等问题；非递归实现的二分法则可以避免这些问题，但是代码相对复杂一些。

总之，二分法是一种非常实用的算法思想，可以用来解决很多实际问题，需要掌握和熟练运用。

二、原理

二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常简单，有点类似分治的思想。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

为了方便理解，我们以数组1, 2, 4, 5, 6, 7, 9, 12, 15, 19, 23, 26, 29, 34, 39，在数组中查找26为例，制作了一张查找过程图，其中low标示左下标，high标示右下标，mid标示中间值下标

图片

二分查找的过程就像上图一样，如果中间值大于查找值，则往数组的左边继续查找，如果小于查找值这往右边继续查找。二分查找的思想虽然非常简单，但是查找速度非常长，二分查找的时间复杂度为O(logn)。虽然二分查找的时间复杂度为O(logn)但是比很多O(1)的速度都要快，因为O(1)可能标示一个非常大的数值，比例O(1000)。

三、局限性

二分查找依赖数组结构

二分查找需要利用下标随机访问元素，如果我们想使用链表等其他数据结构则无法实现二分查找。

二分查找针对的是有序数据

二分查找需要的数据必须是有序的。如果数据没有序，我们需要先排序，排序的时间复杂度最低是 O(nlogn)。所以，如果我们针对的是一组静态的数据，没有频繁地插入、删除，我们可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。

但是，如果我们的数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论哪种方法，维护有序的成本都是很高的。

所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用

数据量太小不适合二分查找

如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如我们在一个大小为 10 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多，只有数据量比较大的时候，二分查找的优势才会比较明显。

数据量太大不适合二分查找

二分查找底层依赖的是数组，数组需要的是一段连续的存储空间，所以我们的数据比较大时，比如1GB，这时候可能不太适合使用二分查找，因为我们的内存都是离散的，可能电脑没有这么多的内存。

3.贪心算法

一、概念

贪心算法是一种解决问题的策略，它在每个阶段选择当前最优的解决方案，以期望最终得到全局最优解。贪心算法通常适用于具有贪心选择性质的问题，即局部最优解能导致全局最优解的问题。

贪心算法的基本思想是：从问题的起始状态开始，每次选择当前状态下最优的解决方案，直到达到结束状态。在每个阶段，都要做出一个局部最优的选择，而不考虑以后可能出现的情况，也就是说，当前的选择不会影响以后的选择。

贪心算法的优点是简单、高效，可以避免深度搜索等复杂算法的时间复杂度过高的问题。但是，贪心算法的局限性也很明显，它只能保证得到局部最优解，不能保证得到全局最优解。因此，贪心算法的应用范围相对有限，需要根据具体问题的特点进行分析和选择。

常见的贪心算法问题包括：找钱问题、活动安排问题、背包问题、最小生成树问题等。

二、应用例题

以下是几个使用贪心算法的样例Java代码：

1.找零钱问题：

假设要找给客户73元的零钱，现有1元、5元、10元、20元、50元的硬币，如何使用最少的硬币找零？

输入：money = 73, coins = {1, 5, 10, 20, 50}

输出：

1元硬币：3个

5元硬币：0个

10元硬币：1个

20元硬币：1个

50元硬币：1个

1
2
3
4
5
6
7
8
9
10
11
12
java
public static void change(int money, int[] coins) {
    int n = coins.length;
    int[] ans = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        ans[i] = money / coins[i];
        money %= coins[i];
    }
    for (int i = 0; i < n; i++) {
        System.out.println(coins[i] + "元硬币：" + ans[i] + "个");
    }
}

2.活动安排问题：
假设有n个活动，每个活动有开始时间和结束时间，如何安排这些活动，使得尽可能多的活动能够被安排？

输入：start = {1, 3, 0, 5, 8, 5}, end = {2, 4, 6, 7, 9, 9}

输出：4

1
2
3
4
5
6
7
8
9
10
11
12
13
java
public static int activityCount(int[] start, int[] end) {
    int n = start.length;
    int ans = 0;
    int lastEnd = 0;
    for (int i = 0; i < n; i++) {
        if (start[i] >= lastEnd) {
            ans++;
            lastEnd = end[i];
        }
    }
    return ans;
}

3.背包问题：
假设有n个物品，每个物品有重量和价值，背包的容量为C，如何选择物品使得背包中的总价值最大？

输入：weight = {10, 20, 30}, value = {60, 100, 120}, capacity = 50

输出：240.0

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
java
public static double knapsack(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    double ans = 0;
    double[] ratio = new double[n];
    for (int i = 0; i < n; i++) {
        ratio[i] = (double) value[i] / weight[i];
    }
    while (capacity > 0) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (weight[i] > 0 && (best == -1 || ratio[i] > ratio[best])) {
                best = i;
            }
        }
        if (best == -1) {
            break;
        }
        int take = Math.min(capacity, weight[best]);
        ans += take * ratio[best];
        capacity -= take;
        weight[best] -= take;
    }
    return ans;
}

这些代码只是简单的示例，实际上贪心算法的应用还要根据具体问题进行分析和设计。
LeetCode1605. 给定行和列的和求可行矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
java
class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int m = rowSum.length, n = colSum.length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[i][j] = Math.min(rowSum[i], colSum[j]);
                rowSum[i] -= res[i][j];
                colSum[j] -= res[i][j];
            }
        }
        return res;
    }
}

三、优缺点分析

利：

  1. 简单易懂：贪心算法思路简单，易于理解。
  2. 高效性：相对于其他算法，贪心算法的时间复杂度较低，效率较高。
  3. 可行性：贪心算法的实现较为简单，可以在较短时间内得到可行的解。

弊：

  1. 局限性：贪心算法只能保证得到局部最优解，不能保证得到全局最优解。
  2. 依赖性：贪心算法的正确性依赖于问题具有贪心选择性质，即局部最优解能导致全局最优解的问题。
  3. 设计困难：对于一些问题，设计贪心算法可能比较困难，需要考虑多种因素和限制条件。
    因此，在使用贪心算法时，需要根据具体问题的特点进行分析和选择，权衡其优缺点，以便得到较为准确的解。

4.KMP算法(字符串匹配)

一、概念

Knuth-Morris-Pratt算法(简称KMP)是一种高效的字符串匹配算法，可以在文本串中快速查找模式串的位置。具体来说，它利用已知信息尽可能地减少匹配的次数，通过对模式串进行预处理，生成一个跳转表（也称为next数组），用于在匹配时快速跳过不必要的比较。在匹配过程中，如果发现不匹配，就利用跳转表进行快速跳转，从而避免了不必要的比较，提高了匹配效率。KMP算法的时间复杂度为O(n+m)，其中n和m分别为文本串和模式串的长度。

二、原理

1.

图片

首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

2.

图片

因为B与A不匹配，搜索词再往后移。

3.

图片

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

4.

图片

接着比较字符串和搜索词的下一个字符，还是相同。

5.

图片

直到字符串有一个字符，与搜索词对应的字符不相同为止。

6.

图片

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。

7.

图片

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

8.

图片

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

9.

图片

已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值
因为 6 - 2 等于4，所以将搜索词向后移动4位。

10.

图片

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

11.

图片

因为空格与A不匹配，继续后移一位。

12.

图片

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

13.

图片

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

14.

图片

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

15.

图片

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

－　“A”的前缀和后缀都为空集，共有元素的长度为0；
－　“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
－　“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－　“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－　“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
－　“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
－　“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
16.

图片

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

三、应用例题

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

参考：字符串匹配的KMP算法 - 阮一峰的网络日志 (ruanyifeng.com)