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

作者：Grey

原文地址：

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

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

贪心的使用方法

分析业务
根据业务逻辑找到不同的贪心策略
对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性
使用对数器来验证贪心策略的正确性与否

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

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

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

如果**（字符串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);
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

会议室安排问题

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

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

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!");
    }



}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

分金条的最小花费

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

准备一个小根堆，把所有金条的价值加入小根堆，每次弹出堆顶两个（当下排名最小的两个值）相加存入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铜板。 输入一个数组，返回分割的最小代价。
 * 
 *     
 * 注：堆和排序是解决贪心问题的最常用的两种方案
 */
// 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!");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

放置路灯问题

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

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

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

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

// 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!");

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

算法和数据结构笔记

参考资料

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

相关阅读:
Java包装类
 【 OpenGauss源码学习 —— 列存储（analyze）(四)】
31.springboot中的注解总结（spring,springmvc,springboot,mybatis,dubbo）
JVM：（五）运行时数据区之虚拟机栈
 【毕业设计】基于大数据的抖音短视频数据分析与可视化 - python 大数据可视化
 中老年美文视频祝福打卡流量主小程序开发
 Linux 中的 cd 命令及示例
 java 启动Selenium 以及端口占用的问题
 ubuntu18.04+RTX3080下安装rangnet++推理版踩坑全纪录
 什么是3322域名?3322域名如何注册?
原文地址：https://blog.csdn.net/hotonyhui/article/details/126918006

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