【算法&数据结构体系篇class13、14】：贪心算法思想

清疚 2024-03-26 18:06 113阅读 0赞

### 一、贪心算法概念 ###

> **贪心算法概念：**  
> 1）最自然智慧的算法  
>   
> 2）用一种局部最功利的标准，总是做出在当前看来是最好的选择  
>   
> 3）难点在于证明局部最功利的标准可以得到全局最优解  
>   
> 4）对于贪心算法的学习主要以增加阅历和经验为主

### 二、给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果 ###

package class13;
    
    import java.util.Arrays;
    import java.util.TreeSet;
    
    /**
     * 给定一个由字符串组成的数组strs，
     * 必须把所有的字符串拼接起来，
     * 返回所有可能的拼接结果中，字典序最小的结果
     *
     * 贪心算法
     * 1）最自然智慧的算法
     *
     * 2）用一种局部最功利的标准，总是做出在当前看来是最好的选择
     *
     * 3）难点在于证明局部最功利的标准可以得到全局最优解
     *
     * 4）对于贪心算法的学习主要以增加阅历和经验为主
     *
     * 贪心算法求解的标准过程
     * 1，分析业务
     *
     * 2，根据业务逻辑找到不同的贪心策略
     *
     * 3，对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性
     *
     * 这往往是特别困难的，要求数学能力很高且不具有统一的技巧性
     *
     * 贪心算法的解题套路
     * 1，实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
     *
     * 2，脑补出贪心策略A、贪心策略B、贪心策略C...
     *
     * 3，用解法X和对数器，用实验的方式得知哪个贪心策略正确
     *
     * 4，不要去纠结贪心策略的证明
     */
    
    
    
    public class LowsetLexicography {
    
        //暴力解法   递归形式 将每个字符作为首部，依次拼接全部情况的结果集，存放到treeset有序集合，取出首元素就是最小的字典序排序拼接方式
        public static String lowestString1(String[] strs){
            if(strs == null || strs.length == 0){
                //null 或者长度0空数组则直接返回空字符串
                return "";
            }
            //有序表保存全部排序情况，返回首元素就是最小排序
            TreeSet<String> ans = process(strs);
            return ans.size() == 0 ? "":ans.first();
        }
        //递归思路，从左到右依次取字符串，然后递归 排除当前字符串的下个字符串数组，将其追加在当前字符串后
        public static TreeSet<String> process(String[] strs){
            //定义一个有序表结构保存结果集，用于返回
            TreeSet<String> ans = new TreeSet<>();
            //当字符串减少到0的时候，就直接返回空字符串
            if(strs.length == 0){
                //注意要加空字符，返回给上层调用才会有空异常
                ans.add("");
                return ans;
            }
            //依次遍历每个字符串
            for(int i = 0; i < strs.length; i++){
                //取当前遍历到的字符串拼接在首部
                String first = strs[i];
                //排除当前字符串 再将数组进行下层递归，直到空的时候，开始向上返回
                TreeSet<String> nexts = process(removeIndexString(strs,i));
                //向上依次拼接给当前节点字符后面
                for(String next : nexts){
                    ans.add(first + next);
                }
            }
            //递归完成，全部排序返回，最后主程序取有序表的首元素，就是最小字典序
            return ans;
        }
    
        // {"abc", "cks", "bct"}
        // 0 1 2
        // removeIndexString(arr , 1) -> {"abc", "bct"}
        //每次移除当前节点元素，返回剩下的字符串数组集
        public static String[] removeIndexString(String[] strs, int index){
            //定义新数组集合以及索引
            String[] ans = new String[strs.length-1];
            int ans_index = 0;
            for(int i = 0;i < strs.length;i++){
                if(i != index){
                    //遍历原数组，排除index索引，不等于的则赋值到新数组
                    ans[ans_index++] = strs[i];
                }
            }
            return ans;
        }
    
    
        //贪心思想
        //字典序排序要最小，已知字典序的排序 "a" < "b" , "b" < "c" 存在传递性规律 所以"a" < "c"
        //而字符拼接后也一样 排序是具有传递性的：
        //如果字符串a拼接字符串b < 字符串b拼接字符串a  那么就返回 前者，即a放b的前面  ；否则返回后者
        //按照这个排序定义比较器排序后，就按序拼接就是最小的：
        //因为假设每个字符串交换到前面，它必定是大于未交换前的字符串拼接的
        public static String lowestString2(String[] strs){
            if(strs == null || strs.length == 0){
                return "";
            }
            //lambda表达式自定义比较器 参数 a  b, 如果字符串数组 字符串a+b < b+a  compareTo返回负数，a排前面 返回正数 b排前面
            Arrays.sort(strs,(a,b)->
                (a+b).compareTo(b+a)
            );
            StringBuilder ans = new StringBuilder();
            for(String str:strs){
                ans.append(str);
            }
            return ans.toString();
        }
    
    
        // for test
        public static String generateRandomString(int strLen) {
            char[] ans = new char[(int) (Math.random() * strLen) + 1];
            for (int i = 0; i < ans.length; i++) {
                int value = (int) (Math.random() * 5);
                ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
            }
            return String.valueOf(ans);
        }
    
        // for test
        public static String[] generateRandomStringArray(int arrLen, int strLen) {
            String[] ans = new String[(int) (Math.random() * arrLen) + 1];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = generateRandomString(strLen);
            }
            return ans;
        }
    
        // for test
        public static String[] copyStringArray(String[] arr) {
            String[] ans = new String[arr.length];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = String.valueOf(arr[i]);
            }
            return ans;
        }
    
        public static void main(String[] args) {
            int arrLen = 6;
            int strLen = 5;
            int testTimes = 10000;
            System.out.println("test begin");
            for (int i = 0; i < testTimes; i++) {
                String[] arr1 = generateRandomStringArray(arrLen, strLen);
                String[] arr2 = copyStringArray(arr1);
                if (!lowestString1(arr1).equals(lowestString2(arr2))) {
                    for (String str : arr1) {
                        System.out.print(str + ",");
                    }
                    System.out.println();
                    System.out.println("Oops!");
                }
            }
            System.out.println("finish!");
        }
    }

