java实现十大经典算法
java10大经典算法 分治算法 贪婪算法 普利姆算法
二分查找算法（非递归）
/*** @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] + "\t");
}
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--;
}
}
}
View Code
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("没有找到！");
}
}
}
View Code
贪心算法
/*** @desc 贪心算法
* 思路分析
* （1）使用穷举法，列出每个可能广播台集合，这被称为幂集。
* （2）假设有n个广播台，则广播台的组合共有2^n-1个，假设每秒可以计算10个子集
* 广播台数量 子集总数 需要的时间
* 5 32 3.2秒
* 10 1024 102.4秒
* ...
*
* 案例：集合覆盖问题
* 假设存在下面需要付费的广播台，以及广播信号可以覆盖的地区，如何选择
* 最少的广播台，让所有的地区都可以接收信息
* 广播台 覆盖地区
* K1 "北京","上海","天津"
* K2 "广州","北京","深圳"
* K3 "成都","上海","杭州"
* K4 "上海","天津"
* K5 "杭州","大连"
* @Author xw
* @Date 2019/9/27
*/
public class GreedyAlgorithm {
public static void main(String[] args) {
Map<String, Set<String>> broadcasts = new HashMap<>(); // 广播电台
broadcasts.put("K1", Arrays.stream(new String[]{"北京", "上海", "天津"}).collect(Collectors.toSet()));
broadcasts.put("K2", Arrays.stream(new String[]{"广州", "北京", "深圳"}).collect(Collectors.toSet()));
broadcasts.put("K3", Arrays.stream(new String[]{"成都", "上海", "杭州"}).collect(Collectors.toSet()));
broadcasts.put("K4", Arrays.stream(new String[]{"上海", "天津"}).collect(Collectors.toSet()));
broadcasts.put("K5", Arrays.stream(new String[]{"杭州", "大连"}).collect(Collectors.toSet()));
// [上海, 天津, 北京, 广州, 深圳, 成都, 杭州, 大连]
List<String> allAreas = broadcasts.values().stream().flatMap(Collection::stream).distinct().collect(Collectors.toList()); // 表示所有需要覆盖的地区
System.out.println("allAreas=" + allAreas);
List<String> selects = new ArrayList<>(); // 选择的地区集合
// 定义一个临时的集合，在遍历过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
Set<String> tempSet = new HashSet<>();
String maxKey; // 最大的电台，保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台key
while (allAreas.size() != 0) {
maxKey = null; // 置空
// 遍历broadcasts，取出对应key
for (String key : broadcasts.keySet()) {
tempSet.clear(); // 清空
Set<String> areas = broadcasts.get(key);
tempSet.addAll(areas);
tempSet.retainAll(allAreas); // tempSet = tempSet与allAreas的交集
if (tempSet.size() > 0 && (maxKey == null
|| tempSet.size() > broadcasts.get(maxKey).size())) {
maxKey = key;
}
}
if (maxKey != null) {
selects.add(maxKey);
// 将maxKey指向的广播电台覆盖地区，从allAreas去掉
System.out.println("maxKey=" + maxKey);
allAreas.removeAll(broadcasts.get(maxKey));
}
}
System.out.println("得到的选择结果是：" + selects);
}
}
View Code
普利姆算法
/*** @desc 普利姆算法
* 应用案例：修路问题
* <p>
* 思路分析
* 1.从<A>顶点开始处理=><A,G> 2
* A,C[7] A-G[2] A-B[5] =>
* 2.<A,G>开始，将A和G顶点和他们相邻的还没有访问的顶面进行处理=> <A,G,B>
* A-C[7] A-B[5] G-B[3] G-F[6]
* 3.<A,G,B>开始，将A,G,B顶点和他们相邻的还没有访问的顶面进行处理=> <A,G,B>
* A-C[7] G-E[4] G-F[6] B-D[9]
* ...
* 4.{A,G,B,E,F,D} -> C // 第6次大循环，对应边<A,C>权值：7 => <A,G,B,E,F,D,C>
* @Author xw
* @Date 2019/10/4
*/
public class PrimAlgorithm {
public static void main(String[] args) {
char[] data = {\'A\',\'B\',\'C\',\'D\',\'E\',\'F\',\'G\'};
int verxs = data.length;
// 邻接矩阵
int[][] weight = new int[][] {
{10000,5,7,10000,10000,10000,2},
{5,10000,10000,9,10000,10000,3},
{7,10000,10000,10000,8,10000,10000},
{10000,9,10000,10000,10000,4,10000},
{10000,10000,8,10000,10000,5,4},
{10000,10000,10000,4,5,10000,6},
{2,3,10000,10000,4,6,10000}
};
// 创建MGraph对象
MGraph graph = new MGraph(verxs);
// 创建最小树
MinTree minTree = new MinTree();
minTree.createGraph(graph, verxs, data, weight);
// 输出
minTree.showGraph(graph);
// 测试普利姆算法
minTree.prim(graph, 0);
}
}
View Code
克鲁斯卡尔算法
/*** @desc 克鲁斯卡尔算法
* 案例：公交车问题
* 1. 某城市新增7个站点，A,B,C,D,E,F,G,现在需要修路7个站点连通
* 2. 各个站点距离用连线表示，比如A-B距离12公里
* 3. 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短
* @Author xw
* @Date 2019/10/8
*/
public class KruskalCase {
private static final int INF = Integer.MAX_VALUE;
private char[] vertexs;
private int[][] matrix;
private int edgeNums; // 边的数量
public KruskalCase(char[] vertexs,int[][] matrix ) {
this.vertexs = vertexs;
this.matrix = matrix;
// 统计边
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) { // 每次少一条边，所以是i+1
if (this.matrix[i][j] != INF) {
edgeNums++;
}
}
}
}
public static void main(String[] args) {
char[] vertexs = {\'A\', \'B\', \'C\', \'D\', \'E\', \'F\', \'G\'};
int[][] matrix = {
/*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/{ 0, 12, INF, INF, INF, 16, 14 },
/*B*/{ 12, 0, 10, INF, INF, 7, INF},
/*C*/{ INF, 10, 0, 3, 5, 6, INF },
/*D*/{ INF, INF, 3, 0, 4, INF, INF },
/*E*/{ INF, INF, 5, 4, 0, 2, 8 },
/*F*/{ 16, 7, 6, INF, 2, 0, 9 },
/*G*/{ 14, INF, INF, INF, 8, 9, 0 }
};
// 创建KruskalCase对象实例
KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
//
kruskalCase.print();
kruskalCase.kruskal();
}
}
View Code
迪杰斯特拉算法
/*** @desc 迪杰斯特拉算法
* 案例：最短路径问题
* 1. 战争时期，胜利乡有7个村庄(A,B,C,D,E,F,G)，现在有6个邮差，从G点出发，需要分别把邮件分别送到A,B,C,D,E,F 六个村庄
* 2. 各个村庄的距离用边线表示（权），比如A-B距离5公里
* 3. 问：如何计算最短距离
*
* @Author xw
* @Date 2019/10/8
*/
public class DijkstraAlgorithm {
public static void main(String[] args) {
char[] vertex = {\'A\', \'B\', \'C\', \'D\', \'E\', \'F\', \'G\'};
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;
matrix[0] = new int[]{N,5,7,N,N,N,2};
matrix[1] = new int[]{5,N,N,9,N,N,3};
matrix[2] = new int[]{7,N,N,N,8,N,N};
matrix[3] = new int[]{N,9,N,N,N,4,N};
matrix[4] = new int[]{N,N,8,N,N,5,4};
matrix[5] = new int[]{N,N,N,4,5,N,6};
matrix[6] = new int[]{2,3,N,N,4,6,N};
// 创建Graph对象
Graph graph = new Graph(vertex, matrix);
graph.showGraph();
// 测试迪杰斯特拉算法
graph.dsj(6); // G
graph.showDijkstra();
}
}
View Code
弗洛伊德算法
/*** @desc 弗洛伊德算法
* @Author xw
* @Date 2019/10/8
*/
public class FloydAlgorithm {
public static void main(String[] args) {
char[] vertex = {\'A\', \'B\', \'C\', \'D\', \'E\', \'F\', \'G\'};
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;
matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
matrix[2] = new int[]{7, N, 0, N, 8, N, N};
matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};
FloydGraph graph = new FloydGraph(vertex.length, matrix, vertex);
graph.floyd();
graph.show();
}
}
View Code
马踏棋盘算法
/*** @desc 马踏棋盘算法
* @Author xw
* @Date 2019/10/8
*/
public class HorseChessboard {
private static int X; // 棋盘的列数
private static int Y; // 棋盘的行数
//创建一个数组，标记棋盘的各个位置是否被访问过
private static boolean visited[];
//使用一个属性，标记是否棋盘的所有位置都被访问
private static boolean finished; // 如果为true,表示成功
public static void main(String[] args) {
System.out.println("骑士周游算法，开始运行~~");
//测试骑士周游算法是否正确
X = 8;
Y = 8;
int row = 1; //马儿初始位置的行，从1开始编号
int column = 1; //马儿初始位置的列，从1开始编号
//创建棋盘
int[][] chessboard = new int[X][Y];
visited = new boolean[X * Y];//初始值都是false
//测试一下耗时
long start = System.currentTimeMillis();
traversalChessboard(chessboard, row - 1, column - 1, 1);
long end = System.currentTimeMillis();
System.out.println("共耗时: " + (end - start) + " 毫秒");
//输出棋盘的最后情况
for(int[] rows : chessboard) {
for(int step: rows) {
System.out.print(step + "\t");
}
System.out.println();
}
}
}
View Code
gitee地址：https://gitee.com/linestyle007/jucdemo2
以上是 java实现十大经典算法 的全部内容， 来源链接： utcz.com/z/393456.html
