第 14 章 程序员常用 10 种算法

1、二分查找算法

1.1、二分查找算法介绍

前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式

二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找

二分查找法的运行时间为对数时间O(log2n) ，即查找到需要的目标位置最多只需要log2n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为log2100 , 即最多需要查找7次( 2^6 < 100 < 2^7)

1.2、二分查找算法思路

• 二分查找需要将数组分为两个部分：左边和右边，所以需要三个指针来记录位置

left ：数组左边界，初始值为 0

right ：数组右边界，初始值为 arr.length - 1

mid ：数组中间值指针，mid = (left + right) / 2

• 目标值 value 与 mid 所指向的值相比较

value == arr[mid] ：找到，返回

value < arr[mid] ：目标值在数组左边，下次需要在 left~(mid-1) 内搜索

value > arr[mid] ：目标值在数组右边，下次需要在 (mid+1))~(right) 内搜索

• 何时停止？left > right 时，表示没有找到，返回索引 -1

1.3、二分查找算法实现

• 代码实现

public class BinarySearchNoRecur {
  public static void main(String[] args) {
    // 测试
    int[] arr = { 1, 3, 8, 10, 11, 67, 100 };
    int index = binarySearch(arr, 100);
    System.out.println("index=" + index);
  }
  // 二分查找的非递归实现
  /**
   * 
   * @param arr    待查找的数组, arr是升序排序
   * @param target 需要查找的数
   * @return 返回对应下标，-1表示没有找到
   */
  public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) { // 说明继续查找
      int mid = (left + right) / 2;
      if (arr[mid] == target) {
        return mid;
      } else if (arr[mid] > target) {
        right = mid - 1;// 需要向左边查找
      } else {
        left = mid + 1; // 需要向右边查找
      }
    }
    return -1;
  }
}

• 程序运行结果

index=6

2、分治算法

2.1、分治算法介绍

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

分治算法可以求解的一些经典问题

二分搜索

大整数乘法

棋盘覆盖

合并排序

快速排序

线性时间选择

最接近点对问题

循环赛日程表

汉诺塔

2.2、分治算法基本步骤

• 分治法在每一层递归上都有三个步骤：

• 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
• 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
• 合并：将各个子问题的解合并为原问题的解。

2.3、分治算法设计模式

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。

ADHOC§是该分治法中的基本子算法，用于直接解小规模的问题P。

因此，当P的规模不超过n0时直接用算法ADHOC§求解。

算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解

if |P|≤n0
   then return(ADHOC(P))
//将P分解为较小的子问题 P1 ,P2 ,…,Pk
for i←1 to k
do yi ← Divide-and-Conquer(Pi)   // 递归解决Pi
T ← MERGE(y1,y2,…,yk)   // 合并子问题
return(T)

2.4、汉诺塔问题

2.4.1、汉诺塔介绍

• 汉诺塔的传说：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
• 假如每秒钟一次，共需多长时间呢？移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

2.4.2、分治思路

如果 A 塔上只有一个盘子：

直接将 A 塔的盘子移动到 C 塔：A —> C

如果 A 塔上有两个盘子：

先将 A 塔上面的盘子移动到 B 塔：A —> B

再将 A 塔最下面的盘子移动到 C 塔：A --> C

最后将 B 塔上面的盘子移动到 C 塔：B --> C

如果 A 塔上有三个盘子：

n >= 2 时，就体现出了分治算法的思想：我们将 A 塔上面的盘子看作一个整体，最下面的单个盘子单独分离出来，分三步走

先将 A 塔上面的盘子看作一个整体，移动到 B 塔（把 C 塔当做中转站）

这样 A 塔就只剩下一个最大的盘子，将 A 塔剩下的盘子移动到 C 塔

最后将 B 塔上面的盘子移动到 C 塔（把 A 塔当做中转站）

2.4.3、代码实现

• 解决汉诺塔问题：

public class Hanoitower {
  public static void main(String[] args) {
    hanoiTower(3, 'A', 'B', 'C');
  }
  //汉诺塔的移动的方法
  //使用分治算法
  public static void hanoiTower(int num, char a, char b, char c) {
    //如果只有一个盘
    if(num == 1) {
      System.out.println("第1个盘从 " + a + "->" + c);
    } else {
      //如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
      //1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
      hanoiTower(num - 1, a, c, b);
      //2. 把最下边的盘 A->C
      System.out.println("第" + num + "个盘从 " + a + "->" + c);
      //3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔  
      hanoiTower(num - 1, b, a, c);
    }
  }
}

