数据结构与算法之美（三） 字符串匹配

字符串匹配

BF算法

BF算法是最简单也是最暴力的一种方法，即模式串依次在主串的第i个位置开始进行比较，相同则继续比较，不同就移至下一位重新比较。

kotlin复制代码package algorithm.string_match;

/**
 * @author EnochStar
 * @title: BF
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/8 11:56
 */
public class BF {
    public boolean isMatching(String mainString,String sonString) {
        if (mainString == null || sonString == null) {
            return false;
        }
        for (int i = 0;i < mainString.length() - sonString.length() + 1;i++) {
            for (int j = 0;j < sonString.length();j++) {
                if (mainString.charAt(i + j) != sonString.charAt(j)) {
                    break;
                }
                if (j == sonString.length() - 1) return true;
            }
        }
        return false;
    }
}

极端情况下时间复杂度为O（n*m）（如：主串”aaaaaaaaaa…..“ 子串”aaaaaab“），尽管时间复杂度很高，但他是最常用的字符串匹配算法。原因如下：

1、在大多数情况下，主串和子串的长度不会特别长，同时子串在中途遇到不能匹配的字符时，就停止匹配了，所以不会完全遍历子串

2、该算法实现简单，当出现bug时也容易发现并修正。

RK算法

其思路是利用哈希算法，求得主串下的所有与模式串相同长度的子串的哈希值，这样只要比较哈希值即可确认主串中是否存在子串。关键就在于求主串下所有子串的哈希值所消耗的时间。

由图可知h[i]与h[i-1]存在一定的关系。

用数学表达可知，h[i] = 26h[i - 1] - 26^m(s[i - 1] - 'a') + s[i + m - 1] - 'a'.

arduino复制代码package algorithm.string_match;

import java.util.HashSet;
import java.util.Set;

/**
 * @author EnochStar
 * @title: RK
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/8 14:17
 */
public class RK {
    private Set<Long> set = new HashSet();

    public boolean matching(String mainString,String sonString) {
        int m = sonString.length();
        initSonOfMainHash(mainString,m);
        long base = initBase(sonString,m);

        return set.contains(base);
    }
    private void initSonOfMainHash(String mainString,int m){
        long base = initBase(mainString,m);
        set.add(base);
        for (int i = 1;i < mainString.length() - m + 1;i++) {
            base = (long) (26 * base - Math.pow(26,m) * (mainString.charAt(i - 1) - 'a')
            + (mainString.charAt(i + m - 1) - 'a'));
            set.add(base);
        }
    }
    private long initBase(String s,int m) {
        long base = 0;
        for (int i = 0;i < m;i++) {
            base += Math.pow(26,m - i - 1) * (s.charAt(i) - 'a');
        }
        return base;
    }

}

由关系表达式，只需要O(n)的时间复杂度即可求得主串下所有子串的哈希值，用set判断模式串的哈希值是否存在也只需要O(n)的时间复杂度，故该方法的时间复杂度为O(n)，但存在缺陷，如果模式串和主串的长度都非常的长，超过了数值的范围，那么这种方法就不可取了，这时候只能允许哈希冲突，当存在哈希值的时候再使用BK算法进行判断。

BM

ini复制代码package algorithm.string_match;

import java.util.Arrays;

/**
 * @author EnochStar
 * @title: BM
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/9 14:58
 */
public class BM {

    // 用于存储坏字符最后一次出现在模式串的位置
    private int[] table = new int[256];

    public int bm(char[] a,int n,char[] b,int m){
        initTable(b,m);
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        initSuffixAndPrefix(b,m,suffix,prefix);
        int i = 0;
        while (i <= n - m) {
            int j;
            for (j = m - 1;j >= 0;j--) {
                if (a[i + j] != b[j]) break;
            }
            if (j < 0) return i;
            int moveBad =j - table[a[j + i]];
            int y = 0;
            if (j < m - 1) {
                y = moveGood(j,m,prefix,suffix);
            }
            i = i + Math.max(y,moveBad);
        }
        return -1;
    }
    private int moveGood(int j,int m,boolean[] prefix,int[] suffix) {
        int k = m - 1 - j;
        if (suffix[k] != -1) {
            return j - suffix[k] + 1;
        }
        for (int r = j + 2;r <= m - 1;r++) {
            if (prefix[m - r]) return r;
        }
        return m;
    }
    private void initTable(char[] b,int m) {
        Arrays.fill(table, -1);
        for (int i = 0;i < m;i++) {
            int ascii = (int)b[i];
            table[ascii] = i;
        }
    }
    private void initSuffixAndPrefix(char[] b,int m,int[] suffix,boolean[] prefix){
        Arrays.fill(suffix,-1);
        Arrays.fill(prefix,false);
        for (int i = 0;i < m - 1;i++) {
            int j = i;
            int k = 0;
            while (j >= 0 && b[j] == b[m - 1 - k]) {
                --j;
                k++;
                suffix[k] = j + 1;
            }
            if (j == -1) prefix[k] = true;
        }
    }
}

