常用算法归类

1. 二分查找（非递归）
2. 分治算法
3. 动态规划
4. KMP算法
5. 贪心算法
6. 回溯算法

以下只给出思路与关键方法，算法的源代码放在了git中，需要的自取

leidl97/algorithm-src

二分查找（非递归）

非递归的话肯定使用while了

难点

注意边界值条件，只有当左边的值大于右边才跳出循环

当目标值小于mid时，应该让right = mid + 1，需要加1，

同样的，相反情况也需要 -1 。

方法实现

//非递归实现
private static void search3(int[] a, int act) {
    int left = 0;
    int right = a.length-1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[mid] == act) {
            //找到该值
            System.out.println("找到该值");
            return;
        }
        if (act < a[mid]) {
            right = mid - 1;
            continue;
        }
        left = mid + 1;
    }
    System.out.println("没有找到该值");
}

分治算法

分而治之，将一个大问题分解成小问题去解决，再将子问题的解合并就是原问题的解。

经典的应用有：归并排序，快速排序，傅里叶变换（快速傅里叶变换），汉诺塔等

以汉诺塔（hannoiTower）为例

解题思路

如果只有1个盘，直接从A移到C

如果两个盘

①那么将最上面部分看作一个整体，先移动到辅助柱子B（递归）

②在将最后一个盘移动到C

③最后将B上的盘移动到C，此时A作为辅助柱子（递归）

代码实现

/**
     * 汉诺塔移动
     * @param n 几个盘子
     * @param a 源柱
     * @param b 辅助柱
     * @param c 目标柱
     */
public void merge(int n, char a, char b, char c) {
    if (n == 1) {
        System.out.println("第1个盘从"+a+"移到"+c);
        return;
    }
    if (n >= 2) {
        merge(n-1,a,c,b);
        System.out.println("第"+n+"个盘从"+a+"移到"+c);
        merge(n-1,b,a,c);
    }
}

动态规划

比如经典的01背包问题

（Dynamic Programing）可以看b站的一个视频，讲的很清楚

【动态规划】背包问题_哔哩哔哩_bilibiliwww.bilibili.com

介绍

就是分步缓存，减少重复计算的过程，增加运行效率，找到最优解

继续回到背包问题，又分为01背包和完全背包，01背包表示放入的东西不能够重复，完全可以放入多件

涉及到两个维度的dp问题，直接考虑构建二维数组解决（大小+1，第0行0列值都是不计入）

根据重量及价格构建一个5 x 4的表格

思路

1、第一行列均置为0

当背包容量为0的时候不能让任何有价值的东西，当这个价值为0的时候，装多少重量价值都为0

都是0的话，为什么需要创建有0的数组，有什么意义吗？

为了后面的计算时候使用

2、for循环遍历，从第一行，第一列开始，逐渐填充该数组

二维数组的每个格子都有两种选择，一种是装入物品，另一种则不装入

①如果装不下，只能选择不填入物品，思路

1、第一行列均置为0，因为当背包容量为0的时候不能让任何有价值的东西，当这个价值为0的时候，装多少重量都为0

都是0的话，为什么需要创建有0的数组，有什么意义吗？

为了后面的计算时候使用

2、for循环遍历，从第一行，第一列开始，逐渐填充该数组

二维数组的每个格子都有两种选择，或者填入物品，或者不填入物品

首先进行判断如果装不下，此时只能选择不填入物品

①当我们选择填入该物品的使用，那么此时这个格子的价值为当前商品的价值+去除这个重量后的价值【1】

解释【1】：先将背包总容量-当前物品的重量获得一个值。然后取前一个物品此重量下的最大价值

②如果不选择该物品，此时物品的价值和前一个物品价值相同

最后取他们两个中较大的那个

代码思路

定义重量数组w[]，价格数组v[]，二维记录数组result[] [] 行表示重量，列表示价格

//价值
int[] v = {1500,3000,2000};
//重量
int[] w = {1,4,3};
//结果数组
int[][] result = new int[v.length + 1][4 + 1];

①result[0] [j] = 0， result[i] [0] = 0 表示第一行第一列为0

②不可以选择（重量超出）：result[i] [j] = result[i-1] [j]（上一行的值）

③可以选择：当前商品价值 + 背包容量除去当前物品重量的最大价值。