### 三、贪心算法求解的标准过程 ###

> 1，分析业务  
>   
> 2，根据业务逻辑找到不同的贪心策略  
>   
> 3，对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性  
>   
> 这往往是特别困难的，要求数学能力很高且不具有统一的技巧性

### 四、贪心算法的套路 ###

> 1，实现一个不依靠贪心策略的解法X，可以用最暴力的尝试  
>   
> 2，脑补出贪心策略A、贪心策略B、贪心策略C...  
>   
> 3，用解法X和对数器，用实验的方式得知哪个贪心策略正确  
>   
> 4，不要去纠结贪心策略的证明

### 五、给定一个字符串str，只由‘X’和‘.’两种字符构成。X’表示墙，不能放灯，也不需要点亮‘.’表示居民点，可以放灯，需要点亮，如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮，返回如果点亮str中所有需要点亮的位置，至少需要几盏灯 ###

package class14;
    
    import java.util.HashSet;
    
    /**
     * 给定一个字符串str，只由‘X’和‘.’两种字符构成。
     * ‘X’表示墙，不能放灯，也不需要点亮
     * ‘.’表示居民点，可以放灯，需要点亮
     * 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮
     * 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯
     *
     * 贪心思想：根据题意 .是要被照亮。 而灯可以照亮三个. 求至少，那么就根据这个最大照亮三个点的情况来贪心 一个灯贪心照亮三个.
     */
    public class Light {
        public static int minLight1(String road) {
            if (road == null || road.length() == 0) {
                return 0;
            }
            return process(road.toCharArray(), 0, new HashSet<>());
        }
    
        // str[index....]位置，自由选择放灯还是不放灯
        // str[0..index-1]位置呢？已经做完决定了，那些放了灯的位置，存在lights里
        // 要求选出能照亮所有.的方案，并且在这些有效的方案中，返回最少需要几个灯
        public static int process(char[] str, int index, HashSet<Integer> lights) {
            if (index == str.length) { // 结束的时候
                for (int i = 0; i < str.length; i++) {
                    if (str[i] != 'X') { // 当前位置是点的话
                        if (!lights.contains(i - 1) && !lights.contains(i) && !lights.contains(i + 1)) {
                            return Integer.MAX_VALUE;
                        }
                    }
                }
                return lights.size();
            } else { // str还没结束
                // i X .
                int no = process(str, index + 1, lights);
                int yes = Integer.MAX_VALUE;
                if (str[index] == '.') {
                    lights.add(index);
                    yes = process(str, index + 1, lights);
                    lights.remove(index);
                }
                return Math.min(no, yes);
            }
        }
    
        //贪心思想
        public static int minLight2(String road) {
            //转换成字符数组 定义索引 与结果值
            char[] chars = road.toCharArray();
            int i = 0;
            int ans = 0;
            //遍历字符数组
            while(i < chars.length){
                //遇到X,不需要照亮，索引往下
                if(chars[i] == 'X'){
                    i++;
                }else{
                    //遇到. 进来先灯+1
                    ans++;
                    //如果i+1 是超过边界 也就是i 是最后一个索引的时候 就可以直接退出了。即使当前i是. 需要照亮，我们已经在前面先+1灯了
                    if(i + 1 == chars.length){
                        break;
                    }else {
                    // 还没到最后边界 那么分析几种情况：
                    //1. 下个字符 i+1 如果是X 那么灯+1，并且索引跳过X，来到i+2
                    //2. 下个字符 i+1 如果是. 那么灯也要+1  这次索引来到i+3 因为不管i+3 是X还是. 都不需要去判断，因为灯可以照亮3个.
                    //这里不管那么种情况，都是需要+1灯，所以统一放前面+1 这么负责索引的走向
                    if(chars[i+1] == 'X'){
                        i = i+2;
                    }else {
                        i = i+3;
                    }
                    }
                }
            }
            //最后返回ans
            return ans;
        }
    
        // 更简洁的解法
        // 两个X之间，数一下.的数量，然后除以3，向上取整
        // 把灯数累加
        public static int minLight3(String road) {
            char[] str = road.toCharArray();
            int cur = 0;
            int light = 0;
            for (char c : str) {
                if (c == 'X') {
                    light += (cur + 2) / 3;
                    cur = 0;
                } else {
                    cur++;
                }
            }
            light += (cur + 2) / 3;
            return light;
        }
    
        // for test
        public static String randomString(int len) {
            char[] res = new char[(int) (Math.random() * len) + 1];
            for (int i = 0; i < res.length; i++) {
                res[i] = Math.random() < 0.5 ? 'X' : '.';
            }
            return String.valueOf(res);
        }
    
        public static void main(String[] args) {
            int len = 20;
            int testTime = 100000;
            for (int i = 0; i < testTime; i++) {
                String test = randomString(len);
                int ans1 = minLight1(test);
                int ans2 = minLight2(test);
                int ans3 = minLight3(test);
                if (ans1 != ans2 || ans1 != ans3) {
                    System.out.println("oops!");
                }
            }
            System.out.println("finish!");
        }
    }