KMP算法

ini复制代码package algorithm.string_match;

/**
 * @author EnochStar
 * @title: KMP
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/10 15:38
 */
public class KMP {
    public int kmp(char[] a,int n,char[] b,int m) {
        int[] next = generateNext(b);
        int j = 0;
        for (int i = 0;i < n - m + 1;i++) {
            while (j > 0 && a[i] != b[j]) {
                j = next[j - 1] + 1;
            }
            if (a[i] == b[j]) j++;
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
    private int[] generateNext(char[] b) {
        int len = b.length;
        int[] next = new int[len];
        int k = -1;
        next[0] = -1;
        for (int i = 1;i < len;i++) {
            while (k != -1 && b[i] != b[k + 1]) {
                k = next[k];
            }
            if (b[i] == b[k + 1]) {
                k++;
            }
            next[i] = k;
        }
        return next;
    }
}

字典树(Trie)

不同于kmp、rk、bm等算法，模式串-主串。他是将所有字符串统一加入到字典中，后续判断字符串是否存在于字典树中。

实现字典树

ini复制代码package algorithm.string_match;

/**
 * @author EnochStar
 * @title: Trie
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/11 10:48
 */
public class Trie {

    TrieNode head = new TrieNode();

    public void insert(char[] string) {
        TrieNode root = head;
        for (int i = 0;i  < string.length;i++) {
            int index = string[i] - 'a';
            if (root.childrenNode[index] == null) {
                TrieNode node = new TrieNode(string[i]);
                root.childrenNode[index] = node;
            }
            root = root.childrenNode[index];
        }
        root.isEnd = true;
    }

    public boolean find(char[] string) {
        TrieNode root = head;
        for (int i = 0;i < string.length;i++) {
            int index = string[i] - 'a';
            if (root.childrenNode[index] == null) {
                return false;
            }
            root = root.childrenNode[index];
        }
        return root.isEnd;
    }
}
class TrieNode{
    private char data;
    public TrieNode[] childrenNode = new TrieNode[26];
    public boolean isEnd;

    public TrieNode() {

    }

    public TrieNode(char data) {
        this.data = data;
    }
}

字典树的优缺点

字典树是一种空间换时间的思路，其本质虽然是避免存储相同前缀的字符串，但重复前缀并不多的情况下，每一个节点都需要存储26个字符，如果需要存储中文字符、数字等，那么需要更多的存储空间。面对空间浪费的情况，可以选择舍弃一定的查询效率，选择红黑树、有序数组、跳表、散列表等。

总结：Trie树使用的场景

1、不适用于字符集特别大的情况

2、要求字符串的前缀重合比较多

3、Trie由于用到了指针，所以对cpu缓存不友好。

Trie树不适合精确查找，比较适合查找前缀匹配的字符。因此可以用于搜索关键字的提示。

贪心算法

贪心算法是一种算法思想。指在对问题求解时，总是做出在当前看来是最好的选择。典型应用于哈夫曼编码。

在给定限定值和期望值的情况下，要求在满足限定值时使期望值达到最大。这个时候可以使用贪心算法。

当背包容量一定时，要求背包内的价值最大，可以对各个豆子求单位容量下的价值，然后从大到小依次放入背包中。

但有时贪心算法得到的也不是最优值。

贪心算法的思路，先找到和S相连权的最小边，直到找到T，路径为S -》 A -》E -》 T ,而最短路径为S -》B -》 D -》 T。

实战题

435. 无重叠区间 - 力扣（LeetCode） (leetcode-cn.com)

402. 移掉 K 位数字 - 力扣（LeetCode） (leetcode-cn.com)

分治算法

分而治之，将原问题划分成n个规模较小，且结构与原问题相似的子问题，递归的解决这个子问题，再合并结果。

应用举例

求逆序对，暴力法为O（n^2）,可以采取分治法的思路，将原数组划分为A、B两个子数组，然后查询A数组内的逆序对和B数组内逆序对，以及A、B之间的逆序对。

ini复制代码class Solution {
    private int num;
    public int reversePairs(int[] nums) {
        num = 0;
        reverse(nums,0,nums.length - 1);
        return num;
    }
    public void reverse(int[] nums,int left,int right) {
        if(left >= right) {
            return;
        }
        int mid = ((right - left) >> 1) + left;
        reverse(nums,left,mid);
        reverse(nums,mid + 1,right);
        sort(nums,left,mid,right);
    }
    public void sort(int[] nums,int left,int mid,int right) {
        int l1 = left;
        int l2 = mid + 1;
        int[] tmp = new int[right - left + 1];
        int k = 0;
        while(l1 <= mid && l2 <= right) {
            if(nums[l1] <= nums[l2]) {
                tmp[k++] = nums[l1++];
            }else{
                num += (mid - l1 + 1);
                tmp[k++] = nums[l2++];
            }
        }
        while(l1 <= mid) {
            tmp[k++] = nums[l1++];
        }
        while(l2 <= right) {
            tmp[k++] = nums[l2++];
        }
        for(int i = 0;i < tmp.length;i++) {
            nums[i + left] = tmp[i];
        }
    }
}

剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode） (leetcode-cn.com)

回溯算法

回溯算法即枚举所有的解。

典型应用

八皇后

ini复制代码class Solution {
    private List<List<String>> res; 
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList();
        char[][] board = new char[n][n];
        init(board);
        tryPut(board,0,n);
        return res;
    }

    public void tryPut(char[][] board,int level,int n) {
        if(level == n) {
            res.add(convert(board));
            return;
        }
        for(int i = 0;i < n;i++) {
            board[level][i] = 'Q';
            if(isValid(board,level,i)) {
                tryPut(board,level + 1,n);
            }
            board[level][i] = '.';
        }
    }

    // 转化为String
    public List<String> convert(char[][] board) {
        List<String> tmp = new ArrayList();
        for(int i = 0;i < board.length;i++) {
            String s = new String(board[i]);
            tmp.add(s);
        }
        return tmp;
    }

    public boolean isValid(char[][] board,int level,int col) {
        for(int i = 0;i < level;i++) {
            if(board[i][col] == 'Q') return false;
        }
        for(int i = level - 1,j = col - 1;i >= 0 && j >= 0;) {
            if(board[i][j] == 'Q') return false;
            i--;
            j--;
        }
        for(int i = level - 1,j = col + 1;i >= 0 && j < board.length;) {
            if(board[i][j] == 'Q') return false;
            i--;
            j++;
        }
        return true;
    }

    // 初始化board
    public void init(char[][] board) {
        for(int i = 0;i < board.length;i++) {
            Arrays.fill(board[i],'.');
        }
    }
}

面试题 08.12. 八皇后 - 力扣（LeetCode） (leetcode-cn.com)

0-1背包

arduino复制代码public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值
// cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
// w背包重量；items表示每个物品的重量；n表示物品个数
// 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
// f(0, 0, a, 10, 100)
    public void f(int i, int cw, int[] items, int n, int w) {
        if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品
            if (cw > maxW) maxW = cw;
            return;
        }
        f(i + 1, cw, items, n, w);
        if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
            f(i + 1, cw + items[i], items, n, w);
        }
    }

