《算法筆記》9. 培養貪心思維、貪心算法深度實踐
目錄
1 貪心算法
1.1 基本概念
1、最自然智慧的算法
2、用一種局部最功利的標準，總是能做出在當前看來是最好的選擇
3、難點在於證明局部最優解最功利的標準可以得到全局最優解
4、對於貪心算法的學習主要是以增加閱歷和經驗為主
1.2.1 貪心算法解釋
正例：通過一個例子來解釋，假設一個數組中N個正數，第一個挑選出來的數乘以1，第二個挑選出來的數乘以2，同理，第N次挑選出來的數乘以N，總的加起來是我們的分數。怎麼挑選數字使我們達到最大分數？
數組按從小到大的順序排序，我們按順序依次挑選，最終結果就是最大的。本質思想是因子隨着挑選次數的增加會增大，我們盡量讓大數去結合大的因子。
貪心算法有時是無效的，後面會貪心算法無效的例子
1.2.2 貪心算法的證明問題
如何證明貪心算法的有效性？
一般來說，貪心算法不推薦證明，很多時候證明是非常複雜的。通過下面例子來說明貪心算法證明的複雜性，從頭到尾講一道利用貪心算法求解的題目。
例子：給定一個由字符串組成的數組strs，必須把所有的字符串拼接起來，返回所有可能的拼接結果中，字典序最小的結果。
字典序概念：直觀理解，兩個單詞放到字典中，從頭開始查找這個單詞，哪個先被查找到，哪個字典序小。
字典序嚴格定義，我們把字符串當成k進制的數，a-z當成26進制的正數，字符長度一樣，abk>abc，那麼我們說abk的字典序更大。字符長度不一樣ac和b，那麼我們要把短的用0補齊，0小於a的accil，那麼ac<b0，高位b>a即可比較出來大小。
Java中字符串的ComparTo方法，就是比較字典序。
本題思路1：按照單個元素字典序貪心，例如在[ac,bk,sc,ket]字符串數組中，我們拼接出來最終的字符串字典序最小，那麼我們依次挑選字典序最小的進行拼接的貪心策略得到acbkketsc。
但是這樣的貪心不一定是正確的，例如[ba,b]按照上述思路的貪心結果是bba，但是bab明顯是最小的結果
本題思路2：兩個元素x和y，x拼接y小於等於x拼接y，那麼x放前，否則y放前面。例如x=b,y=ba。bba大於bab的字典與，那麼ba放前面
證明：
我們把拼接當成k進制數的數學運算，把a-z的數當成26進制的數，’ks’拼接’ts’實質是ks * 26^2 + te。
目標先證明我們比較的傳遞性：證明a拼接b小於b拼接a，b拼接c小於等於c拼接b，推出a拼接c小於等於c拼接a。
a拼接b等於a乘以k的b長度次方 + b。我們把k的x長度次方這個操作當成m(x)函數。所以：
a * m(b) + b <= b * m(a) + a
b * m(c) + c <= c * m(b) + b
=>
a * m(b) * c <= b * m(a) * c + ac - bc
b * m(c) * a + ca - ba <= c * m(b) * a
=>
b * m(c) * a + ca - ba <= b * m(a) * c + ac - bc
=>
m(c) * a + c <= m(a) * c + a
至此，我們證明出我們的排序具有傳遞性質。
根據我們排序策略得到的一組序列，證明我們任意交換兩個字符的位置，都會得到更大的字典序。
例如按照思路二得到的amnb序列，我們交換a和b。我們先把a和m交換，由於按照思路二得到的序列，滿足a.m <= m.a 那麼所以manb > amnb，同理得到amnb < bmna。
再證明任意三個交換都會變為更大的字典序，那麼最終數學歸納法，得到思路二的正確性
所以貪心算法的證明實質是比較複雜的，我們大可不必每次去證明貪心的正確性
package class09;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
public class Code01_LowestLexicography {
// 暴力法窮舉，排列組合
public static String lowestString1(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
ArrayList<String> all = new ArrayList<>();
HashSet<Integer> use = new HashSet<>();
process(strs, use, "", all);
String lowest = all.get(0);
for (int i = 1; i < all.size(); i++) {
if (all.get(i).compareTo(lowest) < 0) {
lowest = all.get(i);
}
}
return lowest;
}
// strs里放着所有的字符串
// 已經使用過的字符串的下標，在use里登記了，不要再使用了
// 之前使用過的字符串，拼接成了-> path
// 用all收集所有可能的拼接結果
public static void process(String[] strs, HashSet<Integer> use, String path, ArrayList<String> all) {
// 所有字符串都是用過了
if (use.size() == strs.length) {
all.add(path);
} else {
for (int i = 0; i < strs.length; i++) {
if (!use.contains(i)) {
use.add(i);
process(strs, use, path + strs[i], all);
use.remove(i);
}
}
}
}
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;
}
// for test
public static String generateRandomString(int strLen) {
char[] ans = new char[(int) (Math.random() * strLen) + 1];
for (int i = 0; i < ans.length; i++) {
int value = (int) (Math.random() * 5);
ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
}
return String.valueOf(ans);
}
// for test
public static String[] generateRandomStringArray(int arrLen, int strLen) {
String[] ans = new String[(int) (Math.random() * arrLen) + 1];
for (int i = 0; i < ans.length; i++) {
ans[i] = generateRandomString(strLen);
}
return ans;
}
// for test
public static String[] copyStringArray(String[] arr) {
String[] ans = new String[arr.length];
for (int i = 0; i < ans.length; i++) {
ans[i] = String.valueOf(arr[i]);
}
return ans;
}
public static void main(String[] args) {
int arrLen = 6;
int strLen = 5;
int testTimes = 100000;
String[] arr = generateRandomStringArray(arrLen, strLen);
System.out.println("先打印一個生成的字符串");
for (String str : arr) {
System.out.print(str + ",");
}
System.out.println();
System.out.println("test begin");
for (int i = 0; i < testTimes; i++) {
String[] arr1 = generateRandomStringArray(arrLen, strLen);
String[] arr2 = copyStringArray(arr1);
if (!lowestString1(arr1).equals(lowestString2(arr2))) {
for (String str : arr1) {
System.out.print(str + ",");
}
System.out.println();
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
全排列的時間複雜度為：O(N!)
每一種貪心算法有可能都有屬於他自身的特有證明，例如哈夫曼樹算法，證明千變萬化
貪心策略算法，盡量不要陷入複雜的證明
1.2 貪心算法求解思路
1.2.1 標準求解過程
1、分析業務
2、根據業務邏輯找到不同的貪心策略
3、對於能舉出反例的策略，直接跳過，不能舉出反例的策略要證明有效性，這往往是比較困難的，要求數學能力很高且不具有統一的技巧性
1.2.2 貪心算法解題套路
1、實現一個不依靠貪心策略的解法X,可以用暴力嘗試
2、腦補出貪心策略A,貪心策略B,貪心策略C……
3、用解法X和對數器，用實驗的方式得知哪個貪心策略正確
4、不要去糾結貪心策略的證明
貪心類的題目在筆試中，出現的概率高達6到7成，而面試中出現貪心的概率不到2成。因為筆試要的是淘汰率，面試要的是區分度。由於貪心的解決完全取決於貪心策略有沒有想對，有很高的淘汰率但是沒有很好的區分度
1.3 貪心算法套路解題實戰
1.3.1 例一：會議日程安排問題
一些項目要佔用一個會議室宣講，會議室不能同時容納兩個項目宣講。給你每個項目的開始時間和結束時間，你來安排宣講的日程，要求會議室進行宣講的場數最多。
返回最多的宣講場次。
思路：本題常見的幾種貪心策略，一種是按照誰先開始安排誰，第二種按照持續時間短的先安排，第三種按照誰先結束安排誰。
通過驗證，無需證明得出第三種貪心策略是正確的
package class09;
import java.util.Arrays;
import java.util.Comparator;
public class Code04_BestArrange {
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;
}
// 解法2：貪心算法
public static int bestArrange2(Program[] programs) {
Arrays.sort(programs, new ProgramComparator());
// timeline表示來到的時間點
int timeLine = 0;
// result表示安排了多少個會議
int result = 0;
// 由於剛才按照結束時間排序，當前是按照誰結束時間早的順序遍歷
for (int i = 0; i < programs.length; i++) {
if (timeLine <= programs[i].start) {
result++;
timeLine = programs[i].end;
}
}
return result;
}
// 根據誰的結束時間早排序
public static class ProgramComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
// 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);
if (bestArrange1(programs) != bestArrange2(programs)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
1.3.2 例二：居民樓路燈問題
給定一個字符串str，只由『X』和『.』兩中國字符構成。
『X』表示牆，不能放燈，也不需要點亮，『.』表示居民點，可以放燈，需要點亮。
如果燈放在i位置，可以讓i-1，i和i+1三個位置被點亮，返回如果點亮str中所需要點亮的位置，至少需要幾盞燈
例如： X..X……X..X. 需要至少5盞燈
package class09;
import java.util.HashSet;
public class Code02_Light {
// 純暴力，用來做對數器。點的位置放燈和不放燈全排列
public static int minLight1(String road) {
if (road == null || road.length() == 0) {
return 0;
}
return process(road.toCharArray(), 0, new HashSet<>());
}
// str[index....]位置，自由選擇放燈還是不放燈
// str[0..index-1]位置呢？已經做完決定了，那些放了燈的位置，存在lights里
// 要求選出能照亮所有.的方案，並且在這些有效的方案中，返回最少需要幾個燈
public static int process(char[] str, int index, HashSet<Integer> lights) {
// index來到結束位置的時候，當前方案準備結束
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;
}
}
}
// 經過for循環的檢查，任意點的位置都被照亮了，返回當前有效的一種解
return lights.size();
} else { // str還沒結束
// i位置不管是 X 或者 . 都可以選擇不放燈
int no = process(str, index + 1, lights);
int yes = Integer.MAX_VALUE;
// 只有在i位置是.的時候，才可以選擇放燈
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();
// index從0出發
int index = 0;
// 當前燈的個數
int light = 0;
while (index < str.length) {
// 當前i位置是X，直接跳到下一個位置做決定
if (str[index] == 'X') {
index++;
// i 位置是 . 不管i+1是X還是.當前區域需要放燈
} else {
light++;
// 接下來沒字符了，遍歷結束
if (index + 1 == str.length) {
break;
} else {
// 如果i+1位置是X，在i位置放燈，去i+2位置做決定
if (str[index + 1] == 'X') {
index = index + 2;
// i位置是. i+1也是. 那麼不管i+2是什麼，都在i+1位置放燈，到i+3去做決定
} else {
index = index + 3;
}
}
}
}
return light;
}
// 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.3.3 例三：哈夫曼樹問題
一根金條切成兩半，是需要花費和長度值一樣的銅板的。
比如長度為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個銅板。
輸入一個數組，返回分割的最小代價。
小根堆，大根堆，排序。是貪心策略最常用的手段，coding代碼量很少。因為堆天然就具備根據我們自定義的排序規則重新組織數據
package class09;
import java.util.PriorityQueue;
public class Code03_LessMoneySplitGold {
// 暴力解法
public static int lessMoney1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return process(arr, 0);
}
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中去
sum += cur;
// 把合成的數加入小根堆中
pQ.add(cur);
}
return sum;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * (maxValue + 1));
}
return arr;
}
public static void main(String[] args) {
int testTime = 100000;
int maxSize = 6;
int maxValue = 1000;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
if (lessMoney1(arr) != lessMoney2(arr)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
1.3.4 例四：項目花費和利潤問題
輸入：正數數組costs，正數數組profits,正數K,正數M
costs[i]表示i號項目的花費，profits[i]表示i號項目在扣除花費之後還能掙到的錢（利潤）
K表示你只能串行的最多K個項目，M表示你的初始資金。
說明：每做完一個項目，馬上獲得收益，可以支持你去做下一個項目。不能並行的做項目。
輸出：你最後獲得的最大錢數。
package class09;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Code05_IPO {
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]));
}
// 做k輪項目
for (int i = 0; i < K; i++) {
// 小根堆不為空，且堆頂的花費被我當前啟動資金cover住
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;
}
}
}
