10种常用算法
代码一道，源远流长，短短几句代码中，往往蕴含着完美的逻辑和精妙的算法！这正是我们程序员追求的东西。我们程序员就应该外修语言，内修算法，数据为根基，算天算地算自己~
1、二分法查找（非递归）
二分查找法是查找算法里面，经典又比较简单的一种。它适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再查找。
二分查找法的运行时间为对数时间O(㏒₂n)，即查找到需要的目标位置最多只需要㏒₂n 步。假设从[0, 99]的队列(100 个数，即 n=100)中寻到目标数 30，则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 26 < 100 < 27)。
因为比较简单，话不多说直接撸代码
现有一组有序集合：[1, 3, 8, 10, 11, 67, 100]。要求写出通过二分法（非递归）查找 67 的完整代码
Java代码实现：
/**
* @description:
* @date: 2021/11/22 22:13
*/
public class AlgorithmUtils {
public static void main(String[] args) {
int[] array = new int[]{1, 3, 8, 10, 11, 67, 100};
int target = 67;
System.out.println(AlgorithmUtils.binarySearch(array, target)); // 5
}
/**
* 非递归二分法查找
* @param array 待查找的数组(升序)
* @param target 目标值
* @return 目标值下标，找不到则返回-1
*/
public static int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (target == array[middle]) {
return middle;
} else if (target > array[middle]) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
}
JavaScript代码实现：
let array = new Array(1, 3, 8, 10, 11, 67, 100);
let target = 67;
console.log(binarySearch(array, target));
function binarySearch(array, target) {
if (Array.isArray(array)) {
let left = 0;
let right = array.length - 1;
while (left <= right) {
let middle = (left + right) / 2;
if (target === array[middle]) {
return middle;
} else if (target > array[middle]) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
} else {
return -1;
}
}
Python代码实现：
def binary_search(list, target):
left = 0
right = len(list) - 1
while left <= right:
middle = int((left + right) / 2)
if target == list[middle]:
return middle
elif target > list[middle]:
left = middle + 1
else:
right = middle - 1
return -1
if __name__ == '__main__':
number_list = [1, 3, 8, 10, 11, 67, 100]
target = 67
print(binary_search(number_list, target))
2、分治算法
2.1、分治算法基本介绍
分治法（Divide-and-Conquer）是一种很重要的算法。字面上的解释是'分而治之'，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…
另外一些经典的问题，也是通过分治算法解决，例如
- 二分搜索
- 大整数乘法
- 棋盘覆盖
- 合并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
分治算法的基本实现步骤（分治法在每一层递归上都有三个步骤）：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解
2.2、汉诺塔问题
分治算法经典问题：汉诺塔问题
汉诺塔的传说
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假如每秒钟一次，共需多长时间呢？移完这些金片需要 5845.54 亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了 5845.54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
OK先来在线体验下传说中的汉诺塔游戏：http://www.7k7k.com/swf/201271.htm
体验完后，我们来整理下移动盘子的思路（假设有A、B、C柱子）：
1、如果只有一个盘，直接可以A->C
2、如果盘子的数量 n >= 2，我就可以看做是两个盘子。。
- 最下边（最大）的盘
- 上面的盘
因此就可以走三部曲
- 先把最上面的盘A->B
- 把最下边的盘A->C
- 把B塔的所有盘从B->C
Java代码实现：
/**
* 汉诺塔问题解决
* @param discNum 盘子数量
* @param a A柱子
* @param b B柱子
* @param c C柱子
*/
public static void towerOfHanoi(int discNum, char a, char b, char c) {
// 如果只有一个盘
if (discNum == 1) {
System.out.println('第1个盘' + a + '->' + c);
} else {
// 盘的数量 >= 2
// 1.上盘A->B
towerOfHanoi(discNum - 1, a, c, b);
// 2.下盘A->C
System.out.println('第' + discNum + '个盘' + a + '->' + c);
// 3.把B柱子的所有盘子移至C柱子
towerOfHanoi(discNum - 1, b, a, c);
}
}
JavaScript代码实现：
function towerOfHanoi(discNum, a, b , c) {
if (discNum === 1) {
console.log('第1个盘' + a + '->' + c);
} else {
towerOfHanoi(discNum - 1, a, c, b);
console.log('第' + discNum + '个盘' + a + '->' + c);
towerOfHanoi(discNum - 1, b, a ,c);
}
}
towerOfHanoi(3, 'A', 'B', 'C');
Python代码实现：
def tower_of_hanoi(disc_num, a, b, c):
if disc_num == 1:
print('第1个盘' + a + '->' + c)
else:
# 上盘 A->B
tower_of_hanoi(disc_num - 1, a, c, b)
# 下盘 A->C
print('第' + str(disc_num) + '个盘' + a + '->' + c)
# B柱子所有盘 B->C
tower_of_hanoi(disc_num - 1, b, a, c)
if __name__ == '__main__':
tower_of_hanoi(3, 'A', 'B', 'C')
3、动态规划算法
3.1、引子
背包问题：现有一个背包，容量为4磅。现有如下物品：
| 物品 | 重量 | 价格 |
|---|
| 吉他(G) | 1 | 1500 | | 音响(S) | 4 | 3000 | | 电脑(D) | 3 | 2000 |
1、要求达到的目标为装入的背包的总价值最大，并且重量不超出
2、要求装入的物品不能重复
3.2、动态规划算法基本介绍
1、动态规划(Dynamic Programming)算法（简称DP算法）的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
2、动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
3、与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
4、动态规划可以通过填表的方式来逐步推进，得到最优解
3.3、代码实现背包问题
1、背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分 01 背包和完全背包(完全背包指的是：每种物品都有无限件可用)
2、这里的问题属于 01 背包，即每个物品最多放一个。而无限背包可以转化为 01 背包。
3、算法的主要思想：利用动态规划来解决。每次遍历到的第 i 个物品，根据w[i] 和 v[i] 来确定是否需要将该物品放入背包中。即对于给定的 n 个物品，设 v[i]、w[i]分别为第 i 个物品的价值和重量，C 为背包的容量。再令 v[i][j]表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。
基于以上设定我们得出：
/*
(1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是 0
(2) 当 w[i]> j时：v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略
(3) 当 j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 当准备加入的新增的商品的容量小于等于当前背包的容量,装入的方式:
1. v[i-1][j]： 就是上一个单元格的装入的最大值
2. v[i]: 表示当前商品的价值
3. v[i-1][j-w[i]]： 装入 i-1 商品，到剩余空间 j-w[i]的最大值
4. 当 j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
*/
图解：
视频讲解地址：https://www.bilibili.com/video/BV1E4411H73v?p=158
Java代码实现：
public static void main(String[] args) {
int[] wight = new int[]{1, 4, 3}; // 物品的重量
int[] price = new int[]{1500, 3000, 2000}; // 物品的价格
int m = 4; // 背包的容量
int n = price.length; // 物品的个数
// 创建一个二维数组
// v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
int[][] v = new int[n + 1][m + 1];
// 初始化第一行和第一列，这里在本程序中，可以不去处理，因为默认就是0
for (int i = 0; i < v.length; i++) {
v[i][0] = 0; // 将第一列设置为0
}
for (int i = 0; i < v.length; i++) {
v[0][i] = 0; // 将第一行设置为0
}
// 为了记录放入商品的情况，我们定一个二维数组
int[][] path = new int[n + 1][m + 1];
// 动态规划处理背包问题
// i和j初始都等于1，目的是不处理第一行第一列
for (int i = 1; i < v.length; i++) {
for (int j = 1; j < v[i].length; j++) {
// 公式
if (wight[i - 1] > j) { // 因为我们程序i是从1开始的，因此原理公式中的w[i]修改成[i-1]
v[i][j] = v[i - 1][j];
} else {
// 因为 i 是从1开始的，因此公式需要做出调整，如下所示
// v[i][j] = Math.max(v[i - 1][j], price[i - 1] + v[i - 1][j - wight[i - 1]]);
if (v[i - 1][j] < price[i - 1] + v[i - 1][j - wight[i - 1]]) {
v[i][j] = price[i - 1] + v[i - 1][j - wight[i - 1]];
// 把当前的情况记录到path
path[i][j] = 1;
} else {
v[i][j] = v[i - 1][j];
}
}
}
}
// 输出v
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++) {
System.out.print(v[i][j] + ' ');
}
System.out.println();
}
// 输出放入的商品情况
int i = path.length - 1; // 行的最大下标
int j = path[0].length - 1; // 列的最大下标
while (i > 0 && j > 0) {
if (path[i][j] == 1) {
System.out.printf('第%d个商品放入到背包\n', i);
j -= wight[i - 1];
}
i--;
}
}
4、KMP算法
4.1、什么是KMP算法
KMP是Knuth、Morris和Pratt首字母的缩写，KMP也是由这三位学者发明（1977年联合发表论文）。
KMP主要应用在字符串的匹配，是一个解决模式串在文本串是否出现过，如果出现过，得出最早出现的位置的经典算法。其主要思想是：当出现字符串不匹配时，可以知道之前已经匹配的文本内容，可以利用这些信息避免从头再去匹配，从而提高匹配效率。
因此如何记录已经匹配的文本内容，才是KMP的重点~这也使得next数组派上了用场。
KMP算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到前面匹配过的位置，省去了大量的计算时间。
4.2、暴力匹配
现给出一段字符串str1：'硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好'，和一段子字符串str2：'尚硅谷你'。
要求写出判断str1是否含有str2的代码，如果存在就返回第一次出现的位置，如果没有则返回-1。
说到字符串匹配，我们第一时间想到的是直接遍历字符串，看看是否存在。这种方法称为暴力匹配，抛开效率不说，这种方式是最直接，最简单的方式。
然而暴力匹配也是一种算法，一种解决方案，针对上述问题，我们可以得出暴力匹配算法的思路（假设现在 str1 匹配到 i 位置，子串 str2 匹配到 j 位置）：
- 如果当前字符匹配成功（即 str1[i] == str2[j]），则 i++，j++，继续匹配下一个字符
- 如果失配（即 str1[i] != str2[j]），令 i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为 0
- 用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间(不可行!)
Java代码实现：
/**
* 暴力匹配算法
* @param str1
* @param str2
* @return 返回str2首次出现在str1的位置，匹配不到则返回-1
*/
public static int violenceMatch(String str1, String str2) {
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int i = 0; // 指向s1
int j = 0; // 指向s2
while (i < s1.length && j < s2.length) {
if (s1[i] == s2[j]) {
i++;
j++;
} else {
// 只要有一个没有匹配上
i = i - (j - 1);
j = 0;
}
}
// 判断是否匹配成功
if (j == s2.length) {
return i - j;
}
return -1;
}
在main方法中测试暴力匹配：
public class AlgorithmUtils {
public static void main(String[] args) {
String str1 = '硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好';
String str2 = '尚硅谷你';
int index = AlgorithmUtils.violenceMatch(str1, str2);
if (index != -1) {
System.out.printf('第一次出现的位置是%d', index);
}
}
}
Python代码实现：
def violence_match(str1, str2):
s1 = list(str1)
s2 = list(str2)
i, j = 0, 0
while i < len(s1) and j < len(s2):
if s1[i] == s2[j]:
i += 1
j += 1
else:
i = i - (j - 1)
j = 0
if j == len(s2):
return i - j
return -1
if __name__ == '__main__':
str1 = '硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好'
str2 = '尚硅谷你'
print(violence_match(str1, str2)) # 4
JavaScript代码实现：
function violenceMatch(str1, str2) {
let s1 = Array.from(str1);
let s2 = Array.from(str2);
let i = 0;
let j = 0;
while (i < s1.length && j < s2.length) {
if (s1[i] === s2[j]) {
i++;
j++;
} else {
i = i - (j - 1);
j = 0;
}
}
if (j === s2.length) {
return i - j;
}
return -1;
}
function main() {
let str1 = '硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好';
let str2 = '尚硅谷你';
console.log(violenceMatch(str1, str2));
}
main();
4.3、KMP算法实现
前面呢我们已经使用暴力匹配算法，完成了上述问题的求解！也知道了暴力匹配存在效率问题，那么KMP算法又是怎样实现呢？
为方便阐述，这里我们换个案例：现有两组字符串
str1 = 'BBC ABCDAB ABCDABCDABDE';
str2 = 'ABCDABD';
要求使用 KMP算法 完成判断，str1 是否含有 str2，如果存在，就返回第一次出现的位置，如果没有，则返回-1。
备注：不能使用简单的暴力匹配算法！！！
思路与图解（视频讲解地址）：https://www.bilibili.com/video/BV1E4411H73v?p=161
END
THANK YOU
|