正则表达式

“*“匹配0个到多个任意字符，”.”匹配0个或1个任意字符。实现正则表达式。

typescript复制代码package algorithm;

/**
 * @author EnochStar
 * @title: Pattern
 * @projectName basic_use
 * @description: “*”表示匹配0个到多个 “。”表示匹配0或1个任意字符
 * @date 2021/11/15 16:35
 */
public class Pattern {
    private boolean isMatched = false;
    // s为待匹配 p为正则表达式
    public boolean match(String s,String p) {
        rMatch(s,0,p,0);
        return isMatched;
    }
    public void rMatch(String s,int sIndex,String p,int pIndex) {
        if (isMatched) return;
        if (pIndex == p.length()) {
            if (sIndex == s.length()) {
                isMatched = true;
            }
            return;
        }
        if (s.charAt(sIndex) == p.charAt(pIndex)) {
            rMatch(s,sIndex + 1,p,pIndex + 1);
        }else if (p.charAt(pIndex) == '.') {
            rMatch(s,sIndex + 1,p,pIndex + 1);
            rMatch(s,sIndex,p,pIndex + 1);
        }else if(p.charAt(pIndex) == '*') {
            for (int i = sIndex;i < s.length();i++) {
                rMatch(s,i,p,pIndex + 1);
            }
        }
    }
}

