二分查找算法

可以用循环或递归

分治算法

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治算法可以求解的一些经典问题
二分搜索
大整数乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔

分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并：将各个子问题的解合并为原问题的解。

例：面试题 08.06. 汉诺塔问题

我的做法：(不对，，没查出来哪里不对)

    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A,B,C);
    }

   public static void move(List<Integer> A, List<Integer> B, List<Integer> C){
        if(A.size() == 2){
            B.add(A.remove(1));
            C.add(A.remove(0));
            C.add(B.remove(0));
            return;
        }
       move(A.subList(1,A.size()),C,B);
       C.add(A.remove(0));
       move(B,A,C);
   }

别人解法：

public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    move(A.size(), A, B, C);
}

private static void move(int n, List<Integer> a, List<Integer> b, List<Integer> c) {
    if (n == 0) return;
    move(n - 1, a, c, b);
    c.add(a.get(a.size() - 1));
    a.remove(a.size() - 1);
    move(n - 1, b, a, c);
}

动态规划算法

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )

动态规划可以通过填表的方式来逐步推进，得到最优解.

算法的主要思想，利用动态规划来解决。每次遍历到的第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]]}

v[i-1][j]： 就是上一个单元格的装入的最大值
v[i] : 表示当前商品的价值
v[i-1][j-w[i]] ： 装入i-1商品，到剩余空间j-w[i]的最大值
当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}

解法：

public class KnapsackProblem {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] w = {1, 4, 3};
		int[] val = {1500, 3000, 2000}; 
		int m = 4;
		int n = val.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; 
		}
		for(int i=0; i < v[0].length; i++) {
			v[0][i] = 0; 
		}
		
	
		for(int i = 1; i < v.length; i++) { 
			for(int j=1; j < v[0].length; j++) {
				if(w[i-1]> j) { 
					v[i][j]=v[i-1][j];
				} else {
					if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
						v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
						path[i][j] = 1;
					} else {
						v[i][j] = v[i - 1][j];
					}
					
				}
			}
		}
		
	
		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();
		}
		
		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("放入背包的商品\n", i); 
				j -= w[i-1]; 
			}
			i--;
		}
		
	}
}

KMP算法

应用场景-字符串匹配问题
字符串匹配问题：
有一个字符串 str1= “ABCBDCE”，和一个子串 str2=“BDC”
现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

KMP算法介绍
KMP方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间
参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

public class KMPAlgorithm {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1 = "BBC ABCDAB ABCDABCDABDE";
		String str2 = "ABCDABD";
		//String str2 = "BBC";
		
		int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
		System.out.println("next=" + Arrays.toString(next));
		
		int index = kmpSearch(str1, str2, next);
		System.out.println("index=" + index); 
		
		
	}
	
	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;
	}
	
	public static  int[] kmpNext(String dest) {
		int[] next = new int[dest.length()];
		next[0] = 0; 
		for(int i = 1, j = 0; i < dest.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;
	}
}