使用贪心来解决的一些问题

作者：Grey

原文地址：

博客园：使用贪心来解决的一些问题

CSDN：使用贪心来解决的一些问题

贪心的使用方法#

1. 根据业务逻辑找到不同的贪心策略

2. 对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性

3. 使用对数器来验证贪心策略的正确性与否

拼接所有的字符串产生字典序最小的字符串#

先考虑暴力解法：使用动态规划，枚举所有字符串，得到字典序最小的那个即可

贪心解法：使用排序，排序策略是

如果（字符串1 + 字符串2）的字典序小于（字符串2 + 字符串1）的字典序，则将(字符串1 + 字符串2)放在前面。

完整代码如下（使用暴力作为对数器验证贪心解法）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

//[编程题]拼接所有的字符串产生字典序最小的字符串
//https://www.nowcoder.com/questionTerminal/f1f6a1a1b6f6409b944f869dc8fd3381
public class NowCoder_LowestString {

    public static String minString(String[] strs) {
        Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }
        return sb.toString();
    }

    // 暴力解
    public static String minString2(String[] strs) {
        HashSet<Integer> used = new HashSet<>();
        ArrayList<String> all = new ArrayList<>();
        String path = "";
        process(strs, used, path, all);
        String min = all.get(0);
        for (String s : all) {
            if (min.compareTo(s) > 0) {
                min = s;
            }
        }
        return min;
    }

    // 已经用过的字符串在used中登记了
    // 已经用过的字符串拼接的结果是path
    // 所有拼接的方式存在all里面
    public static void process(String[] strs, HashSet<Integer> used, String path, ArrayList<String> all) {
        if (used.size() == strs.length) {
            all.add(path);
        } else {
            for (int i = 0; i < strs.length; i++) {
                if (!used.contains(i)) {
                    used.add(i);
                    process(strs, used, path + strs[i], all);
                    used.remove(i);
                }
            }
        }
    }

    public static void main(String[] args) {

        int arrLen = 6;
        int strLen = 5;
        int times = 100000;
        for (int i = 0; i < times; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            String[] arr1 = copyStringArray(arr);
            String[] arr2 = copyStringArray(arr);
            String ans1 = minString(arr1);
            String ans2 = minString2(arr2);

            if (!ans1.equals(ans2)) {
                printArray(arr);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }

    private static void printArray(String[] arr) {
        for (String s : arr) {
            System.out.print(s + ",");
        }
        System.out.println();

    }

    private static String[] copyStringArray(String[] arr1) {
        if (null == arr1) {
            return null;
        }
        String[] arr2 = new String[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = String.valueOf(arr1[i]);
        }
        return arr2;
    }

    private static String[] generateRandomStringArray(int arrLen, int strLen) {
        int len = (int) (Math.random() * (arrLen + 1));
        String[] arr = new String[len];
        for (int i = 0; i < len; i++) {
            arr[i] = generateString(strLen);
        }
        return arr;
    }

    private static String generateString(int strLen) {
        int len = (int) (Math.random() * (strLen)) + 1;
        char[] arr = new char[len];
        for (int i = 0; i < arr.length; i++) {
            int v = 97 + (int) (Math.random() * 26);
            arr[i] = (char) v;
        }
        return String.valueOf(arr);
    }

}

会议室安排问题#

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

完整代码如下（使用暴力作为对数器验证贪心解法）：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;


public class Code_BestArrange {
    public static class Program {
        public int start;
        public int end;

        public Program(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "start:" + start + " end:" + end;
        }
    }

    public static int bestArrange0(Program[] programs) {
        if (null == programs || programs.length < 1) {
            return 0;
        }
        List<Program> ans = new ArrayList<>();
        return p(programs, 0, ans);
    }

    public static int p(Program[] programs, int start, List<Program> ans) {
        if (programs.length == 0 || !enough(programs, start)) {
            return ans.size();
        } else {
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < programs.length; i++) {
                if (start <= programs[i].start) {
                    ans.add(programs[i]);
                    max = Math.max(p(copyExcept(programs, i), programs[i].end, ans), max);
                    ans.remove(programs[i]);
                }
            }
            return max;
        }
    }

    private static boolean enough(Program[] programs, int start) {
        boolean enough = false;
        for (Program p : programs) {
            if (start <= p.start) {
                enough = true;
                break;
            }
        }
        return enough;
    }

    public static Program[] copyExcept(Program[] p, int i) {
        int ind = 0;
        Program[] n = new Program[p.length - 1];
        for (int j = 0; j < p.length; j++) {
            if (j != i) {
                n[ind++] = p[j];
            }
        }
        return n;
    }


    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;
    }

    public static int bestArrange2(Program[] programs) {
        Arrays.sort(programs, Comparator.comparingInt(o -> o.end));
        int timeLine = 0;
        int result = 0;
        for (Program program : programs) {
            if (timeLine <= program.start) {
                result++;
                timeLine = program.end;
            }
        }
        return result;
    }


    // 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);
            int ans0 = bestArrange0(programs);
            int ans1 = bestArrange1(programs);
            int ans2 = bestArrange2(programs);
            if (ans1 != ans2 || ans1 != ans0 || ans0 != ans2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }



}