动态规划（一）

以0-1背包为例，用回溯法解决：

arduino复制代码// 回溯算法实现。注意：我把输入的变量都定义成了成员变量。
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2, 2, 4, 6, 3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量

public void f(int i, int cw) { // 调用f(0, 0)
    if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
        if (cw > maxW) maxW = cw;
        return;
    }
    f(i + 1, cw); // 选择不装第i个物品
    if (cw + weight[i] <= w) {

        f(i + 1, cw + weight[i]); // 选择装第i个物品
    }
}

如图，有很多重复的计算，可以通过备忘录避免冗余计算。

ini复制代码private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2, 2, 4, 6, 3
}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
private boolean[][] mem = new boolean[5][10]; // 备忘录，默认值false

public void f(int i, int cw) { // 调用f(0, 0)
    if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
        if (cw > maxW) maxW = cw;
        return;
    }
    if (mem[i][cw]) return; // 重复状态
    mem[i][cw] = true; // 记录(i, cw)这个状态
    f(i + 1, cw); // 选择不装第i个物品
    if (cw + weight[i] <= w) {
        f(i + 1, cw + weight[i]); // 选择装第i个物品
    }
}

采用动规思路，可以将求解分为n个阶段，每个阶段会决策物品是否放入背包，决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，我们把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过w个（w表示背包的承载重量）

ini复制代码// weight:物品重量，n:物品个数，w:背包可承载重量
public int knapsack(int[] weight, int n, int w) {
    boolean[][] states = new boolean[n][w+1]; // 默认值false
    states[0][0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
    states[0][weight[0]] = true;
    for (int i = 1; i < n; ++i) { // 动态规划状态转移
        for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包
            if (states[i-1][j] == true) states[i][j] = states[i-1][j];
        }
        for (int j = 0; j <= w-weight[i]; ++j) {//把第i个物品放入背包
            if (states[i-1][j]==true) states[i][j+weight[i]] = true;
        }
    }
    for (int i = w; i >= 0; --i) { // 输出结果
        if (states[n-1][i] == true) return i;
    }
    return 0;
}

回溯法的时间复杂度根据回溯树可知，为O（2 ^ n），而动规的时间复杂度为O（ｎ＊ｗ），可以对空间复杂度进行进一步的优化。

arduino复制代码public static int knapsack2(int[] items, int n, int w) {
    boolean[] states = new boolean[w+1]; // 默认值false
    states[0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
    states[items[0]] = true;
    for (int i = 1; i < n; ++i) { // 动态规划
        for (int j = w-items[i]; j >= 0; --j) {//把第i个物品放入背包
            if (states[j]==true) states[j+items[i]] = true;
        }
    }
    for (int i = w; i >= 0; --i) { // 输出结果
        if (states[i] == true) return i;
    }
    return 0;
}

当要求满足最大价格限制前提下，使总价格最大：

ini复制代码private int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private int[] weight = {2, 2, 4, 6, 3}; // 物品的重量
private int[] value = {3, 4, 8, 9, 6}; // 物品的价值
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量

public void f(int i, int cw, int cv) { // 调用f(0, 0, 0)
    if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了

        if (cv > maxV) maxV = cv;
        return;
    }
    f(i + 1, cw, cv); // 选择不装第i个物品
    if (cw + weight[i] <= w) {
        f(i + 1, cw + weight[i], cv + value[i]); // 选择装第i个物品
    }
}

由图可知，在（i，cw）相同的情况下，只需要考虑value最大的即可，此时回溯法无法用备忘录解决。
动规实现：

ini复制代码public static int knapsack3(int[] weight, int[] value, int n, int w) {
    int[][] states = new int[n][w+1];
    for (int i = 0; i < n; ++i) { // 初始化states
        for (int j = 0; j < w+1; ++j) {
            states[i][j] = -1;
        }
    }
    states[0][0] = 0;
    states[0][weight[0]] = value[0];
    for (int i = 1; i < n; ++i) { //动态规划，状态转移
        for (int j = 0; j <= w; ++j) { // 不选择第i个物品
            if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];
        }
        for (int j = 0; j <= w-weight[i]; ++j) { // 选择第i个物品
            if (states[i-1][j] >= 0) {
                int v = states[i-1][j] + value[i];
                if (v > states[i][j+weight[i]]) {
                    states[i][j+weight[i]] = v;
                }
            }
        }
    }
    // 找出最大值
    int maxvalue = -1;
    for (int j = 0; j <= w; ++j) {
        if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];
    }
    return maxvalue;
}

