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

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

leidl97/algorithm-src

二分查找(非递归)

非递归的话肯定使用while了

难点

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

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

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

方法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//非递归实现
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作为辅助柱子(递归)

img

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 汉诺塔移动
* @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背包问题

img

(Dynamic Programing)可以看b站的一个视频,讲的很清楚

【动态规划】背包问题_哔哩哔哩_bilibiliwww.bilibili.com![图标](https://pic3.zhimg.com/v2-d68245a9d65efe6d38ffb7efdf8c18fe_180x120.jpg)

介绍

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

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

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

img

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

img

思路

1、第一行列均置为0

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

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

为了后面的计算时候使用

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

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

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

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

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

为了后面的计算时候使用

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

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

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

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

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

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

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

代码思路

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

1
2
3
4
5
6
//价值
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

关键代码

1
2
3
4
5
6
7
8
9
10
11
12
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]]);
}
}
}

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

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

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

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

方法实现

1
2
3
4
5
6
7
8
9
10
11
12
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--;
}
}

结果如下

img

KMP算法

名字的由来

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

干什么的

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

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

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

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

重点

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

什么是前缀,什么是后缀

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

以APPLE为例

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

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

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

什么是部分匹配值

img

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

如图所示

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

1
2
3
4
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位

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

img

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

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

img

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

img

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

img

关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
}

贪心算法

什么是贪心算法

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

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

举个场景说明

img

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

难点

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

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

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

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

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

关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 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}的距离,并且返回当前可使用的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//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循环是可以执行完的,是有出口的)程序结束。(因为不一定只有一种方案,全部遍历完需要花很长的时间)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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个点中,选哪一个点更加合适,这个就是提高算法效率的点。之前算法没有去定义,只按照了规则中的判断顺序得到

img

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

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

选择少的点遍历,少的点会越来越少,成功的机率会越来越大?

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//进行递增排序,贪心思想
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进行排序即可

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