分金条的最小花费#

霍夫曼算法，贪心的策略为：

准备一个小根堆，把所有金条的价值加入小根堆，每次弹出堆顶两个（当下排名最小的两个值）相加存入cost变量，然后把相加后的和继续放入小根堆，反复上述操作，一直到大根堆只有一个数据。返回 cost 就是最小代价。

完整代码如下（使用暴力作为对数器验证贪心解法）：

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铜板。 输入一个数组，返回分割的最小代价。
 * <p>
 *     
 * 注：堆和排序是解决贪心问题的最常用的两种方案
 */
// https://www.nowcoder.com/questionTerminal/418d2fcdf7f24d6f8f4202e23951c0da
// https://www.lintcode.com/problem/minimum-cost-to-connect-sticks/description
public class NowCoder_SplitGolden {
    public static long lessMoney(long[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        if (arr.length == 2) {
            return arr[0] + arr[1];
        }

        PriorityQueue<Long> queue = new PriorityQueue<>();
        for (long i : arr) {
            queue.add(i);
        }
        long cost = 0;
        while (queue.size() > 1) {
            long i = queue.poll();
            long j = queue.poll();
            cost += (i + j);
            queue.offer(i + j);
        }
        return cost;
    }

    // 暴力递归版本
    public static long lessMoney0(long[] arr) {
        if (arr == null || arr.length <= 1) {
            return 0;
        }
        return process0(arr, 0);
    }

    private static long process0(long[] arr, long s) {
        if (arr.length == 1) {
            return s;
        } else {
            long min = Long.MAX_VALUE;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    min = Math.min(process0(copyExcept(arr, i, j), s + (arr[i] + arr[j])), min);
                }
            }
            return min;
        }
    }


    private static long[] copyExcept(long[] arr, int i1, int i2) {
        int m = 0;
        long[] nArr = new long[arr.length - 1];
        long t = 0;
        for (int j = 0; j < arr.length; j++) {
            if (j != i1 && j != i2) {
                nArr[m++] = arr[j];
            } else {
                t += arr[j];
            }
        }
        nArr[arr.length - 2] = t;
        return nArr;
    }

    public static long[] generateRandomArr(int maxSize, long maxValue) {
        int size = (int) (Math.random() * maxSize) + 1;
        long[] arr = new long[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (long) (Math.random() * (maxValue + 1)) - (long) (Math.random() * (maxValue + 1));
        }
        return arr;
    }

    public static void main(String[] args) {
        int times = 50000;
        long maxValue = 9;
        int maxSize = 7;
        for (int i = 0; i < times; i++) {
            long[] arr = generateRandomArr(maxSize, maxValue);
            if (lessMoney(arr) != lessMoney0(arr)) {
                System.out.println("Ops!");
            }
        }
        System.out.println("Nice!");
    }
}

IPO 问题#

贪心策略：

设置两个堆（一个大根堆，一个小根堆）来实现获取收益的最大值，由于本金为 W ，我们先把所有项目加入到小根堆中，将成本比 W 小或等于的项目加入到大根堆中，那么大根堆的堆顶元素就是但当前能获取收益最大的项目，然后将获取的收益和本金相加，重复这个过程直到做了 k 个项目为止。最终整体的最大收益即为每次的局部最大收益。

