- 1.二分查找算法
- 2.分治算法（如何分---递归算法）
- 汉诺塔
- 3.回溯算法
- 4.动态规划算法（前一个子问题与后一个子问题之间不相互独立，依赖关系）
- 背包问题（01背包）
- 4. 贪心算法（局部最优-->全局最优的近似）——没有套路----刷题去
- 5.KMP算法
- 字符串匹配问题
- 最小生成树（Prim和Kruskal）
- Prim算法
- Kruskal算法（排序+不允许构成回路）
非递归版：
public static int binarySearch(int[] arr,int target){
int left=0;
int right=arr.length-1;
while(left<=right){
int mid=(left+right)/2;
if(arr[mid]==target){
return mid;
}else if(arr[mid]>target){
right=mid-1;//向左边继续查找
}else{
left=mid+1;//向右边继续查找
}
}
return -1;//如果没有这样的数据就返回-1
}
递归版：
public static int binary(int[] arr,int target,int left,int right){
if(left<=right){
int mid=(left+right)/2;
if(arr[mid]>target){
return binary(arr,target,left,mid-1);//继续递归，如果递归结束时也会返回一个数，这个数才是真正的结果
}else if(arr[mid]
2.分治算法（如何分—递归算法）
递归的三部曲：
汉诺塔
分治算法案例实现—64层的汉诺塔实现
解题思路：每次将盘查分为1和（num-1）个盘进行移动，1为目标盘，（num-1）在辅助盘
public static void hanoTower(int num,char a,char b,char c){
if(num==1){
System.out.println("把顶盘从"+a+"移动到"+c);
return;
}
if(num>1){
//每次将盘查分为1和（num-1）个盘进行移动，1为目标盘，（num-1）在辅助盘
//首先将上边（num-1）盘移动到b盘（作为辅助盘）
hanoTower(num-1,a,c,b);
//然后将最后的盘从a移动到c
hanoTower(1,a,b,c);
//将b盘中的（num-1）个移动到c盘(没有用的盘作为辅助盘)
hanoTower(num-1,b,a,c);
}
}
}
3.回溯算法
（递归----纵向深度----终止条件，回溯----横向宽度----for循环----位于递归函数的下方进行撤销操作）
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
回溯的模板-----void backtracking（）函数：
4.动态规划算法（前一个子问题与后一个子问题之间不相互独立，依赖关系）
动态规划5部曲（carl哥）：
背包问题（01背包）
背包问题的解释(案例：01背包，每个物件最多只能用1次)
01背包的过程填表（dp数组）
根据上表来推导出下面的递推公式：
韩顺平老师的扩展，继续输出最佳的组合物品放置情况
public class DynamicProgram {
public static void main(String[] args) {
int[] val={1500,3000,2000};//物品的价值(序号从零开始)
int[] w={1,4,3};//物品的重量(序号从零开始)
int m=4;//背包的最大容量
int[][] v=new int[val.length+1][m+1];//存放前i个物品时的总重量j(new 的时候默认为0)
int[][] path=new int[val.length+1][m+1];
//默认初始化了没有物品v[0][:]=0,初始化没有重量v[:][0]=0
//用于下面的延续与比较或者继承
for (int i = 0; i j){
//当前这个物品的重量超过了背包总重量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]=v[i-1][j];
}else{
//针对同一列时，相对于上一行的值有更新，那么就需要path置1：就说明有新的物品放入背包里(最佳值一定会经过)
v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
path[i][j]=1;
}
}
}
}
System.out.println("_______动态规划表_____");
for (int i = 0; i 0&&j>0){
if(path[i][j]==1){
System.out.println("第"+i+"物品放入背包");
j=j-w[i-1];//这个很关键，减去当前物品的重量，剩余可装入的物品的重量
}
i--;
}
}
}
4. 贪心算法（局部最优–>全局最优的近似）——没有套路----刷题去
5.KMP算法
（字符串的匹配查找问题carl哥讲解）
字符串的前缀和后缀
最终的部分匹配表：
字符串匹配问题
字符串匹配的实际案例-----利用前缀表（部分匹配表）：
构造前缀表的原理没有看懂：利用"前缀表"(可以是整体减1的数组表，据说一共有3种)直接作为next数组（即下面代码的KMPtable）
j回溯的过程就是在递减，也就是在arr[i]与arr[j]不相同,需要重新计算最长相同的前后缀长度,不相同时就继续递减这个j的长度（j代表了最长相同的前后缀长度）。充分理解i与j具体的含义，arr[i]始终代表了当前的前i个字符组成的字符串的最长相同的前后缀长度。（下图是carl哥的手）
public class KMPsearchString {
public static void main(String[] args) {
String s1="aabaabaafa";
String s2="aabaaf";
System.out.println(Arrays.toString(KMPtable(s2)));
int i = KMPsearch(s1, s2, KMPtable(s2));
System.out.println(i);
}
//KMP字符串搜索匹配（返回匹配到的首个元素的位置）
public static int KMPsearch(String s1,String s2,int[] KMPtable){
for (int i = 0,j=0; i 0 && s1.charAt(i)!=s2.charAt(j)){
j=KMPtable[j-1];//将j移动至不匹配字符的前一个字符的前缀表下标的位置，下回比较时直接从模式串的这个位置开始比较
}
if(s1.charAt(i)==s2.charAt(j)){
j++;
}
if(j==s2.length()){//说明匹配上了
return i-j+1;
}
}
return -1;//没有找到
}
//KMP字符串部分匹配表
public static int[] KMPtable(String des){
int[] matchTable=new int[des.length()];
matchTable[0]=0;//字符串的第一个字符没有前缀和后缀
for (int i = 1,j=0; i 0 && des.charAt(i)!=des.charAt(j)){
//开始回退j，一直回退到有相同的元素，实际回退的过程就是在递减j
j=matchTable[j-1];//设置j大于0，防止出现，数组越界
}
if(des.charAt(i)==des.charAt(j)){
j++;
}
matchTable[i]=j;
}
return matchTable;
}
}
最小生成树（Prim和Kruskal）
Prim算法
解决修路问题：
Kruskal算法（排序+不允许构成回路）
公交站问题：
如何判断新加入的边后有无形成回路：