• 程序运行结果

第1个盘从 A->C
第2个盘从 A->B
第1个盘从 C->B
第3个盘从 A->C
第1个盘从 B->A
第2个盘从 B->C
第1个盘从 A->C

3、动态规划算法

3.1、应用场景

• 背包问题：有一个背包，容量为4磅 ， 现有如下物品

• 要求达到的目标为装入的背包的总价值最大，并且重量不超出
• 要求装入的物品不能重复

3.2、动态规划算法介绍

• 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
• 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
• 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
• 动态规划可以通过填表的方式来逐步推进，得到最优解

3.3、背包问题

3.3.1、背包问题介绍

• 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是：每种物品都有无限件可用)
• 这里的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。

3.3.2、代码思路

• 背包容量为 4 磅，物品价格以及重量表如下：

• 先来填表 v ，对应着数组 v[][]，我来解释下这张表：

算法的主要思想：利用动态规划来解决。

每次遍历到的第 i 个物品，根据 w[i - 1]（物品重量）和 val[i - 1]（物品价值）来确定是否需要将该物品放入背包中，C为背包的容量

v[i][j]表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值

• 对于第一行(i=1)，目前只有吉他可以选择，这时不管背包容量多大，也只能放一把吉他

对于第二行(i=2)，目前存在吉他和音响可以选择，新物品为音响，重量为 4 磅，尝试将其放入背包

在 v[2][4] 单元格，尝试将音响放入容量为 4 磅的背包中，看看背包还剩多少容量？还剩 0 磅，再去找找 0 磅能放入最大价值多高的物品：v[1][0] = 0

与上一次 v[1][4] 比较 ， v[1][4] < v[2][4] ，发现确实比之前放得多，采取此方案

• 对于第三行(i=3)，目前存在吉他和音响、电脑可以选择，新物品为电脑，重量为 3 磅，尝试将其放入背包

当背包容量为 3 磅时，可以放入电脑

在 v[3][3] 单元格，尝试将电脑放入容量为 3 磅的背包中，看看背包还剩多少容量？还剩 0 磅，再去找找 0 磅能放入最大价值多高的物品：v[2][0] = 0

与上一次 v[2][3] 比较 ， v[2][3] < v[3][3] ，发现确实比之前放得多，采取此方案

• 当背包容量为 4 磅时，可以放入电脑

在 v[3][4] 单元格，尝试将电脑放入容量为 4 磅的背包中，看看背包还剩多少容量？还剩 1 磅，再去找找 1 磅能放入最大价值多高的物品：v[2][1] = 1500 ，所以总共能放入的重量为 v[3][4] = 3500

与上一次 v[2][4] 比较 ， v[2][4] < v[3][4] ，发现确实比之前放得多，采取此方案

总结公式：

• 当前新增物品的重量 > 背包的重量，则直接拷贝上次的方案

if (w[i - 1] > j) { // 因为我们程序i 是从1开始的，所以是 w[i-1]
    v[i][j] = v[i - 1][j];
}

• 当前新增物品的重量 <= 背包的重量

• 尝试将新物品放入背包，看看还剩多少容量
• 尝试剩余的容量填满，看看此时背包里物品的价值和上次比，哪个更大，取价格更大的方案即可

if (w[i - 1] <= j) { // 因为我们程序i 是从1开始的，所以是 w[i-1]
    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
}

为什么可以这样做？将大问题拆成小问题

• 第一步：求得第一步步骤的最优解
• 第二步：求得第二步步骤的最优解，第二步的最优解依赖于第一步的最优解
• …
• 第 n 步：求得第 n 步步骤的最优解，第 n 步的最优解依赖于第 n-1 步的最优解

3.3.3、代码实现

• 背包问题算法