### 六、切金条 ###

> 一块金条切成两半，是需要花费和长度数值一样的铜板的。  
> 比如长度为20的金条，不管怎么切，都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板?  
>   
> 例如,给定数组\{10,20,30\}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。  
>   
> 如果先把长度60的金条分成10和50，花费60;再把长度50的金条分成20和30，花费50;一共花费110铜板。  
> 但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20，花费30;一共花费90铜板。  
>   
> 输入一个数组，返回分割的最小代价。

package class14;
    
    import java.util.PriorityQueue;
    
    /**
     * 一块金条切成两半，是需要花费和长度数值一样的铜板的。
     * 比如长度为20的金条，不管怎么切，都要花费20个铜板。 一群人想整分整块金条，怎么分最省铜板?
     *
     * 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。
     *
     * 如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50;一共花费110铜板。
     * 但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20， 花费30;一共花费90铜板。
     * 输入一个数组，返回分割的最小代价。
     */
    
    public class LessMoneySplitGold {
    
        // 纯暴力！
        public static int lessMoney1(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            return process(arr, 0);
        }
    
        // 等待合并的数都在arr里，pre之前的合并行为产生了多少总代价
        // arr中只剩一个数字的时候，停止合并，返回最小的总代价
        public static int process(int[] arr, int pre) {
            if (arr.length == 1) {
                return pre;
            }
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
                }
            }
            return ans;
        }
    
        public static int[] copyAndMergeTwo(int[] arr, int i, int j) {
            int[] ans = new int[arr.length - 1];
            int ansi = 0;
            for (int arri = 0; arri < arr.length; arri++) {
                if (arri != i && arri != j) {
                    ans[ansi++] = arr[arri];
                }
            }
            ans[ansi] = arr[i] + arr[j];
            return ans;
        }
    
        //贪心思想：将每个数放到小根堆，依次取堆最小的两段合并，合并值就为当前的代价，再将合并的值添加回堆中进行上一次的合并
        //这个思路是反向的做法，相当于已经切好的段，从最下面开始两两合并直到最后我们堆合并成只有一个数，也就是整个数组的和时就
        //得到了这个最小代价
        public static int lessMoney2(int[] arr){
            //定义小根堆，把数组存放进去
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            for(int num:arr){
                heap.add(num);
            }
            //定义分割总代价值与
            int sum = 0;
            //遍历每段数值，直到合并到只剩一个 也就是总和就退出
            while(heap.size() > 1){
                //合并最小两段，并且这两段的代价按照题意就是两端和，累加到sum
                int merge = heap.poll() + heap.poll();
                sum += merge;
                //然后需要把这次合并的段加回堆中，继续给上层合并
                heap.add(merge);
            }
            //最后返回sum就能得到最小代价分割值
            return sum;
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) (Math.random() * (maxValue + 1));
            }
            return arr;
        }
    
        public static void main(String[] args) {
            int testTime = 100000;
            int maxSize = 6;
            int maxValue = 1000;
            for (int i = 0; i < testTime; i++) {
                int[] arr = generateRandomArray(maxSize, maxValue);
                if (lessMoney1(arr) != lessMoney2(arr)) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("finish!");
        }
    
    }

