左神算法——并查集，KMP，Manacher

并查集，KMP，Manacher——左神算法

并查集

代码实现

并查集是把原有的链表结构重新优化，按照图的上一个node来进行保存

•   import java.util.HashMap;
    import java.util.List;
    import java.util.Stack;
    
    /**
    
     * @Author laimouren
     * @Date 2021/12/7 19:35
       */
       public class UnionFind {
       //样本进来会包一层，叫做元素
       public static class Element<V>{
           public V value;
           public Element(V value){
               this.value = value;
           }
       }
       public static class UnionFindSet<V>{
           //值和element的对应关系
           public HashMap<V,Element<V>> elementMap;
           //key 某个元素 value 该元素的父亲
           public HashMap<Element<V>,Element<V>> fatherMap;
           //key 某个集合的代表元素，value 该集合的大小
           public HashMap<Element<V>,Integer> sizeMap;
           public UnionFindSet(List<V> list){
               elementMap = new HashMap<>();
               fatherMap = new HashMap<>();
               sizeMap = new HashMap<>();
               for (V value : list) {
                   Element<V> element = new Element<V>(value);
                   elementMap.put(value,element);
                   fatherMap.put(element,element);
                   sizeMap.put(element,1);
               }
           }
    //给定一个ele，往上一直找，将代表元素返回
    //调用该函数越频繁，查找的时间复杂度就为O（1）
    private Element<V> findHead(Element<V> element){
        Stack<Element<V>> path = new Stack<>();
        while (element != fatherMap.get(element)){
            path.push(element);
            element = fatherMap.get(element);
        }
        //将遍历的整条链的父都设置为找到的代表元素
        //即将其扁平化(向上找优化)
        //这一步即是对并查集的时间复杂度进行一个优化，类似于一个蒲公英结构，大量的点连接到中间点
        while (!path.isEmpty()){
            fatherMap.put(path.pop(),element);
        }
        return element;
    }
    
    public boolean isSameSet(V a,V b){
        if(elementMap.containsKey(a) && elementMap.containsKey(b)){
            return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
        }
        return false;
    }
    
    public void union(V a,V b){
        if(elementMap.containsKey(a) && elementMap.containsKey(b)){
            Element<V> aF = findHead(elementMap.get(a));
            Element<V> bF = findHead(elementMap.get(b));
            if(aF != bF){
                Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
                Element<V> small = big == aF ? bF : aF;
                fatherMap.put(small,big);
                sizeMap.put(big,sizeMap.get(aF) + sizeMap.get(bF));
                sizeMap.remove(small);
            }
        }
    }
    }
    }
    
    
      #### 趣味补充：
  
  * <img src="https://gitee.com/cat-hair-hutao/images/raw/master/Typora/20240725185840.png" alt="image-20240725185839223" style="zoom:25%;" />
  
      N= 10^80，这个数逼近宇宙的原子数量，图片中央公式的返回值不超过6
  
  ### 使用并查集去建立并行算法（使用多核cpu运行算法），
  
  例题leetcode 200 岛屿数量
  
  1，按照单核cpu的解法求出各个分片的结果
  
  2，记录边界点上被感染的点是最开始被哪个点感染的
  
  3，使用并查集在合并的时候进行操作
  
  ![image-20240725191849517](https://gitee.com/cat-hair-hutao/images/raw/master/Typora/20240725191850.png)
  
  
  
  ## KMP
  
  ### 算法背景：
  
  判断一个str1是不是str2的子串
  
  解决如下问题
  
  ![image-20240725194222536](https://gitee.com/cat-hair-hutao/images/raw/master/Typora/20240725194223.png)
  
  
  
  ### 概念引入
  
  #### 最长相等前后缀
  
  在继续进行之前需要首先了解一个概念： 最长前后缀相等长度。使用过程：有一个字符串，使用头尾双指针，依次向中间靠拢，保存可以让头尾指针走过的地方相等的最长长度，排除字符串本身的长度。字符串长度为本身长度没有意义，前后指针走过的距离长度形成的字符串不是回文的那种形式，对比遍历字符串的方向是一致的。
  
  ![image-20240725195104582](https://gitee.com/cat-hair-hutao/images/raw/master/Typora/20240725195105.png)
  
  #### next arr
  
  ##### 建立
  
  str2是两个字符串中短的那个，这个步骤中需要求出的东西是next arr，这个数组每个位置的含义是，该位置之前的字符串最长前后缀相等长度，类似于迭代器中的end（），并不是说这个位置为null，而是不采用
  
  注意：i位置上的数字代表的是之前的字符串上的最长前后缀
  
  ![image-20240725200337865](https://gitee.com/cat-hair-hutao/images/raw/master/Typora/20240725200339.png)
  
  ##### 使用方法
  
  next arr的具体使用方法，在str1中查找str2，知道s位置，才找到一个不同的char，这个时候str2中对比的指针需要挪到当前段最长前缀的下一个索引位置，即箭头所指位置，str1中s位置保持不变，继续比对，相当于从str1中中间位置被圈出来的a开始匹配
  
  ![image-20240726154437319](https://gitee.com/cat-hair-hutao/images/raw/master/Typora/20240726154438.png)
  
  ##### 证明
  
  证明被跳过的最长前缀中的任何一点都不可能匹配出一个完整是str2出来。点“j”是匹配的新的起始点。在i到j之间任意一点开始往后都不可能匹配出str2。举例：任选点k，从k到x匹配上，因为原来str2是匹配到y为止才不一致，所以在对于str1，在X之前可以匹配上，这个时候最长前后缀长度是确定的，就是目前所给出的，，如果从k到x可以匹配上，就说明在这段内的前后缀长找到个更长的，这是不可能的，因此推断出这段不可能匹配出来。 
  
  ![image-20240726154358837](https://gitee.com/cat-hair-hutao/images/raw/master/Typora/20240726154400.png)
  
  ##### 求解
  
  next arr的0和1索引位置都是人为规定的，-1和0，-1是代表不能再继续条状，0是因为最长前后缀不能等于本身的长度，在这之后前后缀索引计算都可以使用之前计算的长度，步骤如下：
  
  当前索引来到 i 位置，i-1位置需要加入计算，使用i-1位置上的最长前后缀点的位置，因为数组0是起始索引，所以判断str2【next【i-1】】 == str2【i-1】，true就使用i-1位置上上的值并加1，false则需要在next【i-1】的结果为索引，返回执行以上过程，直到遇到边界条件
  
  
  
  ```java
  int i = 2;
        //拿cn字符和i-1的字符比
   int cn = 0; 
  while(i < ms.length){
  if(ms[i - 1] == ms[cn]) {
      //next[i] = cn + 1;
      //i++;
      //cn++;此时cn值是next[i-1]的值，这个i是更新后的i
      next[i++] = ++cn;
  }
  //当前跳到cn位置的字符，和i-1位置的字符配不上
  //cn得往前跳，即它的k值
  else if(cn > 0) {
      cn = next[cn];
  }
  //cn <= 0，没办法往前跳了
  //此时next[i]为0
  else {
      next[i++] = 0;
  }
  }
  

时间复杂度

同样的道理，根据最后kmp算法整体的时间复杂度的证明，求得next arr的时间复杂度是线性的，时间复杂度为O（N)。

代码实现

/**

 * @Author laimouren
 * @Date 2021/12/7 21:41
   */
   public class KMP {
   //N >= M
   public static int getIndexOf(String s, String m){
       if(s == null || m == null || m.length() < 1 || s.length() < m.length()){
           return -1;
       }
       char [] str1 = s.toCharArray();
       char [] str2 = m.toCharArray();
       int i1 = 0;
       int i2 = 0;
       //O(M)
       int [] next = getNextArray(str2);
       //O(N)
       while(i1 < str1.length && i2 < next.length){
           //匹配则str1和str2都加一
           if(str1[i1] == str2[i2]){
               i1++;
               i2++;
           }
           //str2当前位置为0，等同与i2 == 0
           else if(next[i2] == -1){
               i1++;
           }
           //此时str1和str2不匹配，通过nextArray往前跳，得到i2应该在的下一个位置
           else {
               i2 = next[i2];
           }
       }
       //i2越界则匹配成功，结果为i1-i2; 否则i1越界了，此时匹配失败，返回-1
       return ((i2 == str2.length) ? (i1 - i2) : -1);
   }
   /**
    * 获取next数组
      */
      public static int [] getNextArray(char [] ms){
      //人为规定第一个为-1
      if(ms.length == 1) {
          return new int[]{-1};
      }
      int [] next = new int[ms.length];
      next[0] = -1;
      //人为规定第一个为0
      next[1] = 0;
      //next数组的位置
      int i = 2;
      //拿cn字符和i-1的字符比
      int cn = 0;
      while(i < ms.length){
if(ms[i - 1] == ms[cn]) {
    //next[i] = cn + 1;
    //i++;
    //cn++;此时cn值是next[i-1]的值，这个i是更新后的i
    next[i++] = ++cn;
}
//当前跳到cn位置的字符，和i-1位置的字符配不上
//cn得往前跳，即它的k值
else if(cn > 0) {
    cn = next[cn];
}
//cn <= 0，没办法往前跳了
//此时next[i]为0
else {
    next[i++] = 0;
}
}
return next;
}

时间复杂度

该过程的时间复杂度是线性的，O(n)

将while循环的调用和一些变量的变化幅度绑定在一起，这个循环一共存在在三个分支，每个分支都会让给定的参数变大，i1是N，i1-i2同样也是N，于是循环体内的总数据变化浮动是2N，因此可以证明该过程的时间复杂度是线性的

while(i1 < str1.length && i2 < next.length){
          //匹配则str1和str2都加一
          if(str1[i1] == str2[i2]){
              i1++;
              i2++;
          }
          //str2当前位置为0，等同与i2 == 0
          else if(next[i2] == -1){
              i1++;
          }
          //此时str1和str2不匹配，通过nextArray往前跳，得到i2应该在的下一个位置
          else {
              i2 = next[i2];
          }
      }

Manacher

背景：

求解字符串中最长回文子串问题

关键点

一个位置的最长回文半径，回文半径数组

目标问题的经典解法

常见求解这个问题，以某个点为中心向外扩充，然后去判断。但是会错过长度为偶数的回文串。

使用以下方法就可以求解，不跳过新加入的 # 标志字符，最后结果除以2就能得到原字符串的该长度的回文子串的长度

求解的思考

新加入的内容 # 对于是不是原字符串中出现过的字符没有要求

时间复杂度

O（N^2)

举一个极的例子，左右两边每一次都可以直接过，都访问到边界

索引为3的位置，左边到边界，右边到边界，在索引3这个循环内，遍历的字符串，所以时间复杂度是O（n^2)

正题

概念引入

回文半径，回文直径。这俩的概念非常直接

回文半径数组：在从左往右遍历的过程，将所生成的回文半径记录下来

之前所扩的所有位置中所达到的最右右边界： int R = -1;从左到右扩张的过程中，每次回文的右侧的右边界变大，R的值随之变动，所记录的值是该位置的索引。

取得更远边界的时候中心的位置索引：int C . C随R的变动而变动

求解过程

条件1，当查询的点不在R值范围内，使用该问题的经典解法进行暴力扩展，没有优化

条件2，查询的点在R范围内，这时候必然存在C<i<R，此时根据R和C找到该回文串的左侧左边界L，点 i 绕着 中心点 C 做一个对称点 j

在条件2 下可以接着细分

​ 条件2-1， 以点 j 为中心的回文彻底在LR范围内（j 的回文信息可以通过回文半径数组获得），i 的回文半径跟 j 是一样的

​ 条件2-2，以点 j 为中心的回文有一部超出了 LR范文，<L，这个时候对应的回文串的回文半径是 i 到 R。证明：但凡不一样一点，i 的回文串越过了R ，即代表 越过的内容肯定包含 j 越过 L 的部分，那么此时R就不成立，所以是这个结论。

和条件2-1一样，都是使用到了回文串左右对照这一特性

​ 条件2-3，以点 j 为中心的回文压线L，I R 这段区域是可以确定的，再往外就不确定，首先就第一种情况，是因为当 i 扩张，对应的 j 肯定也要扩张，在这里限制着，压线就没有 j 的限制，因此大小不确定，这个时候从R往外扩就行，相当于一个加速。

时间复杂度

O（N)

证明：

如上图所示：每一个点都会经历一个错的过程，所以错失可以估计的，即N

然后就成功扩充，在四个分支中，一旦出现扩充的行为，就会出现R增大的情况，而R最大的变化幅度同样是N

因此时间复杂度是O（N)

代码实现

public class Manacher {
    public static char[] manacherString(String s) {
        char[] charArr = s.toCharArray();
        char[] res = new char[s.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length; ++i) {
            res[i] = (i & 1) == 0 ? '#' : s.charAt(index++);
        }
        return res;
    }
public static int maxLengthOfPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }

    char[] str  = manacherString(s);
    //回文半径数组
    int[] pArr = new int[ str.length];
    // 整体最右回文右边界的下一个位置，最右的有效区是R-1位置，与讲解时不一样   L[...C...]R
    int R = -1;
    // 整体最右回文时的回文半径中心
    int C = -1;
    //扩出来的最大值
    int max = Integer.MIN_VALUE;

    //每个位置都求回文半径
    for (int i = 0; i <  str.length; ++i) {
        //不用验证也知道的i至少的回文区域，先给pArr[i],四种情况都对，可以验证
        //R <= i i在R外，至少不用验证的区域为1，对应情况1
        //R > i i在R内，至少不用验证的区域为为  i‘的位置对应的回文半径 和 R-i中 的最小值，对应 情况2 的1,2,3
        //i'的位置 = R - (R - C) * 2 + (R - i) = R - 2R + 2C + R - i = 2 * C - i
        pArr[i] = R > i ? Math.min(pArr[ 2 * C - i], R - i) : 1;

        //四种情况都往外扩，情况2的1 2 只会执行一次就会失败，这样写是为了省略代码，不需要if else判断多种情况
        while (i + pArr[i] <  str.length && i - pArr[i] > -1) {
            if (str[i + pArr[i]] == str[i - pArr[i]]) {
                pArr[i]++;
            }
            else {
                break;
            }
        }
        if (i + pArr[i] > R) {
            R = i + pArr[i];
            C = i;
        }
        max = Math.max(max, pArr[i]);
    }

    /*
     * 返回值s字符串的最大回文长度 等于改造的字符串的最大回文半径 - 1
     * eg.
     *    1221  ==> #1#2#2#1#   返回值为 5-1 = 4
     *    12321 ==> #1#2#3#2#1# 返回值为 6-1 = 5
     */
    return max - 1;
}

public static void main(String []args) {
    String s1 = "123";
    String s2 = "ab43534c1234321ab";

    System.out.println("s1: " + maxLengthOfPalindrome(s1));
    System.out.println("s2: " + maxLengthOfPalindrome(s2));
 }
}

滑动窗口

概念引入

双端队列：两端都可以插入和删除

过程

LR分别是滑动窗口的左右两端，R前进，则从尾部向双端队列插入数据，如果插入数据后不能维持单调性，弹出双端队列中的数据直到可以维持单调性，L前进，看双端队列的头部存放的索引是不是此次滑动窗口滑出的索引，如果是就从头部弹出该元素，不是不管。

当索引对应的值相同的时候，从尾部弹出已有的索引，插入新的索引

双端队列的单调性保持的是在L弹出的数据后下一个最大值

时间复杂度

O（N)：每个元素最多进出双端队列的可能性是1次，因此时间复杂度是O（N），单点平均时间复杂度O（1），可能会存在单次插入操作的时间复杂度峰值飙升，比如说要插入的索引指向的元素比双端队列的头部最大元素要大，这个时候需要全部弹出，就不是O（1），总的复杂度还是O（1），还是因为每个元素最多进出一次，这次出去了，下次窗口缩小弹出的时候就不需要操作。

处理示例

单调栈

处理问题

求一个数左边距离最近比自身大的，右边距离最近比自身大的

过程

维持一个栈结构从底到顶部的单调性，新加入的元素栈顶的元素如果比它小，弹出栈顶元素,

当一个数被弹出 的时候，此时的栈顶元素和要被压入的元素分别是它的左边最大和右边最大

出现相同元素的时候

将相同元素压缩在一个数据结构中，需要该结构内的数据全部弹出后，才能继续向栈中压入数据

建议放入链表，在C++中也可以使用linkedList，双向链表

过程证明

可以自行分析过程

时间复杂度

O（n）

每个数都只会插入一次栈

题目

定义：数组中累计和与最小值的乘积 ，假设称为指标A

问题，给定一个数组，返回子数组中，指标A的最大值

大流程

要求每一个数都是自己所在子数组的最小值，求出指标A最大的情况，最终问题的结果一定在这些结果中间

过程

每一个数左边比它小的不能扩展，右边比它小的不能扩展，这个区间就是这个数所在子数组中指标A最大的情况，

使用单调栈会很快，因为单调栈的删选过程是O（N)，在加上后来的结果结算是使用索引直接求和然后乘以这个数，所以时间复杂度得证