程序员常用算法合集

一、二分查找算法

1)   前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式

2)    二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找

3)   二分查找法的运行时间为对数时间 O(㏒₂n)  ，即查找到需要的目标位置最多只需要㏒₂n 步，假设从[0,99]的队列(100 个数，即 n=100)中寻到目标数 30，则需要查找步数为㏒₂100 ,  即最多需要查找 7 次( 2^6 < 100 < 2^7)

代码实现：

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zhangzhixi
 * @date 2021/3/14 22:26
 */
public class Test01_二分查找算法 {
    public static void main(String[] args) {
        int[] arr = {3, 1, 6, 2, 5};
        // 二分查找要先将数组进行排序(冒泡排序)
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("排序后的数组：" + Arrays.toString(arr));

        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入一个数字,进行查找：");
        int i = scanner.nextInt();
        int binarySearch = binarySearch(arr, i);

        if (binarySearch != -1) {
            System.out.println("查找到的数据下标是：" + binarySearch);
        } else {
            System.out.println("您输入的数可能不存在在数组中~");
        }
    }

    /**
     * 查找数据，返回对应数据的下标
     * @param arr 要查找的数组
     * @param data 要查找的数据
     * @return
     */
    public static int binarySearch(int[] arr, int data) {
        if (arr.length <= 0) {
            return -1;
        }
        // 数组的开始下标
        int begin = 0;
        // 数组的结束下标
        int end = arr.length - 1;
        while (end > begin) {
            // 给数组的中间做一个标识
            int mid = (begin + end) / 2;
            if (arr[mid] > data) {
                end = mid - 1;
            } else if (arr[mid] < data) {
                begin = mid + 1;
            } else {
                // 找到就返回数据的下标
                return mid;
            }
        }
        return -1;
    }
}

二、分治算法(汉罗塔)

分治算法介绍

1)  分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

2) 分治算法可以求解的一些经典问题

• 二分搜索
• 大整数乘法
• 棋盘覆盖
• 合并排序
• 快速排序
• 线性时间选择
• 最接近点对问题
• 循环赛日程表
• 汉诺塔

分治算法的步骤

分治法在每一层递归上都有三个步骤：

• 1) 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
• 2) 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
• 3) 合并：将各个子问题的解合并为原问题的解。

 分治算法最佳实践-汉诺塔

汉诺塔的传说

　　汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

假如每秒钟一次，共需多长时间呢？移完这些金片需要 5845.54 亿年以上，太阳系的预期寿命据说也就是数百

亿年。真的过了 5845.54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

思路分析

1)  如果是有一个盘， A->C

如果我们有 n >= 2  情况，我们总是可以看做是两个盘 1.最下边的盘 2.  上面的盘

2)  先把 最上面的盘 A->B

3)  把最下边的盘 A->C

4)  把 B 塔的所有盘 从 B->C

代码实现：

/**
 * @author zhangzhixi
 * @date 2021/3/15 10:52
 */
public class Test02_分治算法_汉罗塔问题 {
    public static void main(String[] args) {
        hanrota(3, 'A', 'B', 'C');
        System.out.println("一共：" + count + "次");
    }

    /**
     * 返回汉罗塔的移动步骤
     *
     * @param num 总共有多少个汉罗塔片
     * @param a   第一个柱子
     * @param b   第二个柱子
     * @param c   第三个柱子
     */
    static int count = 0;

    public static void hanrota(int num, char a, char b, char c) {
        if (num == 1) {
            System.out.println("从" + a + " --> " + c + "柱");
        } else {
            // 1.先从A到B，借助C
            hanrota(num - 1, a, c, b);
            // 2.打印
            System.out.println("从" + a + " --> " + c + "柱");
            // 3.从B柱到C柱子，借助A
            hanrota(num - 1, b, a, c);
        }
        count++;
    }
}

三、动态规划问题

应用场景-背包问题

背包问题：有一个背包，容量为 4 磅 ， 现有如下物品

1)        要求达到的目标为装入的背包的总价值最大，并且重量不超出

2)        要求装入的物品不能重复

动态规划算法介绍

1)  动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

2)  动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

3)  与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )

4)  动态规划可以通过填表的方式来逐步推进，得到最优解.

动态规划算法最佳实践-背包问题

背包问题：有一个背包，容量为 4 磅 ， 现有如下物品