public class KnapsackProblem {
  public static void main(String[] args) {
    int[] w = { 1, 4, 3 };// 物品的重量
    int[] val = { 1500, 3000, 2000 }; // 物品的价值 这里val[i]
    int m = 4; // 背包的容量
    int n = val.length; // 物品的个数
    // 创建二维数组，
    // v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
    int[][] v = new int[n + 1][m + 1];
    // 为了记录放入商品的情况，我们定一个二维数组
    int[][] path = new int[n + 1][m + 1];
    // 初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
    for (int i = 0; i < v.length; i++) {
      v[i][0] = 0; // 将第一列设置为0
    }
    for (int i = 0; i < v[0].length; i++) {
      v[0][i] = 0; // 将第一行设置0
    }
    // 根据前面得到公式来动态规划处理
    for (int i = 1; i < v.length; i++) { // 不处理第一行 i是从1开始的
      for (int j = 1; j < v[0].length; j++) {// 不处理第一列, j是从1开始的
        // 公式
        if (w[i - 1] > j) { // 因为我们程序i 是从1开始的，所以是 w[i-1]
          v[i][j] = v[i - 1][j];
        } else {
          // 说明:
          // 因为我们的i 从1开始的， 因此公式需要调整成
          // v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
          // 为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
          if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
            v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
            // 把当前的情况记录到path
            path[i][j] = 1;
          } else {
            v[i][j] = v[i - 1][j];
          }
        }
      }
    }
    // 输出一下v 看看目前的情况
    for (int i = 0; i < v.length; i++) {
      for (int j = 0; j < v[i].length; j++) {
        System.out.print(v[i][j] + "\t ");
      }
      System.out.println();
    }
    System.out.println("============================");
    // 动脑筋
    int i = path.length - 1; // 行的最大下标
    int j = path[0].length - 1; // 列的最大下标
    while (i > 0 && j > 0) { // 从path的最后开始找
      if (path[i][j] == 1) {
        System.out.printf("第%d个商品放入到背包\n", i);
        j -= w[i - 1]; // w[i-1]
      }
      i--;
    }
  }
}

• 程序运行结果

0  0   0   0   0   
0  1500  1500  1500  1500  
0  1500  1500  1500  3000  
0  1500  1500  2000  3500  
============================
第3个商品放入到背包
第1个商品放入到背包

3.4、爬楼梯问题

3.4.1、代码思路

• 当 n < 0 时，无解
• 当 n = 1 时，f (n) = 1
• 当 n = 2 时，有两种方法：

走两次一级楼梯

一下走两级楼梯

• 当 n > 2 时，设总共的跳法为 f(n) 中，第一次跳一级还是两级，决定了后面剩下的台阶的跳法数目的不同：

如果第一次只跳一级，则后面剩下的n-1级台阶的跳法数目为 f(n-1)

如果第一次跳两级，则后面剩下的 n-2 级台阶的跳法数目为 f(n-2)

• 所以，得出递归方程，f(n) = f(n-1) + f(n-2)，问题本质是斐波那契数列。

3.4.2、代码实现

/**上台阶问题，dp**/
public static int climbStairs(int n) {
    if(n==0) return -1;
    if(n==1) return 1;
    int []dp = new int [n];
    dp[0] =1;
    dp[1] =2;
    for(int i=0;i<n-2;i++) {
        dp[i+2]=dp[i]+dp[i+1];
    }
    return dp[n-1];
}

4、KMP 算法

4.1、应用场景

• 字符串匹配问题：

• 有一个字符串 str1= ““硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好””，和一个子串 str2=“尚硅谷你尚硅你”
• 现在要判断 str1 是否含有 str2，如果存在，就返回第一次出现的位置，如果没有，则返回-1

4.2、暴力匹配算法

4.2.1、暴力匹配代码思路

如果用暴力匹配的思路，需要两个指针：i ，j ，i 表示现在 str1 匹配到索引为 i 的位置，子串str2 匹配到索引为 j 的位置

如果当前字符匹配成功（即str1[i] == str2[j]），则i++，j++，继续匹配下一个字符

如果失配（即str1[i]! = str2[j]），令 i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为 0

用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。(不可行!)

为什么匹配失败后，要令指针 i 回溯匹配起始位置的下一个位置？就比如说 001112 和 112 ，当 i 扫描至 str1[4] ，j 扫描至 str2[4] 时，发现字符串不匹配。i 重新回到 str1[2] 的下一个位置 str1[3] ，继续执行扫描，str1[3~5] 和 str2[0~2] 相等，匹配成功

4.2.2、暴力匹配代码

• 代码

