例題

假設存在如下表的需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區(qū)。如何選擇最少的廣播臺，讓所有的地區(qū)都可以接收到信號

代碼

public class Main {    public static void main(String[] args) {        /**         * 1.首先創(chuàng)建總的廣播臺和電視臺         */        //創(chuàng)建一個總的 能裝得下所有的廣播臺和電視臺        HashMap<String, HashSet<String>> broadcastsAndCitys = new HashMap<>();        //分別創(chuàng)建每一個廣播臺的覆蓋地區(qū)，然后加到總的集合中        HashSet<String> K1 = new HashSet<>();        K1.add("北京");        K1.add("上海");        K1.add("天津");        HashSet<String> K2 = new HashSet<>();        K2.add("廣州");        K2.add("北京");        K2.add("深圳");        HashSet<String> K3 = new HashSet<>();        K3.add("成都");        K3.add("上海");        K3.add("杭州");        HashSet<String> K4 = new HashSet<>();        K4.add("上海");        K4.add("天津");        HashSet<String> K5 = new HashSet<>();        K5.add("杭州");        K5.add("大連");        //然后將每一個覆蓋地區(qū)，以及廣播臺名，加入到總的集合中        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.進行貪心算法初始化操作，比如創(chuàng)建包含所有城市的集合，創(chuàng)建選擇的電臺的集合，創(chuàng)建一個 電臺與包含所有城市集合的交集所構成的集合         */        HashSet<String> allCitys = new HashSet<String>();        allCitys.add("北京");        allCitys.add("上海");        allCitys.add("天津");        allCitys.add("廣州");        allCitys.add("深圳");        allCitys.add("成都");        allCitys.add("杭州");        allCitys.add("大連");        HashSet<String> selectBroadcasts = new HashSet<>();        HashSet<String> tempKeys = new HashSet<>();        //創(chuàng)建指向最大城市數(shù)的key的引用，以及指向當前廣播臺的key        String maxKey = null;        /**         * 3.進行正兒八經(jīng)的貪心算法         */        while (allCitys.size() > 0){//只有長度不為0的時候才可以繼續(xù)，否則就是已經(jīng)選好了            //每一次while maxKey都要置空            maxKey = null;            //從broadcastsAndCitys中依次取出key，經(jīng)過循環(huán)賦值，得到maxKey            for (String key: broadcastsAndCitys.keySet()){                //因為tempKeys是針對每一個key的，所以每取得一個key就要清空一次                tempKeys.clear();                //給tempKeys賦值                HashSet<String> hashSet = broadcastsAndCitys.get(key);//！！！這里要重新創(chuàng)建一個集合去接收！！！                tempKeys.addAll(hashSet);                //tempKeys = broadcastsAndCitys.get(key);                //讓當前key和allCitys取交集，得其包括的城市數(shù)                tempKeys.retainAll(allCitys);                //給maxKey賦值                if (tempKeys.size() > 0 &&                        (maxKey == null || tempKeys.size() > broadcastsAndCitys.get(maxKey).size())){                    //不管怎么著，得有城市才能賦值                    //maxKey為空說明還沒賦過值呢，就直接賦值                    //tempKeys里面有東西，且東西的數(shù)目比當前maxKey指向的數(shù)目要多（沒有等于，如果相等，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方法

addAll是傳入一個List，將此List中的所有元素加入到當前List中

public classTest {    public static void main(String[] args) {        HashMap<String, HashSet<String>> broadcastsAndCitys = new HashMap<>();        HashSet<String> test1 = new HashSet<>();        test1.add("我");        test1.add("是");        test1.add("最");        test1.add("帥");        broadcastsAndCitys.put("k1",test1);        //test3是要被交集的        HashSet<String> test3 = new HashSet<>();        test3.add("我");        //test2是保存交集的        HashSet<String> 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指向了相同的位置，相同的內存空間        //如果重新創(chuàng)建一個HashSet來保存test1，然后再與test3取交集        HashSet<String> test4 = broadcastsAndCitys.get("k1");        test2.addAll(test4);//注意用addAll方法        test2.retainAll(test3);        //這里就是打印4 因為原來的沒變        System.out.println(broadcastsAndCitys.get("k1").size());        //原因：test4在與test2發(fā)生關系的時候，用了addAll方法，這個方法是把test4的所有元素的內容加進去        //此時test2相當于指向了另一塊內存空間，其內容與test4是一樣的    }}