思考

双十一想要薅羊毛，提供满200的优惠，现购物车有一系列商品，要求在能薅羊毛的前提下，使得商品价格最少，即大于200的最小值。

ini复制代码// items商品价格，n商品个数, w表示满减条件，比如200
public static void double11advance(int[] items, int n, int w) {
    boolean[][] states = new boolean[n][3*w+1];//超过3倍就没有薅羊毛的价值了
    states[0][0] = true; // 第一行的数据要特殊处理
    states[0][items[0]] = true;
    for (int i = 1; i < n; ++i) { // 动态规划
        for (int j = 0; j <= 3*w; ++j) {// 不购买第i个商品
            if (states[i-1][j] == true) states[i][j] = states[i-1][j];
        }
        for (int j = 0; j <= 3*w-items[i]; ++j) {//购买第i个商品
            if (states[i-1][j]==true) states[i][j+items[i]] = true;
        }
    }
    int j;
    for (j = w; j < 3*w+1; ++j) {
        if (states[n-1][j] == true) break; // 输出结果大于等于w的最小值
    }
    if (j == -1) return; // 没有可行解
    for (int i = n-1; i >= 1; --i) { // i表示二维数组中的行，j表示列
        if(j-items[i] >= 0 && states[i-1][j-items[i]] == true) {
            System.out.print(items[i] + " "); // 购买这个商品
            j = j - items[i];
        } // else 没有购买这个商品，j不变。
    }
    if (j != 0) System.out.print(items[0]);
}

练习

剑指 Offer II 100. 三角形中最小路径之和 - 力扣（LeetCode） (leetcode-cn.com)

动态规划（二）

一模型三特征

1、最优子结构。最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。

2、无后效性。第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。

3、重复子问题。不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态

解决动规的思路

1、状态转移表法。回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码。

2、状态转移方程。找最优子结构-写状态转移方程-将状态 转移方程翻译成代码。

四种思想的比较

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最 优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。

尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重 复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划 之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起 来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。）

思考

322. 零钱兑换 - 力扣（LeetCode） (leetcode-cn.com)

ini复制代码class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int coin : coins) {
            for(int j = coin;j <= amount;j++) {
                if(dp[j - coin] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j],dp[j - coin] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

动态规划（三）

在搜索引擎中输入错误的单词时，搜索引擎提供一个拼音纠错功能。他是如何量化两个字符之间的相似程度的呢？

编辑距离是将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越 小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是0。

编辑距离有两种计算方式。一个是莱文斯坦距离，另一个是最长公共子串长度。莱文斯坦距离允许增加、删除、 替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。分析相似度时，莱文斯坦距离的大小，表示两个字符串差异的大小；而最长公共子串的大小，表示两个字符串相似程度的大小。

莱文斯坦距离

如果a[i]与b[j]匹配，我们递归考察a[i+1]和b[j+1]。如果a[i]与b[j]不匹配，那我们有多种处理方式可选：

• 可以删除a[i]，然后递归考察a[i+1]和b[j]；
• 可以删除b[j]，然后递归考察a[i]和b[j+1]；
• 可以在a[i]前面添加一个跟b[j]相同的字符，然后递归考察a[i]和b[j+1];
• 可以在b[j]前面添加一个跟a[i]相同的字符，然后递归考察a[i+1]和b[j]；
• 可以将a[i]替换成b[j]，或者将b[j]替换成a[i]，然后递归考察a[i+1]和b[j+1]。

ini复制代码package algorithm.edit_distance;

/**
 * @author EnochStar
 * @title: LaiWenSiTan
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/18 11:16
 */
public class LaiWenSiTan {
    private char[] a = "mitcmu".toCharArray();
    private char[] b = "mtacnu".toCharArray();
    private int n = 6;
    private int m = 6;
    private int minDist = Integer.MAX_VALUE; // 存储结果
    // 调用方式 lwstBT(0, 0, 0);
    public void lwstBT(int i, int j, int edist) {
        if (i == n || j == m) {
            if (i < n) edist += (n-i);
            if (j < m) edist += (m - j);
            if (edist < minDist) minDist = edist;
            return;
        }
        if (a[i] == b[j]) { // 两个字符匹配
            lwstBT(i+1, j+1, edist);
        } else { // 两个字符不匹配
            lwstBT(i + 1, j, edist + 1); // 删除a[i]或者b[j]前添加一个字符
            lwstBT(i, j + 1, edist + 1); // 删除b[j]或者a[i]前添加一个字符
            lwstBT(i + 1, j + 1, edist + 1); // 将a[i]和b[j]替换为相同字符
        }
    }
}

递归树可知，(i,j)相同时，保留更小的edist，由此推断出状态转移方程

如果：a[i]!=b[j]，那么：min_edist(i, j)就等于： min(min_edist(i-1,j)+1, min_edist(i,j-1)+1, min_edist(i-1,j-1)+1) 如果：a[i]==b[j]，那么：min_edist(i, j)就等于： min(min_edist(i-1,j)+1, min_edist(i,j-1)+1，min_edist(i-1,j-1)) 其中，min表示求三数中的最小值。

ini复制代码public int lwstDP(char[] a, int n, char[] b, int m) {
    int[][] minDist = new int[n][m];
    for (int j = 0; j < m; ++j) { // 初始化第0行:a[0..0]与b[0..j]的编辑距离
        if (a[0] == b[j]) minDist[0][j] = j;
        else if (j != 0) minDist[0][j] = minDist[0][j-1]+1;
        else minDist[0][j] = 1;
    }
    for (int i = 0; i < n; ++i) { // 初始化第0列:a[0..i]与b[0..0]的编辑距离
        if (a[i] == b[0]) minDist[i][0] = i;
        else if (i != 0) minDist[i][0] = minDist[i-1][0]+1;
        else minDist[i][0] = 1;
    }
    for (int i = 1; i < n; ++i) { // 按行填表
        for (int j = 1; j < m; ++j) {
            if (a[i] == b[j]) minDist[i][j] = min(
                    minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]);
            else minDist[i][j] = min(
                    minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]+1);
        }
    }
    return minDist[n-1][m-1];
}
private int min(int x, int y, int z) {
    int minv = Integer.MAX_VALUE;
    if (x < minv) minv = x;
    if (y < minv) minv = y;
    if (z < minv) minv = z;
    return minv;
}