### 七、一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回最多的宣讲场次。 ###

package class14;
    
    import java.util.Arrays;
    import java.util.Comparator;
    
    /**
     * 一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
     * 给你每一个项目开始的时间和结束的时间
     * 你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。
     * 返回最多的宣讲场次。
     *
     * [1,3],[2,5],[3,6]比如三个会议 起始点  同步安排会议最多场次就是安排第一和第三场
     * 两者时间不交集
     */
    
    public class BestArrange {
    
        //会议类结构
        public static class Program{
            public int start;
            public int end;
            public Program(int s,int e){
                start = s;
                end = e;
            }
        }
    
    
        //贪心思想  将会议按照会议结束时间升序排序 早结束的排前面，然后就依次开始从头遍历匹配，
        //当前会议如果开始时间大于等于我们当前的时间，一开始时间初始值0， 那么就安排这个会议，并且
        //当前时间来到这个会议的结束时间，再往下个会议看，添加下个会议开始时间是大于等于当前时间的，
        //直到结束 就可以得到安排最多场次会议
        public static int bestArrange2(Program[] programs){
            //按照会议的结束时间 升序排序，先结束的会议放到数组前面
            Arrays.sort(programs, (o1, o2) -> o1.end - o2.end);
            //定义能安排多少场次会议, 当前时间节点 初始为0
            int ans = 0;
            int timeNow = 0;
            for(Program pro:programs){
                //遍历排好序的会议，如果当前会议开始时间大于等于 当前时间，那么就可以安排会议，并将当前时间赋值为该会议室的结束时间
                if(pro.start >= timeNow){
                    ans++;
                    timeNow = pro.end;
                }
            }
            return ans;
        }
    
        // 暴力！所有情况都尝试！
        public static int bestArrange1(Program[] programs) {
            if (programs == null || programs.length == 0) {
                return 0;
            }
            return process(programs, 0, 0);
        }
    
        // 还剩下的会议都放在programs里
        // done之前已经安排了多少会议的数量
        // timeLine目前来到的时间点是什么
    
        // 目前来到timeLine的时间点，已经安排了done多的会议，剩下的会议programs可以自由安排
        // 返回能安排的最多会议数量
        public static int process(Program[] programs, int done, int timeLine) {
            if (programs.length == 0) {
                return done;
            }
            // 还剩下会议
            int max = done;
            // 当前安排的会议是什么会，每一个都枚举
            for (int i = 0; i < programs.length; i++) {
                if (programs[i].start >= timeLine) {
                    Program[] next = copyButExcept(programs, i);
                    max = Math.max(max, process(next, done + 1, programs[i].end));
                }
            }
            return max;
        }
        public static Program[] copyButExcept(Program[] programs, int i) {
            Program[] ans = new Program[programs.length - 1];
            int index = 0;
            for (int k = 0; k < programs.length; k++) {
                if (k != i) {
                    ans[index++] = programs[k];
                }
            }
            return ans;
        }
    
        // for test
        public static Program[] generatePrograms(int programSize, int timeMax) {
            Program[] ans = new Program[(int) (Math.random() * (programSize + 1))];
            for (int i = 0; i < ans.length; i++) {
                int r1 = (int) (Math.random() * (timeMax + 1));
                int r2 = (int) (Math.random() * (timeMax + 1));
                if (r1 == r2) {
                    ans[i] = new Program(r1, r1 + 1);
                } else {
                    ans[i] = new Program(Math.min(r1, r2), Math.max(r1, r2));
                }
            }
            return ans;
        }
    
        public static void main(String[] args) {
            int programSize = 12;
            int timeMax = 20;
            int timeTimes = 1000000;
            for (int i = 0; i < timeTimes; i++) {
                Program[] programs = generatePrograms(programSize, timeMax);
                if (bestArrange1(programs) != bestArrange2(programs)) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("finish!");
        }
    
    }

### 八、输入: 正数数组costs、正数数组profits、正数K、正数M costs\[i\]表示i号项目的花费 profits\[i\]表示i号项目在扣除花费之后还能挣到的钱(利润) K表示你只能串行的最多做k个项目 M表示你初始的资金 说明:每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。输出：你最后获得的最大钱数。 ###

package class14;
    
    import java.util.PriorityQueue;
    
    /**
     * 输入: 正数数组costs、正数数组profits、正数K、正数M
     * costs[i]表示i号项目的花费
     * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
     * K表示你只能串行的最多做k个项目
     * W表示你初始的资金
     * 说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
     * 输出：你最后获得的最大钱数。
     * <p>
     * 贪心思想：
     * 将每个项目的cost profit 都存放到一个类中 然后定义小根堆 大根堆 小根堆按cost排序 大根堆按profit排序
     * 然后从小根堆判断 取出来就是最小花费项目 与初始资金W比较 小的就可以做，就将其出堆，然后入大根堆
     * 最后我们判断入大根堆多个中的第一个 就是利益最大的 就做那个项目，同步刷新M 直到我们项目做完，或者我们资金不够做 退出
     */
    public class IPO {
        // 最多K个项目
        // W是初始资金
        // Profits[] Capital[] 一定等长
        // 返回最终最大的资金
        public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
            //定义小根堆 按花费排序   大根堆 按利润排序
            PriorityQueue<Program> minCostsHeap = new PriorityQueue<>((a, b) -> (a.costs - b.costs));
            PriorityQueue<Program> maxProfitsHeap = new PriorityQueue<>((a, b) -> (b.profits - a.profits));
            //遍历数组 利润和花费数组长度都是一样的 将利润 花费项目创建对象并入小根堆
            for (int i = 0; i < Profits.length; i++) {
                minCostsHeap.add(new Program(Profits[i], Capital[i]));
            }
            //开始判断能做多少项目使得最大M
            for (int i = 0; i < K; i++) {
                //当小根堆项目非空 并且资金W不小于小根堆顶项目的消费值 循环都入到大根堆，表示这些项目是可以做的
                while (!minCostsHeap.isEmpty() && minCostsHeap.peek().costs <= W){
                    maxProfitsHeap.add(minCostsHeap.poll());
                }
                //这里需要提前判断 是否是存在能做的项目 假如costs 远大于当前W 那么就无法做，到不了K个项目 需要判空提前退出返回资金值
                if(maxProfitsHeap.isEmpty()){
                    return W;
                }
                //入大根堆后，取堆顶项目做，利益最大,将其出堆 并累计利润给W
                W += maxProfitsHeap.poll().profits;
            }
            return W;
        }
    
        //定义一个类 存放项目的花费和利润
        public static class Program {
            public int profits; //利润
            public int costs; //花销
    
            public Program(int p, int c) {
                profits = p;
                costs = c;
            }
        }
    
    }