Java 数据结构与算法系列精讲之贪心算法
作者:我是小白呀 时间:2023-09-12 17:56:13
概述
从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
贪心算法
贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果.
贪心算法的优缺点:
优点: 贪心算法的代码十分简单
缺点: 很难确定一个问题是否可以用贪心算法解决
电台覆盖问题
假设存在以下的广播台, 以及广播台可以覆盖的地区:
广播台 | 覆盖地区 |
---|---|
K1 | 北京, 上海, 天津 |
K2 | 北京, 广州, 深圳 |
K3 | 上海, 杭州, 成都 |
K4 | 上海, 天津 |
K5 | 杭州, 大连 |
贪心算法的核心思想:
把所有需要覆盖的地区取集合
从电台中取覆盖集合中地区最多的一个
集合中去除已覆盖地区, 继续匹配
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class 贪心算法 {
// 集合, 存放广播台
static HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
// 集合, 存放地区
static HashSet<String> areas = new HashSet<String>();
// 贪心算法
public static ArrayList<String> Greedy() {
// 创建数组存放结果
ArrayList<String> selects = new ArrayList<>();
// 循环直至地区都覆盖
while (areas.size() != 0) {
// 存放交集最大的广播台
String maxKey = null;
// 存放交集最大的值
int maxKeySize = 0;
// 遍历每个剩余电台
for (String key : broadcasts.keySet()) {
// 取出交集个数
int currSize = getRetainSize(key);
// 替换当前最大
if (currSize > 0 && currSize > maxKeySize) {
maxKey = key;
maxKeySize = currSize;
}
}
// 添加广播台到结果
selects.add(maxKey);
// 移除广播台
areas.removeAll(broadcasts.get(maxKey));
}
return selects;
}
// 剩余数量
public static int getRetainSize(String key) {
// 如果为空返回0
if (key == null) return 0;
// 存放key对应的地区集合
HashSet<String> tempSet = new HashSet<>();
// 取key对应的地区
tempSet.addAll(broadcasts.get(key));
// 取交集
tempSet.retainAll(areas);
return tempSet.size();
}
public static void main(String[] args) {
// | K1 | 北京, 上海, 天津 |
// | K2 | 北京, 广州, 深圳 |
// | K3 | 上海, 杭州, 成都 |
// | K4 | 上海, 天津 |
// | K5 | 杭州, 大连 |
// 创建广播台
HashSet<String> K1 = new HashSet<>(Arrays.asList("北京", "上海", "天津"));
HashSet<String> K2 = new HashSet<>(Arrays.asList("北京", "广州", "深圳"));
HashSet<String> K3 = new HashSet<>(Arrays.asList("上海", "杭州", "成都"));
HashSet<String> K4 = new HashSet<>(Arrays.asList("上海", "天津"));
HashSet<String> K5 = new HashSet<>(Arrays.asList("杭州", "大连"));
// 加入map
broadcasts.put("K1", K1);
broadcasts.put("K2", K2);
broadcasts.put("K3", K3);
broadcasts.put("K4", K4);
broadcasts.put("K5", K5);
areas.addAll(K1);
areas.addAll(K2);
areas.addAll(K3);
areas.addAll(K4);
areas.addAll(K5);
// 调试输出
System.out.println(broadcasts);
System.out.println(areas);
ArrayList<String> result = Greedy();
System.out.println(result);
}
}
来源:https://iamarookie.blog.csdn.net/article/details/122120409
标签:Java,贪心算法,数据结构,算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
入门JDK集合之HashMap解析
2023-11-24 02:45:03
![](https://img.aspxhome.com/file/2023/1/59901_0s.png)
深入理解C# DateTime日期格式化
2021-12-08 04:23:17
![](https://img.aspxhome.com/file/2023/1/126091_0s.png)
Spring FreeMarker整合Struts2过程详解
2023-03-01 00:30:52
![](https://img.aspxhome.com/file/2023/9/62169_0s.jpg)
C# CultureInfo类案例详解
2023-04-20 05:00:45
![](https://img.aspxhome.com/file/2023/4/84444_0s.png)
Android开发之ViewPager实现滑动切换页面
2023-03-10 05:32:43
![](https://img.aspxhome.com/file/2023/8/130438_0s.jpg)
Android 如何使用短信链接打开APP
2022-01-09 02:45:25
![](https://img.aspxhome.com/file/2023/1/109221_0s.gif)
java中的常用集合类整理
2022-08-22 10:35:49
浅谈Java基础知识之BigDecimal
2021-09-06 16:49:27
![](https://img.aspxhome.com/file/2023/0/91530_0s.png)
Redis缓存策略超详细讲解
2023-11-08 06:20:10
![](https://img.aspxhome.com/file/2023/8/66078_0s.png)
android工程下不能运行java main程序的解决方法
2023-06-23 21:54:08
详解Java ScheduledThreadPoolExecutor的踩坑与解决方法
2022-11-25 17:34:17
![](https://img.aspxhome.com/file/2023/8/69668_0s.png)
C#通过抽象工厂模式造车
2021-07-05 04:20:55
基于JWT的spring boot权限验证技术实现教程
2022-07-20 01:48:58
Android开发之机顶盒上gridview和ScrollView的使用详解
2021-08-06 11:57:59
![](https://img.aspxhome.com/file/2023/7/94957_0s.jpg)
java 分转元与元转分实现操作
2023-05-13 16:47:22
亲手教你SpringBoot中的多数据源集成问题
2023-08-19 02:57:20
教你怎么用Java回溯算法解数独
2021-12-14 02:27:18
![](https://img.aspxhome.com/file/2023/4/111444_0s.png)
C# 利用PdfSharp生成Pdf文件的示例
2022-01-18 17:31:30
![](https://img.aspxhome.com/file/2023/0/119530_0s.png)
Java解析xml文件遇到特殊符号异常的情况(处理方案)
2023-10-23 17:31:48
SpringBoot+hutool实现图片验证码
2021-06-17 02:55:27
![](https://img.aspxhome.com/file/2023/7/80947_0s.png)