完整代码如下（使用暴力作为对数器验证贪心解法）：

class Solution {
    public static class Project {
        public int profit;
        public int capital;

        public Project(int profit, int capital) {
            this.profit = profit;
            this.capital = capital;
        }
    }

    // k项目个数
    // W初始资金
    // Profits收益
    // Capital花费
    // 所有花费可以cover的项目中，取最大收益的项目
    public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        if (k == 0) {
            return W;
        }
        if (Profits.length == 0) {
            return W;
        }
        k = Math.min(Profits.length, k); // 因为项目无法重复做，所以k最大只能是项目个数
        Project[] projects = initProjects(Profits, Capital);
        PriorityQueue<Project> min = new PriorityQueue<>(Comparator.comparingInt((Project o) -> o.capital));
        PriorityQueue<Project> max = new PriorityQueue<>((o1, o2) -> o2.profit - o1.profit);

        for (Project project : projects) {
            min.offer(project);
        }
        int maxProfit = W;
        while (k > 0) {
            while (!min.isEmpty() && min.peek().capital <= W) {
                max.offer(min.poll());
            }
            if (!max.isEmpty()) {
                maxProfit += max.poll().profit;
                k--;
                W = maxProfit;
            } else {
                break;
            }
        }
        return maxProfit;
    }

    private static Project[] initProjects(int[] profits, int[] capital) {
        Project[] projects = new Project[profits.length];
        for (int i = 0; i < profits.length; i++) {
            projects[i] = new Project(profits[i], capital[i]);
        }
        return projects;
    }
}

放置路灯问题#

贪心策略：如果 i 位置有点，且 i+1 位置也是点，那么 i 位置一定不需要放灯，等到 i+1 号位置来放灯即可。

完整代码如下（使用暴力作为对数器验证贪心解法）：

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个字符串str，只由‘X’和‘.’两种字符构成。 ‘X’表示墙，不能放灯，也不需要点亮 ‘.’表示居民点，可以放灯，需要点亮
 * 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯
 * <p>
 * 暴力方法 可以放灯的点，有放灯不放灯两种情况，在这两种情况下，摘出照亮所有点的情况， 然后再在这些情况中选出灯最少的方案
 */

// https://www.nowcoder.com/questionTerminal/45d20d0e59d94e7d8879f19a5755c177
// 贪心解法
public class NowCoder_Light {
    public static int minLight1(String str) {
        if (str == null || str.length() < 1) {
            return 0;
        }
        return p(str.toCharArray(), 0, new HashSet<>());
    }

    // i及其往后最少的放灯数
    // i之前的放灯情况存在set里面
    public static int p(char[] str, int i, Set<Integer> set) {
        if (i == str.length) {
            for (int s = 0; s < str.length; s++) {
                if (str[s] == '.' && (!set.contains(s - 1) && !set.contains(s) && !set.contains(s + 1))) {
                    return Integer.MAX_VALUE;
                }
            }
            return set.size();
        }
        int no = p(str, i + 1, set);
        if (str[i] == '.') {
            set.add(i);
            int yes = p(str, i + 1, set);
            set.remove(i);
            return Math.min(yes, no);
        }
        return no;
    }

    // 贪心解法
    // i位置有点，且i+1位置也是点，那么i位置一定不需要放灯，等到i+1号位置来放灯
    public static int minLight2(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        char[] str = s.toCharArray();
        int ans = 0;
        int i = 0;
        while (i < str.length) {
            if (str[i] == 'X') {
                i++;
            } else {
                // 无论如何都要
                ans++;
                if (i + 1 < str.length) {
                    if (str[i + 1] == '.') {
                        i += 3;
                    } else {
                        // str[i+1] == 'X'
                        i += 2;
                    }
                } else {
                    // i+1==str.length
                    i++;
                }

            }
        }
        return ans;
    }


    // 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);
            if (ans1 != ans2) {
                System.out.println("oops!");
            }
        }
        System.out.println("finish!");

    }
}

更多#

算法和数据结构笔记

参考资料#

算法和数据结构体系班-左程云