算法沉淀_牛客博客

深度优先搜索算法（DFS）

1、简介

DFS，全称为Depth-First-Search。

2、例子：进行1～n的全排列

如n=3，全排列为123，132，213，231，312，321，共3！种。

3、算法模板

int check(参数){
    if(满足条件){
        return 1;
    }
    return 0;
}
void dfs(int step){
    判断边界{
        相应操作；
    }
    尝试每一种可能{
        满足check条件；
        标记；
        继续下一步dfs(step + 1);
        恢复初始状态(回溯时用到)
    }
}

4、java实现
import java.util.Scanner;

public class Main {
static int n;
static int[] arr;//用来记录已经在排列中的数字
static int[] brr;//标记

static void dfs(int step) {
    if (step == n) {//边界输出
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    } else if (step < n) {
        for (int i = 1; i <= n; i++) {//每一次循环都将i作为第一个数进行排列
            if (brr[i] == 0) {//判断是否重复，相当于check方法是否满足条件
                brr[i] = 1;//标记已经使用
                arr[step] = i;
                dfs(step + 1);//进行下一步
                brr[i] = 0;//清空标记
            }
        }
    } else return;
}
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    arr = new int[n + 1];
    brr = new int[n + 1];
    dfs(0);
}

}

manacher算法（马拉车算法）

1、例子
Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

输入描述:
输入一个字符串

输出描述:

返回有效密码串的最大长度

2、manacher算法优点
(1) 解决长度奇偶性带来的对称轴位置问题
aba ———> #a#b#a#
abba ———> #a#b#b#a#
(2) 解决重复访问的问题

char: # a # b # a #
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i : 0 1 2 3 4 5 6

char: # a # b # b # a #
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i : 0 1 2 3 4 5 6 7 8

通过观察可以发现，RL[i]-1的值，正是在原本那个没有插入过分隔符的串中，以位置i为对称轴的最长回文串的长度。那么只要我们求出了RL数组，就能得到最长回文子串的长度。

于是问题变成了，怎样高效地求的RL数组。基本思路是利用回文串的对称性，扩展回文串。

3、Manacher算法核心
（1）概念：
ManacherString：经过Manacher预处理的字符串，以下的概念都是基于ManasherString产生的。

回文半径和回文直径：因为处理后回文字符串的长度一定是奇数，所以回文半径是包括回文中心在内的回文子串的一半的长度，回文直径则是回文半径的2倍减1。比如对于字符串 "aba"，在字符 'b' 处的回文半径就是2，回文直径就是3。
最右回文边界R：在遍历字符串时，每个字符遍历出的最长回文子串都会有个右边界，而R则是所有已知右边界中最靠右的位置，也就是说R的值是只增不减的。
回文中心C：取得当前R的第一次更新时的回文中心。由此可见R和C时伴生的。
半径数组：这个数组记录了原字符串中每一个字符对应的最长回文半径。

（2）流程：

步骤1：预处理原字符串

先对原字符串进行预处理，预处理后得到一个新的字符串，这里我们称为S，为了更直观明了的让大家理解Manacher的流程操作，我们在下文的S中不显示特殊字符(这样并不影响结果)。

步骤2：R和C的初始值为-1，创建半径数组pArr

这里有点与概念相差的小偏差，就是R实际是最右边界位置的右一位。

步骤3：开始从下标 i = 0去遍历字符串S

1）分支1：i > R ，也就是i在R外，此时没有什么花里胡哨的方法，直接暴力匹配，此时记得看看C和R要不要更新。

2）分支2：i <= R，也就是i在R内，此时分三种情况，在讨论这三个情况前，我们先构建一个模型
图片说明

L是当前R关于C的对称点，i'是i关于C的对称点，可知 i' = 2*C - i，并且我们会发现，i'的回文区域是我们已经求过的，从这里我们就可以开始判断是不是可以进行加速处理了

情况1：i'的回文区域在L-R的内部，此时i的回文直径与 i' 相同，我们可以直接得到i的回文半径，下面给出证明
图片说明

红线部分是 i' 的回文区域，因为整个L-R就是一个回文串，回文中心是C，所以i形成的回文区域和i'形成的回文区域是关于C对称的。

情况2：i'的回文区域左边界超过了L，此时i的回文半径则是i到R,下面给出证明
图片说明

首先我们设L点关于i'对称的点为L'，R点关于i点对称的点为R'，L的前一个字符为x，L’的后一个字符为y，k和z同理，此时我们知道L - L'是i'回文区域内的一段回文串，故可知R’ - R也是回文串，因为L - R是一个大回文串。所以我们得到了一系列关系，x = y，y = k，x != z，所以 k != z。这样就可以验证出i点的回文半径是i - R。

情况3：i' 的回文区域左边界恰好和L重合，此时i的回文半径最少是i到R，回文区域从R继续向外部匹配，下面给出证明
图片说明

