09-贪心算法
贪心算法
- 最自然智慧的算法
- 用一种局部最功利的标准，总是做出在当前看来是最好的选择
- 难点在于证明局部最功利的标准可以得到全局最优解
- 对于贪心算法的学习主要以增加阅历和经验为主
贪心算法求解的标准过程
1，分析业务
2，根据业务逻辑找到不同的贪心策略
3，对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性
这往往是特别困难的，要求数学能力很高且不具有统一的技巧性
贪心算法的解题套路
1，实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
2，脑补出贪心策略A、贪心策略B、贪心策略C…
3，用解法X和对数器，用实验的方式得知哪个贪心策略正确
4，不要去纠结贪心策略的证明
字符串组成的数组拼接后字典序最小的结果
给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，
返回所有可能的拼接结果中，字典序最小的结果
字典序
认为字符串就是K进制的正数
当两个字符串长度一样，直接认为是K进制的正数进行比较
当两个字符串长度不一样的时候，短的要补的跟长的一样长，通过补0完成(认为0的ASCII比a还小)
暴力解法中，深度优先遍历后记得要恢复数据，防止脏数据影响后面的操作，避免干扰平行分支里后面的选择
暴力解：
public static String lowestString1(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
TreeSet<String> ans = process(strs);
return ans.size() == 0 ? "" : ans.first();
}
// strs中所有字符串全排列，返回所有可能的结果
public static TreeSet<String> process(String[] strs) {
TreeSet<String> ans = new TreeSet<>();
if (strs.length == 0) {
ans.add("");
return ans;
}
for (int i = 0; i < strs.length; i++) {
String first = strs[i];
String[] nexts = removeIndexString(strs, i);
TreeSet<String> next = process(nexts);
for (String cur : next) {
ans.add(first + cur);
}
}
return ans;
}
public static String[] removeIndexString(String[] arr, int index) {
int N = arr.length;
String[] ans = new String[N - 1];
int ansIndex = 0;
for (int i = 0; i < N; i++) {
if (i != index) {
ans[ansIndex++] = arr[i];
}
}
return ans;
}
贪心:
public static class MyComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
return (a + b).compareTo(b + a);
}
}
public static String lowestString2(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
Arrays.sort(strs, new MyComparator());
String res = "";
for (int i = 0; i < strs.length; i++) {
res += strs[i];
}
return res;
}
点亮str中所有需要点亮的位置至少需要几盏灯
给定一个字符串str，只由‘X’和‘.’两种字符构成。
‘X’表示墙，不能放灯，也不需要点亮
‘.’表示居民点，可以放灯，需要点亮
如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮
返回如果点亮str中所有需要点亮的位置，至少需要几盏灯
暴力解：
// 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();
}
// str还没结束
else {
// 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[] str = road.toCharArray();
int i = 0;
int light = 0;
while (i < str.length) {
if (str[i] == 'X') {
i++;
} else {
//灯数量++，因为无论我后面是灯还是X，都会放一盏灯
light++;
//判断是否结尾，break
if (i + 1 == str.length) {
break;
}
else {
//如果下一个是X ，跳到下下个。
if (str[i + 1] == 'X') {
i = i + 2;
//如果下一个是灯，跳3格，因为无论是 。。。 还是 。。X 灯数量已经+1，跳到下一步继续判断zz
} else {
i = i + 3;
}
}
}
}
return light;
}
金条分割的最小代价
一块金条切成两半，是需要花费和长度数值一样的铜板的。
比如长度为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 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> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
会议室能容纳的最多宣讲场次
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间
你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。
返回最多的宣讲场次。
暴力解：
public static class Program {
public int start;
public int end;
public Program(int start, int end) {
this.start = start;
this.end = end;
}
}
// 暴力！所有情况都尝试！
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;
}
贪心：
// 会议的开始时间和结束时间，都是数值，不会 < 0
public static int bestArrange2(Program[] programs) {
Arrays.sort(programs, new ProgramComparator());
int timeLine = 0;
int result = 0;
// 依次遍历每一个会议，结束时间早的会议先遍历
for (int i = 0; i < programs.length; i++) {
if (timeLine <= programs[i].start) {
result++;
timeLine = programs[i].end;
}
}
return result;
}
做项目获得的最大钱数
输入: 正数数组costs、正数数组profits、正数K、正数M
costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
K表示你只能串行的最多做k个项目
M表示你初始的资金
说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
输出：你最后获得的最大钱数。
贪心：
// 最多K个项目
// W是初始资金
// Profits[] Capital[] 一定等长
// 返回最终最大的资金
public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
for (int i = 0; i < Profits.length; i++) {
minCostQ.add(new Program(Profits[i], Capital[i]));
}
for (int i = 0; i < K; i++) {
while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
maxProfitQ.add(minCostQ.poll());
}
if (maxProfitQ.isEmpty()) {
return W;
}
W += maxProfitQ.poll().p;
}
return W;
}
public static class Program {
public int p;
public int c;
public Program(int p, int c) {
this.p = p;
this.c = c;
}
}
public static class MinCostComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.c - o2.c;
}
}
public static class MaxProfitComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o2.p - o1.p;
}
}
一些总结
其实贪心算法其实就是找一种策略， 局部最优从而可以得到全局最优。
我们需要根据问题，去思考对应的策略，从而得到解。
如上面的那道题，很明显，策略就是我要去做自己有能力，且可以获得最多的钱的项目。
代码也是通过costs小根堆锁住不能的项目，profits大根堆表示可以做的项目。
这样去不断做够能力且钱最多的项目。这是一种策略。
倒数第二道，思考的策略就是，endtime早的，先安排。安排后将不能安排的划掉，继续找endtime早的，且能安排的。
所以说，策略需要根据具体具体业务逻辑去思考。
但我们可以使用暴力解法，如暴力递归，得到一个解法X
然后我们可以思考自动策略，对于能举出反例的策略直接跳过。
如果思考出策略后，可以使用暴力解法X和对数器，来验证自己的策略是否正确。
09-贪心算法
https://blog.isle.ink//archives/tan-xin-suan-fa