public class ViolenceMatch {
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    // 测试暴力匹配算法
    String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
    String str2 = "尚硅谷你尚硅你";
    int index = violenceMatch(str1, str2);
    System.out.println("index=" + index);
  }
  // 暴力匹配算法实现
  public static int violenceMatch(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int s1Len = s1.length;
    int s2Len = s2.length;
    int i = 0; // i索引指向s1
    int j = 0; // j索引指向s2
    while (i < s1Len && j < s2Len) {// 保证匹配时，不越界
      if (s1[i] == s2[j]) {// 匹配ok
        i++;
        j++;
      } else { // 没有匹配成功
        // 如果失配（即str1[i]! = str2[j]），令i = i - (j - 1)，j = 0。
        i = i - (j - 1);
        j = 0;
      }
    }
    // 判断是否匹配成功
    if (j == s2Len) {
      return i - j;
    } else {
      return -1;
    }
  }
}

• 程序运行结果

index=15

4.3、KMP 算法

4.3.1、KMP 算法介绍

KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法.

KMP方法算法利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间

参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

4.3.2、KMP 算法流程

• 举例来说，有一个字符串 Str1 = “BBC ABCDAB ABCDABCDABDE”，判断，里面是否包含另一个字符串 Str2 = “ABCDABD”？
• 首先，第一步用Str1的第一个字符和Str2的第一个字符去比较，不符合，关键词向后移动一位

• 重复第一步，还是不符合，再后移

• 一直重复，直到Str1有一个字符与Str2的第一个字符符合为止

• 接着比较字符串和搜索词的下一个字符，还是符合

• 遇到Str1有一个字符与Str2对应的字符不符合

• 这时候，想到的是继续遍历Str1的下一个字符，重复第1步

其实是很不明智的，因为此时BCD已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”

为什么我知道 BCD已经比较过了呢？待匹配的子串为 ABCDABD ，当在源字符串中匹配至 ABCDABX（X != D） 时， BCD 很明显不可能与字符串 A 匹配成功，但ABX 有可能与 ABC 相等，所以 ABXXXXX 有可能与 ADCDABD 匹配成功，所以我们直接将搜索位置向后移动 4 个位置

KMP 算法的想法是，设法利用这个已知信息，不要把搜索位置移回已经比较过的位置，继续把它向后移，这样就提高了效率

• 怎么做到把刚刚重复的步骤省略掉？可以对Str2计算出一张《部分匹配表》，这张表的产生在后面介绍

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

移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动 4 位。

说白了，不就是字符串 ABCDAB 的后缀中包含 AB ，前缀也包含了 AB

当我们匹配到了 ABCDABX（X != D） 时，其实 BCD 部分其实无须再去匹配，但因为后缀 ABX 有可能等于 ABC ，所以需要从 ABX 中的 A 开始匹配，

相同的前后缀 AB 长度为 2 ，所以搜索位置向后移动 4 位（待匹配的子串长度 - 相同的前后缀长度）

• 因为空格与Ｃ不匹配，搜索词还要继续往后移。

这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位。

来仔细想想，为啥是向后移动 2 位？

当我们匹配到 ABX（X != C）时，我们需要考虑搜索位置往后面移动多少个位置

由于字符串 AB 没有相同的前后缀，所以部分匹配值为 0 ，也就是说，如果匹配不到子串 匹配到 ABX（X != C） ，直接从 X 的位置开始继续搜索，因为字符串 AB 中没有相同的前后缀~~~

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

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

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

4.3.3、部分匹配表

• 有没有想过部分匹配表怎么产生的？首先我们先介绍字符串的前缀，后缀是什么？

• “部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”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。

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

4.3.4、KMP 算法实现

1、计算部分匹配表

• KMP 中的关键就是求公共最长匹配前缀和后缀的长度了（多读几遍这句话，你就懂了）
• next 数组的含义：next[i] 表示原字符串的子串 str.subString(0, i) 中，前缀和后缀的最长的共有元素的长度
• 首先，如果只包含单个字符的字符串，其部分匹配表为 { 0 } ，所以next[0] = 0;
• 然后索引 i 从 1 ~ dest.length() 递增，依次求取每个子串的部分匹配表，就很神奇，下一次子串的部分匹配表的求解依赖于上一次子串的部分匹配表（具体看下面）
• 索引 j 的含义：

索引 j 指向当前待匹配字符的索引，每当匹配到一个字符时，索引 j 便执行 +1 操作