最长公共子串

ini复制代码package algorithm.edit_distance;

/**
 * @author EnochStar
 * @title: MaxLongSonString
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/18 11:22
 */
public class MaxLongSonString {
    public int lcs(char[] a, int n, char[] b, int m) {
        int[][] maxlcs = new int[n][m];
        for (int j = 0; j < m; ++j) {//初始化第0行：a[0..0]与b[0..j]的maxlcs
            if (a[0] == b[j]) maxlcs[0][j] = 1;
            else if (j != 0) maxlcs[0][j] = maxlcs[0][j-1];
            else maxlcs[0][j] = 0;
        }
        for (int i = 0; i < n; ++i) {//初始化第0列：a[0..i]与b[0..0]的maxlcs
            if (a[i] == b[0]) maxlcs[i][0] = 1;
            else if (i != 0) maxlcs[i][0] = maxlcs[i-1][0];
            else maxlcs[i][0] = 0;
        }
        for (int i = 1; i < n; ++i) { // 填表
            for (int j = 1; j < m; ++j) {
                if (a[i] == b[j]) maxlcs[i][j] = max(
                        maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]+1);
                else maxlcs[i][j] = max(
                        maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]);
            }
        }
        return maxlcs[n-1][m-1];
    }
    private int max(int x, int y, int z) {
        int maxv = Integer.MIN_VALUE;
        if (x > maxv) maxv = x;
        if (y > maxv) maxv = y;
        if (z > maxv) maxv = z;
        return maxv;
    }
}

优化纠错功能

针对纠错效果不好的问题，我们有很多种优化思路，我这里介绍几种。

• 我们并不仅仅取出编辑距离最小的那个单词，而是取出编辑距离最小的TOP 10，然后根据其他参数，决策选择哪个单词作为拼写纠错单词。
• 比如使用搜索热门程度来决定哪个单词作为拼写纠错单词。 我们还可以用多种编辑距离计算方法，比如今天讲到的两种，然后分别编辑距离最小的TOP 10，然后求交集，用交集的结果，再继续优化处理。
• 我们还可以通过统计用户的搜索日志，得到最常被拼错的单词列表，以及对应的拼写正确的单词。搜索引擎在拼写纠错的时候，首先在这个最长被拼错单词列表中查找。如果一旦找到，直接返回对应的正确的单词。 这样纠错的效果非常好。
• 我们还有更加高级一点的做法，引入个性化因素。针对每个用户，维护这个用户特有的搜索喜好，也就是常用的搜索关键词。当用户输入错误的单词的时候，我们首先在这个用户常用的搜索关键词中，计算编辑距 离，查找编辑距离最小的单词。
  针对纠错性能方面，我们也有相应的优化方式。我讲两种分治的优化思路。