1)        要求达到的目标为装入的背包的总价值最大，并且重量不超出

2)        要求装入的物品不能重复

思路分析和图解

3)        背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分 01 背包和完全背包(完全背包指的是：每种物品都有无限件可用)

4)        这里的问题属于 01 背包，即每个物品最多放一个。而无限背包可以转化为 01 背包。

5)       

(1)   v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是 0

(2)  当 w[i]> j 时：v[i][j]=v[i-1][j]     // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略

(3) 当 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]的最大值当 j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} :

算法的主要思想，利用动态规划来解决。每次遍历到的第 i 个物品，根据 w[i]和 v[i]来确定是否需要将该物品放入背包中。即对于给定的 n 个物品，设 v[i]、w[i]分别为第 i 个物品的价值和重量，C 为背包的容量。再令 v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果：

6)  图解

代码实现：

package Demo13_常用算法合集;

/**
 * @author zhangzhixi
 * @date 2021/3/15 14:06
 */
public class Test03_动态规划算法_背包问题 {

    public static void main(String[] args) {
        int[] w = {1, 4, 3};//物品的重量
        int[] val = {1500, 3000, 2000}; //物品的价值 这里 val[i] 就是前面讲的 v[i]
        int m = 4; //背包的容量
        int n = val.length; //物品的个数
        //创建二维数组，
        //v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值
        int[][] v = new int[n + 1][m + 1];
        //为了记录放入商品的情况，我们定一个二维数组i
        int[][] path = new int[n + 1][m + 1];

        //初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是 0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0; //将第一列设置为 0
        }
        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0; //将第一行设置 0
        }

        //根据前面得到公式来动态规划处理
        for (int i = 1; i < v.length; i++) { //不处理第一行 i 是从 1 开始的
            for (int j = 1; j < v[0].length; j++) {//不处理第一列, j 是从 1 开始的
                //公式
                if (w[i - 1] > j) { //  因为我们程序 i  是从 1 开始的，因此原来公式中的 w[i] 修改成 w[i-1]
                    v[i][j]=v[i-1][j];
                } else {
                    //因为我们的 i  从 1 开始的， 因此公式需要调整成
                    //v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
                    //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    //为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用 if-else 来体
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - 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];

                    }
                }
            }
        }
        //输出一下 v  看看目前的情况
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("============================");
        //输出最后我们是放入的哪些商品
        //遍历 path,  这样输出会把所有的放入情况都得到,  其实我们只需要最后的放入
        //动脑筋
        int i = path.length - 1; //行的最大下标
        int j = path[0].length - 1;    //列的最大下标
        while (i > 0 && j > 0) { //从 path 的最后开始找
            if (path[i][j] == 1) {
                System.out.printf("第%d 个商品放入到背包
", i);
                j -= w[i - 1]; //w[i-1]
            }
            i--;
        }
    }
}

四、KMP算法 

应用场景-字符串匹配问题

• 字符串匹配问题：：

1)  有一个字符串 str1= "张志喜喜欢跑步"，和一个子串 str2="喜欢"

2)  现在要判断 str1  是否含有 str2,  如果存在，就返回第一次出现的位置,  如果没有，则返回-1

暴力匹配

如果用暴力匹配的思路，并假设现在 str1 匹配到 i 位置，子串 str2 匹配到 j  位置，则有:

• 1)   如果当前字符匹配成功（即 str1[i] == str2[j]），则 i++，j++，继续匹配下一个字符
• 2)   如果失配（即 str1[i]! = str2[j]），令 i = i - (j - 1)，j = 0。相当于每次匹配失败时，i  回溯，j  被置为 0。
• 3)   用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。(不可行!)

 代码实现：

package Demo13_常用算法合集;

/**
 * @author zhangzhixi
 * @date 2021/3/15 15:18
 */
public class Test04_KMP算法_暴力匹配 {
    public static void main(String[] args) {
        String str1 = "张志喜喜欢跑步";
        String str2 = "喜欢";
        System.out.println(violentMatch(str1, str2));

    }

