重学数据结构与算法（Java）|【程序员必会十大算法】之贪心算法 java|算法

例题假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号

文章图片

代码

public class Main {public static void main(String[] args) {/** * 1.首先创建总的广播台和电视台 */ //创建一个总的能装得下所有的广播台和电视台 HashMap> broadcastsAndCitys = new HashMap<>(); //分别创建每一个广播台的覆盖地区，然后加到总的集合中 HashSet K1 = new HashSet<>(); K1.add("北京"); K1.add("上海"); K1.add("天津"); HashSet K2 = new HashSet<>(); K2.add("广州"); K2.add("北京"); K2.add("深圳"); HashSet K3 = new HashSet<>(); K3.add("成都"); K3.add("上海"); K3.add("杭州"); HashSet K4 = new HashSet<>(); K4.add("上海"); K4.add("天津"); HashSet K5 = new HashSet<>(); K5.add("杭州"); K5.add("大连"); //然后将每一个覆盖地区，以及广播台名，加入到总的集合中 broadcastsAndCitys.put("k1",K1); broadcastsAndCitys.put("k2",K2); broadcastsAndCitys.put("k3",K3); broadcastsAndCitys.put("k4",K4); broadcastsAndCitys.put("k5",K5); System.out.println(broadcastsAndCitys); //{k1=[上海, 天津, 北京], k2=[广州, 北京, 深圳], k3=[成都, 上海, 杭州], k4=[上海, 天津], k5=[大连, 杭州]}/** * 2.进行贪心算法初始化操作，比如创建包含所有城市的集合，创建选择的电台的集合，创建一个电台与包含所有城市集合的交集所构成的集合 */ HashSet allCitys = new HashSet(); allCitys.add("北京"); allCitys.add("上海"); allCitys.add("天津"); allCitys.add("广州"); allCitys.add("深圳"); allCitys.add("成都"); allCitys.add("杭州"); allCitys.add("大连"); HashSet selectBroadcasts = new HashSet<>(); HashSet tempKeys = new HashSet<>(); //创建指向最大城市数的key的引用，以及指向当前广播台的key String maxKey = null; /** * 3.进行正儿八经的贪心算法 */ while (allCitys.size() > 0){ //只有长度不为0的时候才可以继续，否则就是已经选好了 //每一次while maxKey都要置空 maxKey = null; //从broadcastsAndCitys中依次取出key，经过循环赋值，得到maxKey for (String key: broadcastsAndCitys.keySet()){//因为tempKeys是针对每一个key的，所以每取得一个key就要清空一次 tempKeys.clear(); //给tempKeys赋值 HashSet hashSet = broadcastsAndCitys.get(key); //！！！这里要重新创建一个集合去接收！！！ tempKeys.addAll(hashSet); //tempKeys = broadcastsAndCitys.get(key); //让当前key和allCitys取交集，得其包括的城市数 tempKeys.retainAll(allCitys); //给maxKey赋值 if (tempKeys.size() > 0 && (maxKey == null || tempKeys.size() > broadcastsAndCitys.get(maxKey).size())){//不管怎么着，得有城市才能赋值 //maxKey为空说明还没赋过值呢，就直接赋值 //tempKeys里面有东西，且东西的数目比当前maxKey指向的数目要多（没有等于，如果相等，maxKey就指向第一个） maxKey = key; } }if (maxKey != null){//把选出来的maxKey加进去selectBroadcasts selectBroadcasts.add(maxKey); //把选出来的maxKey覆盖的城市从allCitys中去掉 allCitys.removeAll(broadcastsAndCitys.get(maxKey)); }else {//如果比较下来都没有一个合适的maxKey，而且allCitys.size()还可能>0，那么很遗憾，可能只能找到最接近需求的解 break; } }System.out.println(selectBroadcasts); } }

结果

{ k1=[上海, 天津, 北京], k2=[广州, 北京, 深圳], k3=[成都, 上海, 杭州], k4=[上海, 天津], k5=[大连, 杭州]} [k1, k2, k3, k5]

意外收获：addAll方法 【重学数据结构与算法（Java）|【程序员必会十大算法】之贪心算法】addAll是传入一个List，将此List中的所有元素加入到当前List中

public class Test {public static void main(String[] args) {HashMap> broadcastsAndCitys = new HashMap<>(); HashSet test1 = new HashSet<>(); test1.add("我"); test1.add("是"); test1.add("最"); test1.add("帅"); broadcastsAndCitys.put("k1",test1); //test3是要被交集的 HashSet test3 = new HashSet<>(); test3.add("我"); //test2是保存交集的 HashSet test2 = new HashSet<>(); //test2把test1拿出来，与test3取交集，赋给test2 test2 = broadcastsAndCitys.get("k1"); test2.retainAll(test3); //结果test1变成了test2，就是取完交集的那个结果，这里就是打印1 因为只有一个交集 System.out.println(broadcastsAndCitys.get("k1").size()); //原因：test2把test1拿出来，意味着test2和test1指向了相同的位置，相同的内存空间//如果重新创建一个HashSet来保存test1，然后再与test3取交集 HashSet test4 = broadcastsAndCitys.get("k1"); test2.addAll(test4); //注意用addAll方法 test2.retainAll(test3); //这里就是打印4 因为原来的没变 System.out.println(broadcastsAndCitys.get("k1").size()); //原因：test4在与test2发生关系的时候，用了addAll方法，这个方法是把test4的所有元素的内容加进去 //此时test2相当于指向了另一块内存空间，其内容与test4是一样的 } }