參考
理論
本質：找到每個階段的區域最優，然后去推導得到全域最優
兩個極端：常識&&很難：
很多同學通過了貪心的題目，但都不知道自己用了貪心演算法，因為貪心有時候就是常識性的推導，所以會認為本應該就這么做！
套路：
貪心沒有套路，說白了就是常識性推導加上舉反例
做題的時候，只要想清楚 區域最優 是什么，如果推匯出全域最優，其實就夠了，
貪心演算法一般分為如下四步：
將問題分解為若干個子問題
找出適合的貪心策略
求解每一個子問題的最優解
將區域最優解堆疊成全域最優解
這個四步其實過于理論化了，我們平時在做貪心類的題目 很難去按照這四步去思考，真是有點“雞肋”，
Leetcode題目
簡單題
455.分發餅干
思路：大餅干 喂 胃口大的kid，才能充分利用
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int j=s.length-1;
int sum = 0;
for(int i=g.length-1;i>=0;i--){
if(j>=0 && s[j]>=g[i]){
sum++;
j--;
}
}
return sum;
}
}
中等題
序列問題---376. 擺動序列
思路：考慮情況
記錄擺動條件：
prediff>0 && curdiff<0
或者 prediff<0 && curdiff>0
情況1：上下坡中有平坡
在圖中，當i指向第一個2的時候，prediff > 0 && curdiff = 0 ，當 i 指向最后一個2的時候 prediff = 0 && curdiff < 0，
如果我們采用，刪左面三個2的規則，那么 當 prediff = 0 && curdiff < 0 也要記錄一個峰值，
綜合到上述：記錄條件【prediff>=0 && curdiff<0 或 prediff=<0 && curdiff>0】
情況2：首尾兩端
result初始為1（默認最右面有一個峰值），
curDiff > 0 && preDiff <= 0，那么result++（計算了左面的峰值），最后得到的result就是2（峰值個數為2即擺動序列長度為2）
做法：初始化prediff=0
情況3：單調有平坡
只需要在 這個坡度 擺動變化的時候，更新prediff就行，這樣prediff在 單調區間有平坡的時候 就不會發生變化
做法：調整prediff更新位置
java實作
class Solution {
public int wiggleMaxLength(int[] nums) {
int prediff = 0;//考慮只有兩個元素的時候，默認為0；為頭元素制造一個平坡
int curdiff = 0;
int result = 1;//默認最右端有坡度
//一個元素的時候
if(nums.length == 0) return result;
for(int i=0;i<nums.length-1;i++){//nums.length-1 因為最右端已經記錄了
curdiff = nums[i+1] - nums[i];
if((prediff>=0 && curdiff <0) || (prediff<=0 && curdiff >0)){
result++;
prediff = curdiff;
}
//prediff = curdiff;
}
return result;
}
}
股票問題---122. 買賣股票的最佳時機 II
兩個維度權衡問題---135. 分發糖果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550667.html
標籤：其他
上一篇：【ACM演算法競賽日常訓練】DAY16【奇♂妙拆分】【區區區間間間】【小AA的數列】數學 | 位運算 | 前綴和
下一篇：返回列表