高龄白菜java学习第105天（java数据结构和算法（23））

kmp算法的学习主要参考了sofu6博主的帖子，链接如下： KMP算法详解

思路分析

1、取一轮中包含覆盖地区最多的key
2、在下一轮把已覆盖的地区从地区集合中去掉，直到地区集合为空
代码实现：

package Algorithm.GreedyAlgorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Greedy {
    public static void main(String[] args) {
        //创建广播电台
        HashMap> broadcasts = new HashMap<>();
        //添加每个广播电台可覆盖的地区的集合
        HashSet s1 = new HashSet<>();
        HashSet s2 = new HashSet<>();
        HashSet s3 = new HashSet<>();
        HashSet s4 = new HashSet<>();
        HashSet s5 = new HashSet<>();

        s1.add("北京");
        s1.add("上海");
        s1.add("天津");

        s2.add("广州");
        s2.add("北京");
        s2.add("深圳");

        s3.add("成都");
        s3.add("上海");
        s3.add("杭州");

        s4.add("上海");
        s4.add("天津");

        s5.add("杭州");
        s5.add("大连");

        broadcasts.put("K1", s1);
        broadcasts.put("K2", s2);
        broadcasts.put("K3", s3);
        broadcasts.put("K4", s4);
        broadcasts.put("K5", s5);

        //创建全地区集合
        HashSet allArea = new HashSet<>();

        for (Map.Entry> entry : broadcasts.entrySet()) {
            allArea.addAll(entry.getValue());
        }
        System.out.println(allArea.toString());

        //创建存放我们选择的电台集合
        ArrayList selects = new ArrayList<>();

        //定义一个临时set，用来存放遍历过程中电台能够覆盖的城市范围和当前还未覆盖的城市集合这两者的交集
        HashSet tempSet = new HashSet<>();

        //定义一个maxkey，保存在一次遍历中能够覆盖最大范围的电台对应的key
        String maxkey;
        while (broadcasts.size() > 0) {
            maxkey=null;
            //取到当前key对应的覆盖地区
            for (String key : broadcasts.keySet()) {
                //将上一轮的tempSet清空
                tempSet.clear();
                HashSet areas = broadcasts.get(key);
                tempSet.addAll(areas);
                //求出tempSet和allArea的交集
                tempSet.retainAll(allArea);//两者取交集并将结果赋值给调用方法的集合
                //如果当前集合包含的为覆盖地区的数量比maxkey对应的还多,此处的判断条件体现出贪心算法的特性
                broadcasts.get(maxkey).retainAll(allArea);
                if ((tempSet.size() > 0) && ((maxkey == null) || (tempSet.size() > broadcasts.get(maxkey).size()))) {
                    maxkey = key;
                }
            }
            //
            if (maxkey!=null){
                selects.add(maxkey);
                //将maxkey对应的覆盖地区从allarea里面清除掉
                allArea.removeAll(broadcasts.get(maxkey));
            }
        }
    }
}