使用贪心来解决的一些问题
作者：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!");
}
}