Java 实现经典算法，阿里 java 技术专家面试
解决：若子问题规模较小则直接解决，否则递归地解各个子问题
合并：将各个子问题的解合并为原问题的解
分治算法案例：汉诺塔
/**
经典案例：汉诺塔
思路分析：
（1）如果有一个盘，A->C
n0=2
if (n<=n0) {
// 直接解出来
}
// 将 P 分解为较小的问题 P1,P2...PK
while(n>n0) {
分(n);
n--;
}
// T <- MERGE(y1,y2...yk) 合并子问题
@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);
}
}
}
算法案例：背包问题
/**
@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--;
}
}
}
KMP 算法介绍
KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置就经典算法。Knuth-Morris-Pratt 字符串查找法，简称 KMP。KMP 算法就是利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共序列的长度，每次回溯时，通过 next 数组找到，前面匹配的位置，省去了大量的计算时间
/**
@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 != -
{
System.out.println("找到了，位置：" + index);
} else {
System.out.println("没有找到！");
}
}
}
思路分析
（1）使用穷举法，列出每个可能广播台集合，这被称为幂集。
（2）假设有 n 个广播台，则广播台的组合共有 2^n-1 个，假设每秒可以计算 10 个子集
广播台数量 子集总数 需要的时间
5 32 3.2 秒
10 1024 102.4 秒
...
案例：集合覆盖问题
/**
@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);
}
}
/**
应用案例：修路问题
<p>
思路分析
1.从<A>顶点开始处理=><A,G> 2
2.<A,G>开始，将 A 和 G 顶点和他们相邻的还没有访问的顶面进行处理=> <A,G,B>
3.<A,G,B>开始，将 A,G,B 顶点和他们相邻的还没有访问的顶面进行处理=> <A,G,B>
...
4.{A,G,B,E,F,D} -> C // 第 6 次大循环，对应边<A,C>权值：7 => <A,G,B,E,F,D,C>
@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);
}
}
/**
案例：公交车问题
某城市新增 7 个站点，A,B,C,D,E,F,G,现在需要修路 7 个站点连通
各个站点距离用连线表示，比如 A-B 距离 12 公里
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论