使用贪心来解决的一些问题
作者：Grey
原文地址：
贪心的使用方法
-
分析业务
-
根据业务逻辑找到不同的贪心策略
-
对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性
-
使用对数器来验证贪心策略的正确性与否
拼接所有的字符串产生字典序最小的字符串
先考虑暴力解法：使用动态规划，枚举所有字符串，得到字典序最小的那个即可
贪心解法：使用排序，排序策略是
如果（字符串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!"); } } 
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/3.jpg&w=218&h=124&zc=1)