result[i][j] = Math.max(result[i-1][j], v[i-1] + result[i-1][j - w[i-1]]);

最大价值如何计算？

比如此例的最后一个格，值应为2000+1500=3500

max(result[3-1] [4] , v[2] + result[3-1] [4 - w[3-1]])

result[3-1] [4] = 同列上行的值也就是1500

result[3-1] [4 - w[3-1]] = result[2] [4 - 3] =

上行重量为4-3也就是result[2] [1]处的最大价值1500 + 当前物品的价值v[2]2000 = 3500

关键代码

for (int i = 1; i < result.length; i++) {
    for (int j = 1; j < result[0].length; j++) {
        //判断重量
        if (w[i-1] > j) {
            //大于给定重量，那么只能不选，采用上方的
            result[i][j] = result[i-1][j];
        } else {
            //在不选和选取较大值
            result[i][j] = Math.max(result[i-1][j], v[i-1] + result[i-1][j - w[i-1]]);
        }
    }
}

现在只是可以获得最大值，但是不知道具体方案，所以需要进行回溯

从二维数组的最后一个数字开始遍历，与上一行的值进行对比，如果相等说明该物品没有加入背包(行–)，

如果不相等说明该物品加入背包，此时行–，

判断上个物品有没有，重量得从总重量减去当前物品的重量，所以列 = 列 - 当前物品的重量

方法实现

int i = result.length-1;
int j = result[0].length-1;
while (i > 0 && j > 0) {
    if (result[i][j] != result[i-1][j]) {
        //不等于上面的，那么该物品装入背包
        System.out.println(i+"号物品装入背包");
        j -= w[i-1];
        i--;
    } else {
        i--;
    }
}

结果如下

KMP算法

名字的由来

由三个人研究出的字符串查找算法分别是Knuth-Morris-Pratt，简称为KMP算法

干什么的

匹配字符串用的，效率相较于传统的暴力破解效率很高

暴力破解：指一位一位的进行对比，不匹配向后移一位，直到匹配成功，或者匹配失败

总之KMP算法不死板,不像暴力破解总是不匹配向后移动一位，然后一位一位比。

而是利用自身的算法来实现移动多位，来减少匹配次数，提高运行效率

重点

找前缀和后缀的共同部分的最大长度

什么是前缀，什么是后缀

前缀就是含头不含尾，后缀就是含尾不含头

以APPLE为例

前缀分别为：A | AP | APP | APPL

后缀分别为：E | LE | PLE | PPLE

需要找出模式串的部分匹配值，存入next表中

什么是部分匹配值

一个串的前缀后缀相等的最大长度就是部分匹配值

如图所示

A没有前后缀就是 0

AB前缀为A，后缀为B，没有相同部分为0

ABC前缀为A,AB后缀为 C,BC，没有相同部分为0

同理0的就不举例了

ABCDA前缀 A, AB,ABC,ABCD,后缀A,DA,CDA,BCDA,有公共的A，且长度为1，所以值为1

移动位数 = 已匹配的字符数（当前目标串下标） - next表的匹配值（不匹配的表中下标对应的值）

难点

1、如何创建部分匹配表，容易理解，怎么去实现写出来

数组第一个为0，如果第二个数与第一个字符相等，则匹配值+1，并且next[第二个数的下标] = 匹配值。此时 AAA 得到的数组为【0，1，2】

如果不相等该怎么办

第一想法是让匹配值归0，重新遍历。

但KMP算法精髓在于 匹配值 = next[当前匹配值下标 - 1] 而不是直接为0

while (j > 0 && str.charAt(i) != str.charAt(j)) {
//     j = result[j - 1];
       j = 0;
}

举例“AACDAAA”

如果是j=0的方式，得到的结果为[0, 1, 0, 0, 1, 2, 1]，这个值是错的

如果是j = result[j - 1]的方式，得到的结果为[0, 1, 0, 0, 1, 2, 2]

2、如何将目标串与模式串匹配

过程思路

假设目标串为 “BBC ABCDAB ABCDABCDABDE”，模式串为“ABCDABD”

该模式串的匹配表为next = [0, 0, 0, 0, 1, 2, 0]

如果模式串指针位为0，那么当目标串第一位始终不匹配的时候，目标串的指针始终向后移动1位