比如匹配 ABCDA 时，i 指向最后一个 A ，即 i == 4 ，此时 j 还是 0 ，匹配到 str[i] == str[j] ，j +=1 ，为下一次匹配做准备

• 怎么求每个子串的部分匹配值呢？以 ABCDABD 为例

A 的部分匹配表为 { 0 } ，那么 AB、ABC、ABCD、ABCDA、ABCDAB、ABCDABD 的部分匹配表要怎么计算呢？其实每个字符串的部分匹配表都要根据上一个子串的部分匹配表来计算

• 比如我们需要求 ABCDAB 的部分匹配表

我们在上一步已经求出 ABCDA 的部分匹配表为 { 0, 0, 0, 0, 1 }

此时 i == 5 ，j == 1 ，我们尝试匹配 str[j] 和 str[i] ：str[j] == str[i] == ‘B’ ，匹配成功，我们在上一步部分匹配表的基础上，对最后一个部分匹配值进行 +1 操作

所以我们求得 ABCDAB 的部分匹配表为 { 0, 0, 0, 0, 1, 2 }

• 再来，我们现在继续求 ABCDABD 的部分匹配表

我们在上一步已经求出 ABCDAB 的部分匹配表为 { 0, 0, 0, 0, 1, 2 }

此时 i == 6 ，j == 2 ，我们尝试匹配 str[j] 和 str[i] ：str[j] == ‘C’ ， str[i] == ‘D’ ，发现 str[j] != str[i]

我们进行匹配，发现 “ABC” != “ABD” 时，j 就应该进行回退，索引 j 肯定需要往前面回溯，那么 j 怎么回溯呢？

举个例子：“ABCX” 和 “ABDX” ，其中X为任意字符，因为有字符 D 的存在，如果想要前缀与后缀匹配，只能再从头开始算起，所以j需要回退到 ABC 中的 A 字符，即 j = next[j - 1];

// 获取到一个字符串(子串) 的部分匹配表

