程序员必知必会十大算法（一）数据结构与算法qq44895397的博客-

1、二分算法

进行二分查找的数组必须是有序的
二分查找法是对一组有序的数字中进行查找，传递相应的数据，进行比较查找到与原数据相同的数据，查找到了返回对应的数组下标，没有找到返回-1；

递归实现二分查找：

 /**   * 递归实现   *   * @param arr   * @param left   * @param right   * @param index   * @return   */ public static int binarySearch(int[] arr, int left, int right, int index) { if (left <= right) { int mid = (right + left) / 2; if (arr[mid] == index) return mid; if (index > arr[mid]) return binarySearch(arr, mid + 1, right, index); else return binarySearch(arr, left, mid - 1, index); } return -1; } 

非递归实现二分查找：

public static int binarySearch02(int[] arr, int index) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == index) return mid; else if (arr[mid] > index) right = mid - 1; else left = mid + 1; } return -1; } 

2、分治算法（解决汉诺塔问题）

汉诺塔（港台：河内塔）是根据一个传说形成的数学问题：
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
每次只能移动一个圆盘；
大盘不能叠在小盘上面。
提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？

求解：
解法的基思想是递归。假设有 A、B、C 三个塔，A 塔有 {displaystyle N}N 块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的 {displaystyle N-1}{displaystyle N-1} 块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 {displaystyle N-1}{displaystyle N-1} 块盘移到 C。
* 如此递归地使用下去, 就可以求解。

代码实现：

 /**   * @param num 盘子数   * @param a   塔名   * @param b   * @param c   //移动的目标   */ public static void fun(int num, char a, char b, char c) { if (num == 1) {          System.out.println("第一个盘子" + a + "->" + c); } else { //有大于等于2的盘子，则把这些盘子看成两部分。1、最底下一部分的盘子-->a-c //2、上面所有盘子 这些盘子先移动到全部b fun(num - 1, a, c, b);//把上面部分的盘子从a移动到b，借助c          System.out.println("第" + num + "个盘子 " + a + "->" + c); fun(num - 1, b, a, c);//b->c } } 

3、动态规划（解决0-1背包问题）

什么是0-1背包问题？
小偷从入门到精通（滑稽）
首先得知道什么是0-1背包问题（knapsack problem）

 ◆ 贼，夜入豪宅，可偷之物甚多，而负重能力有限，偷哪些才更加不枉此行？     ◆ 抽象的话，就是：       给定一组多个（[公式]）物品，    每种物品都有自己的重量（[公式]）和价值（[公式]），在限定的总重量/总容量（[公式]）内，    选择其中若干个（也即每种物品可以选0个或1个），设计选择方案使得物品的总价值最高。 

代码实现：

public static void main(String[] args) { int[] weight = {1, 4, 3};//表示物品的重量 int[] value = {1500, 3000, 2000};//物品的价值 int m = 4;//背包的容量 int n = value.length;//物品的个数 int[][] v = new int[n + 1][m + 1]; int[][] path = new int[n + 1][m + 1];//放入商品的记录 for (int i = 0; i < v.length; i++) {             v[i][0] = 0;//二维数组第一列为0 } for (int i = 0; i < v[0].length; i++) {             v[0][i] = 0;//让二维数组第一行为0 } //放入商品进行动态规划 //二维数组列表示的是商品，行表示背包的容量逐渐增加 //第二列，虽然背包的容量虽然增加，商品种类只有一种，所以没有比较 for (int i = 1; i < v.length; i++) { for (int j = 1; j < v[0].length; j++) { if (weight[i - 1] > j) {//当前商品的重量大于了背包的容量，就从上一各取结果                     v[i][j] = v[i - 1][j]; } else { // weight[i]<=j 我们首先尝试把当前商品放进去，如果还有多余空间，我们再放入其他商品 //与上一个表格价值进行比较，取最大的价值填入当前表格 //v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]); int v1 = (value[i - 1] + v[i - 1][j - weight[i - 1]]); int v2 = v[i - 1][j]; if(v1>v2){                         v[i][j] = v1;                         path[i][j] = 1; }else {                         v[i][j] = v2; } } } } show(v);         System.out.println("======"); show(path); } 

4、暴力匹配算法

假设现在我们面临这样一个问题：有一个文本串 S，和一个模式串 P，现在要查找 P 在 S 中的位置，怎么查找呢？

如果用暴力匹配的思路，并假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置，则有：

1. 如果当前字符匹配成功（即 S[i] == P[j]），则 i++，j++，继续匹配下一个字符；
2. 如果失配（即 S[i]! =P[j]），令 i = i – (j – 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：

 public static int violenceMath(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int s1len = s1.length; int s2len = s2.length; int i = 0;//表示匹配s1的索引 int j = 0;//表示匹配s2的索引 while (i < s1len && j < s2len) { if (s1[i] == s2[j]) {//匹配成功                  i++;                  j++; } else {//匹配失败                  i = i - (j - 1); } } if (j == s2len) {//完全匹配 return i - s2len; } else { return -1; } } 

5、KMP算法：

定义：
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这三人的姓氏命名此算法。

1、部分匹配表求法：

部分匹配值就是前缀和后缀的最长的共有元素的长度
以”ABCDABD”为例：
A 的前缀和后缀都为空，共有长度为0；
AB 的前缀A 后缀B ，共有长度 0；
ABC 前缀[A,AB]后缀[BC,C]，共有长度 0
ABCD 前缀[A,AB,ABC]后缀[BCD,CD,D]，共有长度 0
ABCDA 前缀[A,AB,ABC,ABCD]后缀[BCDA,CDA,DA,A]，共有元素A，共有长度 1
…

 public static int[] kmpNext(String dest) { int[] next = new int[dest.length()];     next[0] = 0;//只有一个字母的字符串，部分匹配值为0 for (int i = 1,j = 0; i < next.length; i++) { while (j > 0 && dest.charAt(i) != dest.charAt(j)) j = next[j - 1]; if (dest.charAt(i) == dest.charAt(j)) {             j++; }         next[i] = j; } return next; } 

匹配算法：

 /**   * @param str1 字符串   * @param str2 //子串   * @param next //部分匹配值表   * @return   */ public static int kmpSearch(String str1, String str2, int[] next) { for (int i = 0, j = 0; i < str1.length(); i++) { while (j > 0 && str1.charAt(i) != str2.charAt(j)){              j = next[j - 1]; } if (str1.charAt(i) == str2.charAt(j)) {              j++; } if (j == str2.length()) { return i - j + 1; } } return -1; }