• 如果纠错功能的TPS不高，我们可以部署多台机器，每台机器运行一个独立的纠错功能。当有一个纠错请求的时候，我们通过负载均衡，分配到其中一台机器，来计算编辑距离，得到纠错单词。
• 如果纠错系统的响应时间太长，也就是，每个纠错请求处理时间过长，我们可以将纠错的词库，分割到很多台机器。当有一个纠错请求的时候，我们就将这个拼写错误的单词，同时发送到这多台机器，让多台机器并 行处理，分别得到编辑距离最小的单词，然后再比对合并，最终决定出一个最优的纠错单词.

最短距离

迪杰斯特拉算法

单源最短路径（一个顶点到另一个顶点） 时间复杂度O（ElogV）

ini复制代码package algorithm.shortest_road;

import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * @author EnochStar
 * @title: Graph
 * @projectName basic_use
 * @description:
 * v表示顶点数
 * adj表示第i个顶点的出度即两个顶点间的权值
 * Edge存储某一点到另一点及两点的权值
 * Vertex存储从最起始点，到某一点的权值
 * @date 2021/11/19 15:07
 */
public class Graph {
    private int v;
    private LinkedList<Edge> adj[];

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0;i < v;i++) {
            adj[i] = new LinkedList<Edge>();
        }
    }
    public void addEdge(int s,int e,int c) {
        adj[s].add(new Edge(s,e,c));
    }
    private class Edge{
        private int begin;
        private int end;
        private int count;

        public Edge(int begin, int end, int count) {
            this.begin = begin;
            this.end = end;
            this.count = count;
        }
    }
    private class Vertex implements Comparable<Vertex> {
        private int did;
        private int dist;

        public Vertex(int did, int dist) {
            this.did = did;
            this.dist = dist;
        }

        @Override
        public int compareTo(Vertex o) {
            if (o.dist > this.dist) {
                return -1;
            }else{
                return 1;
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex vertex = (Vertex) o;
            return did == vertex.did;
        }

        @Override
        public int hashCode() {
            return Objects.hash(did);
        }
    }

    /**
     * @param s s 起点
     * @param t t 终点
     *        isInQueue 用于判断某一点是否处于队列中，
     *        preRoad 用于输出两点间最短路径
     *        vertices 记录最值
     */
    public void disktra(int s,int t) {
        boolean[] isInQueue = new boolean[v];
        int[] preRoad = new int[v];
        Vertex[] vertices = new Vertex[v];
        PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
        for (int i = 0;i < v;i++) {
            vertices[i] = new Vertex(i,Integer.MAX_VALUE);
        }
        vertices[s].dist = 0;
        isInQueue[s] = true;
        priorityQueue.add(vertices[s]);
        while (!priorityQueue.isEmpty()) {
            Vertex tmp = priorityQueue.poll();
            if (tmp.did == t) {
                break;
            }
            for (int i = 0;i < adj[tmp.did].size();i++) {
                Edge edge = adj[tmp.did].get(i);
                Vertex next = vertices[edge.end];
                if (tmp.dist + edge.count < next.dist) {
                    next.dist = tmp.dist + edge.count;
                    preRoad[next.did] = tmp.did;
                    if (!isInQueue[next.did]) {
                        isInQueue[next.did] = true;
                        priorityQueue.add(next);
                        // 更新优先队列
                    }else{
                        priorityQueue.remove(next);
                        priorityQueue.add(next);
                    }
                }
            }
        }
        System.out.println("输出路径");
        System.out.print(s);
        printRoad(s,t,preRoad);
    }
    public void printRoad(int s,int t,int[] preRoad) {
        if (s == t) return;
        printRoad(s,preRoad[t],preRoad);
        System.out.print("-->" + t);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(2,3,1);
        graph.addEdge(3,4,1);
        graph.disktra(2,4);
    }
}

弗洛伊德算法

所有点到所有点 最短路径的算法。时间复杂度O（n^3）

ini复制代码package algorithm.shortest_road;

/**
 * @author EnochStar
 * @title: Floyd
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/19 19:06
 */
public class Floyd {
    private static int[][] distance;
    private static int[][] path;

