java实现十大经典算法
二分查找算法(非递归)
/** * @desc 二分查询(非递归方式) * 案例: * {1,3,8,10,11,67,100},编程实现二分查找,要求使用非递归方式完成。 * @Author xw * @Date 2019/9/27 */ public class BinarySearchNonRecursive { public static void main(String[] args) { int[] arr = {1, 3, 8, 10, 11, 67, 100}; int index = binarySearch(arr, 1); if (index != -1) { System.out.println("找到了,下标为:" + index); } else { System.out.println("没有找到--"); } } private 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; } }
分治算法
/** * @desc 分治算法案例:汉诺塔 * (1)基本概念 * 分治算法是一种很重要的算法,字面上的解释是“分而治之”,就是把一个复杂的问题 * 分解成两个或更多的相同或相似的子问题...直到最后子问题可以简单的直接求解,原 * 问题的解即子问题的解的合并,这个技巧就是很多高效算法的基础,如排序算法(快速排序,归并排序),傅里叶变换(快速傅里叶变换)... * (2)基本步骤 * 1)分解:将原问题分解为若干个规模较小的问题,相互独立,与原问题形式相同的子问题 * 2)解决:若子问题规模较小则直接解决,否则递归地解各个子问题 * 3)合并:将各个子问题的解合并为原问题的解 * (3)分治算法设计模式 * if |P|<=n0 * then return (ADHOC(P)) * // 将P分解为较小的问题P1,P2...PK * for i <- 1 to k * do yi <- Divide-and-Conquer(Pi) 递归解决Pi * T <- MERGE(y1,y2...yk) 合并子问题 * return (T) * <p> * |P|:表示问题P的规模 * n0:表示阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。 * ADHOC(P):是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时直接用算法ADHOC(P)求解 * 算法MERGE(y1,y2...yk):是该分治算法中的合并子算法,用于将P的子问题P1,P2...PK的相应的解y1,y2,..yk合并为P的解。 * <p> * 经典案例:汉诺塔 * 思路分析: * (1)如果有一个盘,A->C * n0=2 * if (n<=n0) { * // 直接解出来 * } * // 将P分解为较小的问题P1,P2...PK * while(n>n0) { * 分(n); * n--; * } * // T <- MERGE(y1,y2...yk) 合并子问题 * @Author xw * @Date 2019/9/27 */ public class HanoiTower { public static void main(String[] args) { hanoiTower(3, 'A', 'B', 'C'); } private static void hanoiTower(int num, char a, char b, char c) { if (num == 1) { // 只有一个盘,直接解出 System.out.println("第1个盘从" + a + "->" + c); } else { // 如果n>=2的情况 // 1.先把最上面的所有盘A->B,移动过程会使用C hanoiTower(num - 1, a, c, b); // 2.把最下边的盘A->C System.out.println("第" + num + "个盘从" + a + "->" + c); // 3.把B塔所有盘从B->C,移动过程使用到A hanoiTower(num - 1, b, a, c); } } }
动态规划算法
/** * @desc 动态规划算法案例:背包问题 * 思路分析: * (1)假设: * 用w[i],v[i]来确定是否需要将该物品放入背包中; * 即对于给定的n个物品,设v[i],w[i]分别为第i个物品的价值和重量,C为背包的容量。 * 再令v[i][j] 表示在前i个物品中能够装入容量j的背包的最大价值。则我们有下面的结果: * (2)结论: * 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-1][j-w[i]]} * <p> * 案例: * 物品 重量 价格 * 吉他(G) 1 1500 * 音响(S) 4 3000 * 电脑(L) 3 2000 * @Author xw * @Date 2019/9/27 */ public class KnapsackProblem { public static void main(String[] args) { 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]; // 1)当v[i][0]=v[0][j]=0; // 表示填入表 第一行和第一列是0 for (int i = 0; i < v.length; i++) { v[0][i] = 0; // 第一列为0 } for (int i = 0; i < v.length; i++) { v[i][0] = 0; // 第一行为0 } int[][] path = new int[n + 1][m + 1]; for (int i = 1; i < v.length; i++) { for (int j = 1; j < v[0].length; j++) { // 不处理第1列 // 当w[i]>j时;v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于当前背包的容量时,就直接使用上一个单元格的装入策略 if (w[i - 1] > j) { v[i][j] = v[i - 1][j]; } else { // 当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]的最大值 // 当准入的新增的商品的容量小于等于当前背包的容量,装入方式: if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) { // w[i]->w[i-1]替换? v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]]; // 把当前的情况记录到path 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("========================"); /*for (int i = 0; i < path.length; i++) { for (int j = 0; j < path[i].length; j++) { if (path[i][j] == 1) { System.out.println(String.format("第%d个商品放入背包", i)); } } }*/ // 其实我们只需要最后的放入 int i = path.length - 1; int j = path[0].length - 1; while (i > 0 && j > 0) { if (path[i][j] == 1) { System.out.println(String.format("第%d个商品放入到背包", i)); j -= w[i - 1]; } i--; } } }
KMP算法
/** * @desc KMP算法 * 基本介绍: * (1)暴力匹配算法 * 1)如果当前字符匹配成功(即str1[i]=str2[i]),则i++,j++,继续匹配下一个字符 * 2)如果失败,令i=i-(j-1),j=0,相当于每次匹配失败时,i回溯,j被转为0 * 3)用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费大量时间。(不可行) * 4)暴力匹配实现 * (2)KMP算法介绍 * 1)KMP是一个解决模式串在文本串是否出现过,如果出现过,最早出现的位置就经典算法。 * 2)Knuth-Morris-Pratt字符串查找法,简称KMP。 * 3)KMP算法就是利用之前判断过信息,通过一个next数组,保存模式串中前后最长公共序列的长度,每次回溯时,通过next数组找到, * 前面匹配的位置,省去了大量的计算时间 * 4)参考资料:https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html * @Author xw * @Date 2019/9/27 */ public class KMPAlgorithm { public static void main(String[] args) { // 暴力匹配 String str1 = "ABCDE"; String str2 = "CD"; int index = violenceMatch(str1, str2); if (index != -1) { System.out.println("找到了,位置:" + index); } else { System.out.println("没有找到!"); } // KMP算法介绍 // 字符串模板匹配值 str1 = "BBC ABCDAD ABCDABCDABDE"; str2 = "ABCDABD"; /*int[] next = kmpNext("ABCDABD"); System.out.println("next=" + Arrays.toString(next));*/ index = kmpMatch(str1, str2, kmpNext(str2)); if (index != -1) { System.out.println("找到了,位置:" + index); } else { System.out.println("没有找到!"); } } }