第一次开始匹配的位置如下：

D与空格不符，那么模式串的指针由空格位 - next[模式串下标-1]

也就是next[6-1] = 移动2位，位置如下

C与空格不匹配，向后移动next[2-1] = 0位，这里程序做了处理，如果移动为0位，那么直接向后挪一位进行比较，直到下一次匹配到的位置

发现D!=C，移动next[6-1] = 2位，此时逐个比较，发现完全匹配，返回第一次位置的下标

关键代码

public static int cal(String str1, String str2) {
        //创建目标串指针
        int i = 0;
        //创建模式串指针
        int j = 0;
        //获得匹配表
        int[] next = next(str2);
        while (i < str1.length()) {
            if (j == str2.length()) {
//                return i - str2.length();
                //换为下面的更有效率
                return i - j;
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else if (j == 0){
                //如果没有匹配成功，那么直接将i向后移动
                i++;
            } else {
                //否则表示匹配过程中失败，将i退回到相应的位置
                //利用先前的公式
                i = i - next[j-1];
                j = 0;
            }
        }
        return -1;
    }

    //生成next数组
    public static int[] next(String str) {
        int[] result = new int[str.length()];
        result[0] = 0;
        for (int i = 1, j = 0; i < str.length(); i++) {
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = result[j - 1];
                j = 0;
            }
            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            result[i] = j;
        }
        return result;
    }

贪心算法

什么是贪心算法

对问题求解时，每一步都选择用最好或最优的方式，从而使结果达到最好的一种算法

但得到的结果不一定是最优解，是相对接近最优解的结果。求最合适的解，但不一定是最优解

举个场景说明

如图所示，有5个广播台，得出一种方案使得，选择最少的广播台来覆盖所有的地区

难点

1、怎么遍历才能获得覆盖地区最多的广播台

每次都找覆盖最大的一个广播台，找到之后从总集合重去除，在按这种方式继续，直到总广播台被找完，这也是贪心的思想，总是去找相对大或者相对好的。为什么是相对？比如此例中，有3个广播台都是覆盖3个城市，那么选到的不一定是最优的，但总比覆盖2个城市的优先级要高

2、什么情况下需要覆盖最大广播台

当这个广播台还有未覆盖地区的时候（size>0）并且 （ 当定义的max没有初始值的时候 或者 当前遍历的广播台所覆盖的地区数量大于之前的广播台数量 ）

此时当前广播台为最优选择，这也是贪心算法的思想

关键代码

 while (allArea.size()>0) {
            String max = null;
            for (Map.Entry<String,String> entry : radio.entrySet()) {
                String k = entry.getKey();
                String v = entry.getValue();
                String[] ss = v.split("，");
                for (String str : ss) {
                    temp.add(str);
                }
                temp.retainAll(allArea);
                if (temp.size() > 0 && (max == null || temp.size() > radio.get(max).split("，").length)) {
                    max = k;
                }
                temp.clear();
            }
            //将方案添加到结果集中
            result.add(max);
            for (String str : radio.get(max).split("，")) {
                allArea.remove(str);
            }
//            radio.remove(max);

        }

回溯算法

场景举例

马踏棋盘是一个经典的回溯问题

小游戏地址：马踏飞棋

问题描述

如果给定一个m x n的棋盘，在给定一个马儿棋子的初始位置，按照马走日的规则，如何可以在每个方格只进入一次的情况下，走完整个棋盘。

当然，存在棋盘或者有些起始点不能使马儿走完整个棋盘的情况。

问题解析

马儿在任意一个点，总是会有可走的选择，如果可以走的话，选取一个点走，走不通的话就返回上一步，重新考虑下一个点进行尝试

如何获取当前点的下一个可选点？

根据马走日原则，如果满足原始点{1,2}的距离，并且返回当前可使用的点