    /**
     * 判断子字符串在字符串中第一次出现的下标位置
     *
     * @param str1
     * @param str2
     * @return
     */
    public static int violentMatch(String str1, String str2) {
        // 将字符串转为字符数组
        char[] c1 = str1.toCharArray();
        char[] c2 = str2.toCharArray();

        // 字符数组的长度
        int c1Len = c1.length;
        int c2Len = c2.length;

        // 下标,i索引下标指向c1,j索引下标指向c2
        int i = 0;
        int j = 0;

        // 保证匹配的时候不越界
        while (i < c1Len && j < c2Len) {
            // 匹配成功
            if (c1[i] == c2[j]) {
                // 继续匹配下一个字符
                i++;
                j++;
            } else {
                // 没有匹配成功,让下标后移，继续与子字符串进行匹配
                i = i - (j - 1);
                j = 0;
            }
        }
        // 判断是否匹配成功,子字符串的下标跟子字符串的长度一样长，就说明匹配成功了
        if (j == c2Len) {
            return i - j;
        } else {
            return -1;
        }
    }
}

KMP 算法介绍

1)        KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法

2)        Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法.

3)        KMP 方法算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间

4)        参考资料：https://blog.csdn.net/v_july_v/article/details/7041827

KMP 算法最佳应用-字符串匹配问题

• 字符串匹配问题：：

1)  有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串 str2="ABCDABD"

2)  现在要判断 str1  是否含有 str2,  如果存在，就返回第一次出现的位置,  如果没有，则返回-1

3)  要求：使用 KMP 算法完成判断，不能使用简单的暴力匹配算法.

思路分析：

　　举例来说，有一个字符串 Str1 = “BBC ABCDAB ABCDABCDABDE”，判断，里面是否包含另一个字符串 Str2 =“ABCDABD”？

1. 首先，用 Str1 的第一个字符和 Str2 的第一个字符去比较，不符合，关键词向后移动一位

2.重复第一步，还是不符合，再后移

 3.一直重复，直到 Str1 有一个字符与 Str2 的第一个字符符合为止

4.接着比较字符串和搜索词的下一个字符，还是符合。

5.遇到 Str1 有一个字符与 Str2 对应的字符不符合

 

6.这时候，想到的是继续遍历 Str1 的下一个字符，重复第 1 步。

(其实是很不明智的，因为此时 BCD 已经比较过了， 没有必要再做重复的工作，一个基本事实是，当空格与 D 不匹配时，你其实知道前面六个字符是”ABCDAB”。

KMP 算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。)

7.怎么做到把刚刚重复的步骤省略掉？可以对 Str2 计算出一张《部分匹配表》,看第13步骤的介绍

8. 已知空格与 D 不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符 B 对应的”部分匹配值”为 2，因此按照下面的公式算出向后移动的位数：

移动位数 = 已匹配的字符数 - 对应的部分匹配值因为 6 - 2 等于 4，所以将搜索词向后移动 4 位。

9.因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为 2（”AB”），对应的”部分匹配值” 为 0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位。

10.因为空格与 A 不匹配，继续后移一位

11. 逐位比较，直到发现 C 与 D 不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动 4 位

12. 逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配）， 移动位数 = 7 - 0，再将搜索词向后移动 7 位，这里就不再重复了。

 

13. 介绍《部分匹配表》怎么产生的先介绍前缀，后缀是什么

部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

－”A”的前缀和后缀都为空集，共有元素的长度为 0；

－”AB”的前缀为[A]，后缀为[B]，共有元素的长度为 0；

－”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度 0；

－”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为 0；

－”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为 1；

－”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为 2；

－”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD,D]，共有元素的长度为 0。

---

 14.”部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是 2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动 4 位（字符串长度- 部分匹配值），就可以来到第二个”AB”的位置。

 

 代码实现：

package Demo13_常用算法合集;

import java.util.Arrays;

/**
 * @author zhangzhixi
 * @date 2021/3/15 14:49
 */
public class Test04_KMP算法 {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        //String str2 = "BBC";