因为 i' 的回文左边界和L重合，所以已知的i的回文半径就和i'的一样了，我们设i的回文区域右边界的下一个字符是y，i的回文区域左边界的上一个字符是x，现在我们只需要从x和y的位置开始暴力匹配，看是否能把i的回文区域扩大即可。

总结一下，Manacher算法的具体流程就是先匹配 -> 通过判断i与R的关系进行不同的分支操作 -> 继续遍历直到遍历完整个字符串。

时间复杂度：
我们可以计算出时间复杂度为何是线性的，分支一的情况下时间时间复杂度是O(n)，分支二的前两种情况都是O(1)，分支二的第三种情况，我们可能会出现O(1)——无法从R继续向后匹配，也可能出现O(n)——可以从R继续匹配，即使可以继续匹配，R的值也会增大，这样会影响到后续的遍历匹配复杂度，所以综合起来整个算法的时间复杂度就是线性的，也就是O(n)。

4、java实现

public class Manacher {
    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
     }
    public static int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length];
        int C = -1;
        int R = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != charArr.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while (i + pArr[i]  -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }
    public static void main(String[] args) {
        String str1 = "abc123321cba";
        System.out.println(maxLcpsLength(str1));
    }
}

0-1背包问题（动态规划）

1、问题描述
给定n个重量为w1、w2、...、wn，价值为v1、v2、...、vn的物品和容量为C的背包，求这个物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的总价值最大。

分析：我们用F(n，C)表示前n个物体放入容量为C的背包，得到的最大价值。

2、java实现

public class KnapSack01 {
    /**
     * 解决背包问题的递归函数
     *
     * @param w        物品的重量数组
     * @param v        物品的价值数组
     * @param index    当前待选择的物品索引
     * @param capacity 当前背包有效容量
     * @return 最大价值
     */
    private static int solveKS(int[] w, int[] v, int index, int capacity) {
        //基准条件：如果索引无效或者容量不足，直接返回当前价值0
        if (index < 0 || capacity <= 0)
            return 0;
        //不放第index个物品所得价值
        int res = solveKS(w, v, index - 1, capacity);
        //放第index个物品所得价值（前提是：第index个物品可以放得下）
        if (w[index] <= capacity) {
            res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
        }
        return res;
    }
    public static int knapSack(int[] w, int[] v, int C) {
        int size = w.length;
        return solveKS(w, v, size - 1, C);
    }
    public static void main(String[] args){
        int[] w = {2,1,3,2};
        int[] v = {12,10,20,15};
        System.out.println(knapSack(w,v,5));
    }
}

3、拓展（分组背包、有依赖的背包）
引论：0-1背包=>分组背包=>有依赖的背包，是个递进的过程。

匈牙利算法（最大匹配问题）

1、问题描述
题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。

输出:

输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数

分析：由于要使得数对和为素数，那么这两个数字就一定为一个奇数和偶数(因为除了2偶数不可能为素数，而题目给出的范围一定是大于2的)，那么就能自然而然的想到将所有的数先依照奇偶性分为两组。我们要尽可能的在满足匹配要求的前提下多给两边连线，这就是一个二分图的最大匹配问题。
基本思路：
- 对奇数堆的数字依次遍历，让每个数字去尝试匹配偶数堆的数字；
- 若和值为素数且那个偶数没有配对，则将他俩配对；
- 若和值为素数但是那个偶数已经名花有主，则再让那个偶数的配对奇数对所有偶数进行遍历，找到下一个接盘者，好把位子腾出来给那个奇数。

2、java实现

public class Main {
    public static List oddList=new ArrayList();//奇数组
    public static List evenList=new ArrayList();//偶数组
    public static Set flagSet=new HashSet();//标记数组
    public static Map hashMap=new HashMap();//存储匹配对数
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            oddList.clear();
            evenList.clear();
            hashMap.clear();
            int num=sc.nextInt();
            for(int i=0;i<num;i++){
                int temp=sc.nextInt();
                if(temp%2==0){
                    evenList.add(temp);
                }else{
                    oddList.add(temp);
                }
            }
            for(int i=0;i<oddList.size();i++){
                flagSet.clear();
                find(oddList.get(i));
            }
            System.out.println(hashMap.size());
        }
    }
    public static boolean find(int left){
        for(int i=0;i<evenList.size();i++){
            if(judge(evenList.get(i)+left)&&!flagSet.contains(evenList.get(i))){
                flagSet.add(evenList.get(i));
                if(!hashMap.containsKey(evenList.get(i))||find(hashMap.get(evenList.get(i)))){
                    hashMap.put(evenList.get(i),left);
                    return true;
                }
            }
        }
        return false;
    }
    //判断是否为素数
    public static boolean judge(int num){
        for(int i=2;i<=num/2;i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }
}