// 获取到一个字符串(子串) 的部分匹配表
public static int[] kmpNext(String dest) {
    // 创建一个next 数组保存部分匹配值
    int[] next = new int[dest.length()];
    next[0] = 0; // 如果字符串是长度为1 部分匹配值就是0
    for (int i = 1, j = 0; i < dest.length(); i++) {
        // 当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
        // 直到我们发现 有 dest.charAt(i) == dest.charAt(j)成立才退出
        // 这是kmp算法的核心点
        while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
            j = next[j - 1];
        }
        // 当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
        if (dest.charAt(i) == dest.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

看到一篇写 KMP 的博客，写得还不错

参考资料：https://blog.csdn.net/dark_cy/article/details/88698736

2、执行 KMP 搜索

索引 i 从 0 ~ dest.length() 递增，依次与目标子串中的字符进行比较

next[] 为部分搜索表

如果当前字符匹配成功，则 j++ ，为匹配下一个字符做准备

如果当前字符匹配失败，则 j 往前回溯，具体做法是：从子串的部分匹配表中，获取当前需要从子串的哪个索引位置开始继续执行匹配（j = next[j - 1]），目的是为了跳过那些没有必要再比较的字符

// 写出我们的kmp搜索算法
/**
 * 
 * @param str1 源字符串
 * @param str2 子串
 * @param next 部分匹配表, 是子串对应的部分匹配表
 * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
 */
public static int kmpSearch(String str1, String str2, int[] next) {
  // 遍历
  for (int i = 0, j = 0; i < str1.length(); i++) {
    // 需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
    // KMP算法核心点, 可以验证...
    while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
      j = next[j - 1];
    }
    if (str1.charAt(i) == str2.charAt(j)) {
      j++;
    }
    if (j == str2.length()) { // 找到了
      return i - j + 1;
    }
  }
  return -1;
}

3、代码测试

• 首先计算待搜索子串的部分匹配表
• 然后从利用子串的部分匹配表，在源字符串中进行搜索

public static void main(String[] args) {
    String str1 = "BBC ABCDAB ABCDABCDABDE";
    String str2 = "ABCDABD";
    // String str2 = "BBC";
    int[] next = kmpNext("ABCDABD"); // [0, 1, 2, 0]
    System.out.println("next=" + Arrays.toString(next));
    int index = kmpSearch(str1, str2, next);
    System.out.println("index=" + index); // 15
}

• 程序运行结果

next=[0, 0, 0, 0, 1, 2, 0] index=15

5、贪心算法

5.1、应用场景(集合覆盖问题)

• 假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号

5.2、贪心算法介绍

• 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
• 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

5.3、集合覆盖问题

5.3.1、穷举法缺点

• 如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有 2ⁿ -1 个,假设每秒可以计算10个子集，

5.3.2、代码思路

• 目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高
• 在选择策略上，因为需要覆盖全部地区的最小集合，大致思路如下：

声明几个辅助变量：

ArrayList selects;：存放已经选取的电台，比如 { K1, K2, …}

HashSet allAreas; ：存放当前还未覆盖的地区

String maxKey = null; ：存放当前能覆盖最多未覆盖地区的电台，比如 K1、K2

• 在所有电台中，找到一个能覆盖最多还未覆盖地区的电台（此电台可能包含一些已覆盖的地区，但没有关系）：maxKey
• 将其加入到 selects 集合中，表示已经选了该电台
• 将 maxKey 电台中的地区从 allAreas 中移除
• 重复如上步骤，直至 allAreas 为空

5.3.3、代码实现

• 使用贪心算法解决集合覆盖问题

public class GreedyAlgorithm {
  public static void main(String[] args) {
    // 创建广播电台,放入到Map
    HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
    // 将各个电台放入到broadcasts
    HashSet<String> hashSet1 = new HashSet<String>();
    hashSet1.add("北京");
    hashSet1.add("上海");
    hashSet1.add("天津");
    HashSet<String> hashSet2 = new HashSet<String>();
    hashSet2.add("广州");
    hashSet2.add("北京");
    hashSet2.add("深圳");
    HashSet<String> hashSet3 = new HashSet<String>();
    hashSet3.add("成都");
    hashSet3.add("上海");
    hashSet3.add("杭州");
    HashSet<String> hashSet4 = new HashSet<String>();
    hashSet4.add("上海");
    hashSet4.add("天津");
    HashSet<String> hashSet5 = new HashSet<String>();
    hashSet5.add("杭州");
    hashSet5.add("大连");
    // 加入到map
    broadcasts.put("K1", hashSet1);
    broadcasts.put("K2", hashSet2);
    broadcasts.put("K3", hashSet3);
    broadcasts.put("K4", hashSet4);
    broadcasts.put("K5", hashSet5);
    // allAreas 存放所有的地区
    HashSet<String> allAreas = new HashSet<String>();
    for (Entry<String, HashSet<String>> broadcast : broadcasts.entrySet()) {
      allAreas.addAll(broadcast.getValue());
    }
    // 创建ArrayList, 存放选择的电台集合
    ArrayList<String> selects = new ArrayList<String>();
    // 定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖地区的交集
    HashSet<String> tempSet = new HashSet<String>();
    // 定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
    // 如果maxKey 不为null , 则会加入到 selects
    String maxKey = null;
    Integer maxCount = 0;
    Integer curCount = 0;
    while (allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区
      // 每进行一次while，需要重置指针，重置计数器
      maxKey = null;
      maxCount = 0;
      // 遍历 broadcasts, 取出对应key
      for (String key : broadcasts.keySet()) {
        // 每进行一次for清除tempSet
        tempSet.clear();
        // 当前这个key能够覆盖的地区
        HashSet<String> areas = broadcasts.get(key);
        tempSet.addAll(areas);
        // 求出tempSet 和 allAreas 集合的交集, 交集会赋给 tempSet
        tempSet.retainAll(allAreas);
        // 当前站台可以覆盖额外的多少个城市
        curCount = tempSet.size();
        // 如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多，就需要重置maxKey
        // curCount > maxCount 体现出贪心算法的特点,每次都选择最优的
        if (curCount > maxCount) {
          maxKey = key;
          maxCount = curCount;
        }
      }
      // maxKey != null, 就应该将maxKey 加入selects
      if (maxKey != null) {
        selects.add(maxKey);
        // 将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉
        allAreas.removeAll(broadcasts.get(maxKey));
      }
    }
    System.out.println("得到的选择结果是" + selects);// [K1,K2,K3,K5]
  }
}

• 程序运行结果

得到的选择结果是[K1, K2, K3, K5]

5.4、注意事项

贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

比如上题的算法选出的是K1, K2, K3, K5，符合覆盖了全部的地区

但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果K2 的使用成本低于K1,那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的