貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)(即最有利)的選擇,從而希望導(dǎo)致結(jié)果是全局最好或最優(yōu)的算法。
貪心算法與動態(tài)規(guī)劃的不同在于它對每個子問題的解決方案都作出選擇，不能回退。動態(tài)規(guī)劃則會保存以前的運(yùn)算結(jié)果，并根據(jù)以前的結(jié)果對當(dāng)前進(jìn)行選擇，有回退功能。
每次當(dāng)下選擇最好的會不會是全局最優(yōu)的呢？不一定，有時候可以，有時候不行
很多情況下，可以在某一步用貪心算法，全局再加一個搜索或遞歸或動態(tài)規(guī)劃之類
貪心:當(dāng)下做局部最優(yōu)判斷
回溯:能夠回退
動態(tài)規(guī)劃:最優(yōu)判斷+回退
貪心法可以解決一些最優(yōu)化問題，如:求圖中的最小生成樹、求哈夫曼編碼等。然而對于工程和生活中的問題，貪心法一般不能得到我們所要求的答案。
一單一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結(jié)果，貪心法也可以用作輔助算法或者直接解決一些要求結(jié)果不特別精確的問題。
當(dāng)硬幣可選集合固定:Coins = [20,10,5,1],求最少幾個硬幣可以拼出總數(shù)。比如total=36。
36 - 20 = 16 20
16 - 10 = 6 20 10
6 - 5 = 1 20 10 5
1 - 1 = 0 20 10 5 1
前面這些硬幣依次是后面硬幣的整數(shù)倍，可以用貪心法，能得到最優(yōu)解，
貪心法的反例
非整除關(guān)系的硬幣，可選集合:Coins = [10,9,1],求拼出總數(shù)為18最少需要幾個硬幣？
最優(yōu)化算法:9 + 9 = 18 兩個9
貪心算法:18 - 10 = 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0 八個1
何種情況下可以用到貪心算法
簡單地說，問題能夠分解成子問題來解決，子問題的最優(yōu)解能遞推到最終問題的最優(yōu)解。這種子問題最優(yōu)解成為最優(yōu)子結(jié)構(gòu)。
貪心算法與動態(tài)規(guī)劃的不同在于它對每個子問題的最終方案都作出選擇，不能回退。
動態(tài)規(guī)劃則會保存以前的運(yùn)算結(jié)果，并根據(jù)以前的結(jié)果對當(dāng)前進(jìn)行選擇，有回退功能。
分發(fā)餅干(亞馬遜)
假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。
示例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。
示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(yīng)該輸出2.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
public int findContentChildren(int[] g, int[] s) {
//排序小孩胃口值
Arrays.sort(g);
//排序餅干數(shù)量
Arrays.sort(s);
//記錄滿足條件數(shù)量
int res = 0;
int i = 0;
int j = 0;
while (i<g.length && j<s.length){
if (g[i] <= s[j]){
res+=1;
i++;
j++;
}else{
j++;
}
}
return res;
}
買賣股票的最佳時機(jī)(亞馬遜、字節(jié)、微軟)
給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。
設(shè)計(jì)一個算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。
因?yàn)檫@樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。
public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;
int res = 0;
for(int i = 1;i<prices.length;i++){
if (prices[i] > prices[i-1]){
res += (prices[i] - prices[i-1]);
}
}
return res;
}
跳躍游戲(亞馬遜、華為、Facebook)
給定一個非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個下標(biāo) 。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達(dá)最后一個下標(biāo)。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再從下標(biāo) 1 跳 3 步到達(dá)最后一個下標(biāo)。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 ， 所以永遠(yuǎn)不可能到達(dá)最后一個下標(biāo)。
public boolean canJump(int[] nums) {
if (nums == null) return false;
int endReachable = nums.length - 1;
for (int i = nums.length -1; i>=0;i--){
if (nums[i] + i >= endReachable){
endReachable = i;
}
}
return endReachable == 0;
}
跳躍游戲II(亞馬遜、華為、字節(jié)跳動)
給定一個非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個位置。
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個位置。
說明:
假設(shè)你總是可以到達(dá)數(shù)組的最后一個位置。
移動下標(biāo)只要遇到當(dāng)前覆蓋最遠(yuǎn)距離的下標(biāo)，直接步數(shù)加一，不考慮是不是終點(diǎn)的情況。
想要達(dá)到這樣的效果，只要讓移動下標(biāo)，最大只能移動到nums.size - 2的地方就可以了。
因?yàn)楫?dāng)移動下標(biāo)指向nums.size - 2時：
如果移動下標(biāo)等于當(dāng)前覆蓋最大距離下標(biāo)， 需要再走一步（即ans++），因?yàn)樽詈笠徊揭欢ㄊ强梢缘降慕K點(diǎn)。（題目假設(shè)總是可以到達(dá)數(shù)組的最后一個位置），如圖：
如果移動下標(biāo)不等于當(dāng)前覆蓋最大距離下標(biāo)，說明當(dāng)前覆蓋最遠(yuǎn)距離就可以直接達(dá)到終點(diǎn)了，不需要再走一步。如圖：
public int jump(int[] nums) {
int ans = 0;//記錄要跳躍的步數(shù)
int curDistance = 0; //當(dāng)前覆蓋的最遠(yuǎn)距離下標(biāo)
int nextDistance = 0; //下一步覆蓋的最遠(yuǎn)距離下標(biāo)
for (int i = 0;i<nums.length - 1;i++){//小于nums.length-1
nextDistance = Math.max(nums[i]+i,nextDistance);//獲取下一步能覆蓋的最遠(yuǎn)距離下標(biāo)
if (curDistance == i){//遇到當(dāng)前位置的最遠(yuǎn)距離下標(biāo)
curDistance = nextDistance;//更新當(dāng)前覆蓋的最遠(yuǎn)距離下標(biāo)
ans++;
}
}
return ans;
}
模擬行走機(jī)器人
機(jī)器人在一個無限大小的 XY 網(wǎng)格平面上行走，從點(diǎn) (0, 0) 處開始出發(fā)，面向北方。該機(jī)器人可以接收以下三種類型的命令 commands ：
-2 ：向左轉(zhuǎn) 90 度
-1 ：向右轉(zhuǎn) 90 度
1 <= x <= 9 ：向前移動 x 個單位長度
在網(wǎng)格上有一些格子被視為障礙物 obstacles 。第 i 個障礙物位于網(wǎng)格點(diǎn) obstacles[i] = (xi, yi) 。
機(jī)器人無法走到障礙物上，它將會停留在障礙物的前一個網(wǎng)格方塊上，但仍然可以繼續(xù)嘗試進(jìn)行該路線的其余部分。
返回從原點(diǎn)到機(jī)器人所有經(jīng)過的路徑點(diǎn)（坐標(biāo)為整數(shù)）的最大歐式距離的平方。（即，如果距離為 5 ，則返回 25 ）
注意：
北表示 +Y 方向。
東表示 +X 方向。
南表示 -Y 方向。
西表示 -X 方向。
示例 1：
輸入：commands = [4,-1,3], obstacles = []
輸出：25
解釋：
機(jī)器人開始位于 (0, 0)：
- 向北移動 4 個單位，到達(dá) (0, 4)
- 右轉(zhuǎn)
- 向東移動 3 個單位，到達(dá) (3, 4)
距離原點(diǎn)最遠(yuǎn)的是 (3, 4) ，距離為 32 + 42 = 25
示例 2：
輸入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
輸出：65
解釋：機(jī)器人開始位于 (0, 0)： - 向北移動 4 個單位，到達(dá) (0, 4)
- 右轉(zhuǎn)
- 向東移動 1 個單位，然后被位于 (2, 4) 的障礙物阻擋，機(jī)器人停在 (1, 4)
- 左轉(zhuǎn)
- 向北走 4 個單位，到達(dá) (1, 8)
距離原點(diǎn)最遠(yuǎn)的是 (1, 8) ，距離為 12 + 82 = 65
public int robotSim(int[] commands, int[][] obstacles) {
int result = 0;
int x=0,y=0,direction =0;
int[] directX = new int[]{0,1,0,-1};
int[] directY = new int[]{1,0,-1,0};
Set<String> obstacleSet = new HashSet<>();
for (int[] m: obstacles) {
obstacleSet.add(m[0]+","+m[1]);
}
for (int i : commands) {
if (i == -2){//向左轉(zhuǎn)
direction = (direction + 3)%4;
}
else if (i==-1){//向右轉(zhuǎn)
direction = (direction + 1)%4;
}else{
for (int j = 1;j<=i;j++){
int newX = x + directX[direction];
int newY = y + directY[direction];
if (obstacleSet.contains(newX+","+newY)){
break;
}
x = newX;
y = newY;
result = Math.max(result,x*x+y*y);
}
}
}
return result;
}
檸檬水找零(亞馬遜)
在檸檬水?dāng)偵?，每一杯檸檬水的售價為 5 美元。
顧客排隊(duì)購買你的產(chǎn)品，（按賬單 bills 支付的順序）一次購買一杯。
每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。
注意，一開始你手頭沒有任何零錢。
如果你能給每位顧客正確找零，返回 true ，否則返回 false 。
示例 1：
輸入：[5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元。
第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由于所有客戶都得到了正確的找零，所以我們輸出 true。
示例 2：
輸入：[5,5,10]
輸出：true
示例 3：
輸入：[10,10]
輸出：false
示例 4：
輸入：[5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那里，我們按順序收取 2 張 5 美元的鈔票。
對于接下來的 2 位顧客，我們收取一張 10 美元的鈔票，然后返還 5 美元。
對于最后一位顧客，我們無法退回 15 美元，因?yàn)槲覀儸F(xiàn)在只有兩張 10 美元的鈔票。
由于不是每位顧客都得到了正確的找零，所以答案是 false。
public boolean lemonadeChange(int[] bills) {
int five = 0,ten = 0,twenty = 0;
for (int bill : bills) {
if (bill == 5){
five++;
}else if(bill == 10){
if (five>0) {
five--;
ten++;
}else return false;
}else if(bill == 20){
if (ten>0 && five > 0){
ten --;
five --;
twenty ++;
}else if(five >=3){
five -= 3;
twenty ++;
}else{
return false;
}
}
}
return true;
}
coin change題目-零錢兌換
給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
你可以認(rèn)為每種硬幣的數(shù)量是無限的。
示例 1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
示例 2：
輸入：coins = [2], amount = 3
輸出：-1
示例 3：
輸入：coins = [1], amount = 0
輸出：0
示例 4：
輸入：coins = [1], amount = 1
輸出：1
示例 5：
輸入：coins = [1], amount = 2
輸出：2
int minAns = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount){
if (amount == 0) return 0;
Integer[] coinArray = Arrays.stream(coins).boxed().toArray(Integer[]::new);
Arrays.sort(coinArray,Collections.reverseOrder());
coinChangeBfs(coinArray,amount,0,0);
minAns = (minAns == Integer.MAX_VALUE)?-1:minAns;
return minAns;
}
//coinArray:硬幣數(shù)組 amount:目標(biāo)值 index: 有效硬幣數(shù)組范圍 count: 已使用硬幣數(shù) miniAns: 當(dāng)前最小值
public void coinChangeBfs(Integer[] coinArray,int amount,int index,int count){
if (amount == 0) {//遍歷到最后有解
minAns = Math.min(minAns,count);
return;
}
if (coinArray.length == index) return;//遍歷到最后無解
for (int maxCoinNum = amount/coinArray[index];maxCoinNum>=0 && maxCoinNum+count<minAns;maxCoinNum--){
coinChangeBfs(coinArray,amount-maxCoinNum*coinArray[index],index+1,count+maxCoinNum);
}
}