//i，j表示马的位置
List<Luozi> next(int[][] act, int i, int j) {
    int size = act.length;
    List<Luozi> ls = new ArrayList<>();
    //四象限
    if (i+1 < size && j+2 < size && act[i+1][j+2] ==0) {
        ls.add(new Luozi(i+1,j+2));
    }
    if (i+2 < size && j+1 < size && act[i+2][j+1] ==0) {
        ls.add(new Luozi(i+2,j+1));
    }
    //三象限
    if (i+1 < size && j-2 >= 0 && act[i+1][j-2] ==0) {
        ls.add(new Luozi(i+1,j-2));
    }
    if (i+2 < size && j-1 >= 0 && act[i+2][j-1] ==0) {
        ls.add(new Luozi(i+2,j-1));
    }
    //一象限
    if (i-1 >= 0 && j-2 >= 0 && act[i-1][j-2] ==0) {
        ls.add(new Luozi(i-1,j-2));
    }
    if (i-2 >= 0 && j-1 >= 0 && act[i-2][j-1] ==0) {
        ls.add(new Luozi(i-2,j-1));
    }
    //二象限
    if (i-1 >= 0 && j+2 < size && act[i-1][j+2] ==0) {
        ls.add(new Luozi(i-1,j+2));
    }
    if (i-2 >= 0 && j+1 < size && act[i-2][j+1] ==0) {
        ls.add(new Luozi(i-2,j+1));
    }
    return ls;
}

有规则之后，直接使用该规则进行编写代码

1、首先将马儿当前的坐标点置为step（当前步数）

2、根据刚才的next方法来获取可选的坐标点

3、遍历所有的坐标点，递归调用当前方法继续执行12操作

4、如果遍历完之后没有达到预定步数，那么将当前坐标点置为0（未使用）进行回溯

5、如果步数达到预定步数或者程序执行完（for循环是可以执行完的，是有出口的）程序结束。（因为不一定只有一种方案，全部遍历完需要花很长的时间）

void DFS(int[][] act,int i, int j,int step) {
    act[i][j] = step;
    if (step == act.length * act.length) {
        //如果达到预定步数，则打印
        print(act);
    }
    //得到可以落子的坐标集合
    List<Luozi> ls = next(act, i, j);
    //贪心思想，每次都尽量选取返回数量最小的，以减少回溯的次数
    //先注释
    //sort(ls,act);
    for (Luozi l : ls) {
        //递归调用可用坐标
        DFS(act,l.i,l.j,step+1);
    }
    //如果没有达到预定步数，将此点置为0，进行回溯
    if (step < act.length * act.length) {
        act[i][j] = 0;
    }
}

存在的问题

该算法不足的点在于由于每个人在编写规则顺序不同，返回的list不同，走的路径也会不同。导致执行的时间往往会很长。上述算法通过计数器可得到，在6 x 6 棋盘，起始点{1,3}的情况下，找到第一种方案，需要执行该方法11195506次！如果我使用8 x 8的棋盘，根本走不完。

那么如果提高效率？

贪心思想

如图，在6个点中，选哪一个点更加合适，这个就是提高算法效率的点。之前算法没有去定义，只按照了规则中的判断顺序得到

可以直接将这6个点的下一个可走的点得到，看这6个点哪一个的下一个可选点最少，哪一个点就是相对最优选。这样选择“出口”最少的点进行搜索，是一种局部调优的做法，回溯的次数也会减少。测试可知，用贪心思想执行方法的次数变为了36次！8 x 8的也仅用64次！

回溯的次数与找到点有什么关系？

选择少的点遍历，少的点会越来越少，成功的机率会越来越大？

其实我想它这种遍历方式，应该是从外圈到内圈的遍历方式，是一种循序的遍历过程，回溯过程缺失变少，试想如果任由自己跳，到最后阶段往往会不断进行回溯来调整之前的位置，也许这就是回溯少带来的优势。

//进行递增排序，贪心思想
void sort(List<Luozi> ls,int[][] act) {
    ls.sort(new Comparator<Luozi>() {
        @Override
        public int compare(Luozi o1, Luozi o2) {
            int a = next(act, o1.i, o1.j).size();
            int b = next(act, o2.i, o2.j).size();
            if (a < b) {
                return -1;
            } else if(a == b) {
                return 0;
            } else {
                return 1;
            }
        }
    });
}

最后只需要将之前得到的ls进行排序即可

List<Luozi> ls = next(act, i, j);
//贪心思想，每次都尽量选取返回数量最小的，以减少回溯的次数
//打开注释
sort(ls,act);
for (Luozi l : ls) {
    //递归调用可用坐标
    DFS(act,l.i,l.j,step+1);
}