        //[0, 1, 2, 0]
        int[] next = kmpNext("ABCDABD");
        System.out.println("next=" + Arrays.toString(next));
        int index = kmpSearch(str1, str2, next);
        System.out.println("index=" + index); // 15 了
    }

    /**
     * 写出我们的 kmp 搜索算法
     *
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表,  是子串对应的部分匹配表
     * @return 如果是-1 就是没有匹配到，否则返回第一个匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {

        //遍历
        for (int i = 0, j = 0; i < str1.length(); i++) {
            //需要处理 str1.charAt(i) ！= str2.charAt(j),  去调整 j 的大小
            //KMP 算法核心点, 可以验证...
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }
            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            //找到了 // j = 3 i
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    //获取到一个字符串(子串) 的部分匹配值表
    public static int[] kmpNext(String dest) {
        //创建一个 next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        //如果字符串是长度为 1 部分匹配值就是 0
        next[0] = 0;
        for (int i = 1, j = 0; i < dest.length(); i++) {
            //当 dest.charAt(i) != dest.charAt(j) ，我们需要从 next[j-1]获取新的 j
            //直到我们发现 有    dest.charAt(i) == dest.charAt(j)成立才退出
            //这时 kmp 算法的核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            //当 dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

五、贪心算法

应用场景-集合覆盖问题

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

贪心算法介绍

1) 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法

2) 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

贪心算法最佳应用-集合覆盖

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

2）思路分析:

• 如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有 n 个广播台，则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算 10 个子集， 如图:

 

3） 实现步骤：

1) 目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:

2)  遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）

3)  将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。重复第 1 步直到覆盖了全部的地区

代码实现：

package Demo13_常用算法合集;

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

/**
 * @author zhangzhixi
 * @date 2021/3/16 21:45
 */
public class Test05_贪心算法 {
    public static void main(String[] args) {
        // 1、创建广播台
        Map<String, HashSet<String>> broadCast = new HashMap<>(16);
        // 添加广播所覆盖的地区
        HashSet<String> HashSet1 = new HashSet<>();
        HashSet1.add("北京");
        HashSet1.add("上海");
        HashSet1.add("天津");
        HashSet<String> HashSet2 = new HashSet<>();
        HashSet2.add("广州");
        HashSet2.add("北京");
        HashSet2.add("深圳");
        HashSet<String> HashSet3 = new HashSet<>();
        HashSet3.add("成都");
        HashSet3.add("上海");
        HashSet3.add("杭州");
        HashSet<String> HashSet4 = new HashSet<>();
        HashSet4.add("上海");
        HashSet4.add("天津");
        HashSet<String> HashSet5 = new HashSet<>();
        HashSet5.add("杭州");
        HashSet5.add("大连");
        // 2、加入到map集合中
        broadCast.put("k1", HashSet1);
        broadCast.put("k2", HashSet2);
        broadCast.put("k3", HashSet3);
        broadCast.put("k4", HashSet4);
        broadCast.put("k5", HashSet5);

        ///3、allAreas表示存放所有的地区
        HashSet<String> allAreas = new HashSet<>();
        // 添加所有的地区（不重复）
        for (Map.Entry<String, HashSet<String>> entry : broadCast.entrySet()) {
            // 将指定集合中的所有元素添加到此集合中
            //entry.getValue()获取的是每一个hashSet、
            allAreas.addAll(entry.getValue());
        }

        // 4、创建 ArrayList,  存放选择的电台集合
        ArrayList<String> selects = new ArrayList<String>();
        // 5、定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        HashSet<String> tempSet = new HashSet<String>();
        //定义给 maxKey，保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的 key
        //如果 maxKey 不为 null , 则会加入到 selects
        String maxKey = null;
        // 如果 allAreas  不为 0,  则表示还没有覆盖到所有的地区
        while (allAreas.size() != 0) {
            //每进行一次 while,需要
            maxKey = null;
            //遍历 broadcasts, 取出对应 key
            for (String key : broadCast.keySet()) {
                //每进行一次 for
                tempSet.clear();
                //当前这个 key 能够覆盖的地区
                HashSet<String> areas = broadCast.get(key);
                tempSet.addAll(areas);
                //求出tempSet 和allAreas 集合的交集, 交集会赋给 tempSet
                tempSet.retainAll(allAreas);
                //如果当前这个集合包含的未覆盖地区的数量，比 maxKey 指向的集合地区还多就需要重置 maxKey
                // tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
                if (tempSet.size() > 0 &&
                        (maxKey == null || tempSet.size() > broadCast.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            //maxKey != null, 就应该将 maxKey 加入 selects
            if (maxKey != null) {
                selects.add(maxKey);
                //将 maxKey 指向的广播电台覆盖的地区，从 allAreas 去掉
                allAreas.removeAll(broadCast.get(maxKey));
            }
        }
        System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]
    }

}