    public static void floyd(int[][] graph) {
        distance = graph;
        int n = graph.length;
        path = new int[n][n];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                path[i][j] = j;
            }
        }
        // 中转点
        for (int i = 0;i < n;i++) {
            // 入度
            for (int j = 0;j < n;j++) {
                // 出度
                for (int k = 0;k < distance[j].length;k++) {
                    if (distance[j][i] != -1 && distance[i][k] != -1) {
                        int newDistance = distance[j][i] + distance[i][k];
                        if (newDistance < distance[j][k] || distance[j][k] == -1) {
                            distance[j][k] = newDistance;
                            path[j][k] = i;
                        }
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        char[] vertices = new char[]{'A', 'B', 'C', 'D'};
        int[][] graph = new int[][]{
                {0, 2, -1, 6}
                , {2, 0, 3, 2}
                , {-1, 3, 0, 2}
                , {6, 2, 2, 0}};
        floyd(graph);
        System.out.println("====distance====");
        for (int[] ints : distance) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
        System.out.println("====path====");
        for (int[] ints : path) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}

区别： Dijkstra 算法：每次从「未求出最短路径」的点中 取出 最短路径的点，并通过这个点为「中转站」刷新剩下「未求出最短路径」的距离。

Dijkstra 的算法在图中的效果像是：以起点为中心像是一个涟漪一样在水面上铺开。

Floyd 算法在图中的效果像是：一个一个多点的小涟漪，最后小涟漪铺满整个水面。

练习：
网络延迟时间 - 网络延迟时间 - 力扣（LeetCode） (leetcode-cn.com)

位图

思考：如何实现网页爬虫的url去重问题？

对于这个问题，要实现的功能是，添加一个url以及查询一个url，同时要求复杂度尽可能的高。显然，散列表是率先想到的方法，无论添加还是查找都只需要O（1）的时间复杂度，然而对于查找操作，由于是url所以这会涉及到字符串匹配的问题，同时如果爬取的url很多，那么也会消耗极大的内存空间。对于后者，可以采用分治的思路，即利用哈希算法，多台机器存储url。

那么，如何在提高时间复杂度的前提下，尽可能使内存占用率小呢？

可以使用位图来解决这个方法，假设有一千万个数，每个数的范围是1到1亿之间，我们需要判断一个数是否存在于这个集合中，不存在则添加。

java复制代码package algorithm.bit;

/**
 * @author EnochStar
 * @title: BitMap
 * @projectName basic_use
 * @description: nbits表示数据的最大范围
 * @date 2021/11/22 10:53
 */
public class BitMap {
    private char[] bits;
    private int nbits;

    public BitMap(int nbits) {
        this.nbits = nbits;
        bits = new char[nbits / 8 + 1];
    }

    public void set(int num) {
        if (num > nbits) return;
        int byteIdx = num / 8;
        int bitIdx = num % 8;
        bits[byteIdx] |= (1 << bitIdx);
    }

    public boolean get(int num) {
        int byteIdx = num / 8;
        int bitIdx = num % 8;
        return (bits[byteIdx] & (1 << bitIdx)) != 0;
    }
}

如果是动态的添加数据，即未知数据量的大小，以及数据所在的范围呢？

那这时候就需要进行动态扩容，可以先初始化四个long类型数组，第一个数组不放数据，剩下的三个数组的操作和位图一致，假设添加的数字为67540，则对应的数组下标应该为1055，对应的位应该为20，此时就需要对原数组扩容，下标为4的数组和下标为0的数组一样仍然不存储数据，此时下标为4的值转化为2进制
110000011100，其中前32位表示后续连续存储数据的数组，后32位表示跨越的数组，此时数组中下标为5的位置就存储67540的值。当判断数据是否存在时，则可以通过解析存储跨度信息的下标，即从0开始解析，然后依次判断。

此处参考：漫画：Bitmap算法 整合版 (qq.com)

当允许存在精确误差时，可以使用布隆过滤器，布隆过滤器是基于位图实现的，其目的是在丢失部分精确性的前提下进一步节省内存空间。实现原理是，对于一个数字，通过多个哈希算法求得多个下标，并设置为1，当判断是否存在时，同样也是用多个哈希算法求得对应下标，判断是否为1.其产生误差的原因如图：

因此在允许误差的情况下，可以使用布隆过滤器对网页爬虫的url去重。

思考

假设我们有1亿个整数，数据范围是从1到10亿，如何快速并且省内存地给这1亿个数据从小到大排序？

答：可以使用位图，将数字添加到位图中，依次读取值为1的下标。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有