代碼隨想錄：貪心算法
貪心算法的本質(zhì)是選擇每一階段的局部最優(yōu)從而實現(xiàn)全局最優(yōu)
貪心算法的難點在于如何通過局部最優(yōu)推出全局最優(yōu)，驗證可不可以使用貪心算法可以舉反例，如果舉不出反例就可以嘗試貪心算法
貪心算法解題一般分四部：
1.將問題分解成子問題
2.找出適合的貪心策略
3.求解每一個子問題的最優(yōu)解
4.將局部最優(yōu)堆疊成全局最優(yōu)
力扣455：分發(fā)餅干
public?class?Solution?{
????int?Cookies(int[]?g,?int[]?s)
????{
????????int?result?=?0;
????????int?j?=?g.Length-1;
????????for?(int?i?=?s.Length-1;?i?>=0?;?i--)
????????{
????????????while?(i>=0&&j>=0&&?s[i]<g[j])
????????????{
????????????????j--;
//當前最大的餅干不能滿足胃口最大的孩子就看下一個孩子
????????????}
????????????
????????????if?(j>=0)
????????????{
????????????????result++;
????????????????j--;
//滿足了就計數(shù)并接著指定下一個孩子
????????????}
????????????
????????????if?(j<0)
????????????{
????????????????break;
//沒有下一個孩子就結(jié)束
????????????}
????????}
????????return?result;
????}
????public?int?FindContentChildren(int[]?g,?int[]?s)?{
????????Array.Sort(g);
????????Array.Sort(s);
????????return?Cookies(g,?s);
????}
}
力扣376：擺動序列
public?class?Solution?{
//局部最優(yōu)就是要刪除出現(xiàn)的每個單調(diào)坡度上面除兩端以外的節(jié)點，最后剩下的就是擺動序列
????int?Wiggle(int[]?nums,?bool[]?relation)
????{
????????int?count?=?1;
????????int?i?=?1;
????????while?(i<nums.Length&&nums[i]-nums[i-1]==0)
????????{
????????????i++;
//找到開頭第一次出現(xiàn)差值不為0的位置，第二次提交因為這里條件中忘寫i<nums.Length導致數(shù)據(jù)異常，在使用下標指定數(shù)字時要先判斷下標的范圍
????????}
????????if?(i!=nums.Length)
????????{
????????????count++;
????????????relation[i?-?1]?=?nums[i]?-?nums[i?-?1]?>?0;
????????????i++;
//第一次遇到差值計數(shù)加一
????????}
????????for?(;?i?<?nums.Length;?i++)
????????{
????????????
????????????if?(nums[i]-nums[i-1]!=0)
????????????{
????????????????relation[i-1]?=?nums[i]?-?nums[i?-?1]?>?0;
????????????????if?(relation[i-1]!=relation[i-2])
????????????????{
????????????????????count++;
//差值不等于0就看跟前一次差值正負是否相同，不同計數(shù)就+1
????????????????}
????????????}
????????????else?if?(nums[i]-nums[i-1]==0)
????????????{
????????????????relation[i-1]?=relation[i-2];
//差值等于0就繼承前一次的正負屬性
????????????}
????????????
????????}
????????return?count;
????}
????public?int?WiggleMaxLength(int[]?nums)
????{
????????if?(nums.Length<2)
????????{
????????????return?nums.Length;
????????}
????????bool[]?relation?=?new?bool[nums.Length];
????????return?Wiggle(nums,?relation);
????}
}
//第一次寫這個的時候為了應(yīng)對前幾個數(shù)全都相同的情況，將開頭差值為0的情況判斷寫到了for循環(huán)中間，因此導致中間出現(xiàn)差值為0的情況也被這樣處理，導致結(jié)果錯誤，開頭的情況就要在循環(huán)前處理完成，循環(huán)內(nèi)再處理循環(huán)內(nèi)出現(xiàn)的特殊情況
力扣53：最大子數(shù)組和
public?class?Solution?{
//遇到子數(shù)組和為負數(shù)時就放棄，從下一個元素繼續(xù)尋找新的子數(shù)組，最后統(tǒng)計和最大的子數(shù)組就行
????int?sub(int[]?nums)
????{
????????int?result?=?nums[0],temp=0;
????????for?(int?i?=?0;?i?<?nums.Length;?i++)
????????{
????????????temp?+=?nums[i];
????????????result?=?Math.Max(result,?temp);
//先更新result再判斷是否重置temp，否則數(shù)組只有一個負數(shù)時結(jié)果會變成0
????????????if?(temp<0)
????????????{
????????????????temp?=?0;
????????????}
????????}
????????return?result;
????}
????public?int?MaxSubArray(int[]?nums)
????{
????????return?sub(nums);
????}
}
力扣155：買賣股票的最佳時機II
public?class?Solution?{
//假設(shè)股票在第一天買進第三天賣出，利潤i=i[3]-i[1]，可以拆解為i=(i[3]-i[2])+(i[2]-i[1])，因此在哪天買進賣出最終受益都是這幾天每兩天的利潤和，分別計算每兩天的利潤并相加求出利潤為正的區(qū)間，并將全部正利潤結(jié)果加入到結(jié)果中即可得到最終利潤
????int?Profit(int[]?prices)
????{
????????int[]?profit?=?new?int[prices.Length?-?1];
????????int?count?=?0;
????????for?(int?i?=?1;?i?<?prices.Length;?i++)
????????{
????????????profit[i?-?1]?=?prices[i]?-?prices[i?-?1];
????????????if?(profit[i-1]>0)
????????????{
????????????????count?+=?profit[i?-?1];
????????????}
????????}
????????return?count;
????}
????public?int?MaxProfit(int[]?prices)
????{
????????return?Profit(prices);
????}
}
力扣55：跳躍游戲
public?class?Solution?{
//每一個數(shù)字都指定了跳躍范圍，只要在范圍內(nèi)的數(shù)字都可以跳到，對于在范圍內(nèi)的數(shù)字又指定了下一個跳躍范圍，因此只要不停更新跳躍范圍最后范圍包括最后一位數(shù)就一定能跳躍到
????public?bool?CanJump(int[]?nums)
????{
????????int?cover?=?0;
????????if?(nums.Length==1)
????????{
????????????return?true;
//只有一個元素一定能到最后
????????}
????????for?(int?i?=?0;?i?<=?cover;?i++)
????????{
//這里將循環(huán)終止條件設(shè)置為i<=cover，會隨著循環(huán)一起更新cover的值
????????????cover=Math.Max(i+nums[i],cover);
//如果寫cover+=nums[i]則會出現(xiàn)范圍不正確，會一直增加cover范圍，正確的范圍是當前坐標加當前數(shù)字
????????????if?(cover>=nums.Length-1)
????????????{
????????????????return?true;
????????????}
????????}
????????return?false;
????}
}
力扣45：跳躍游戲II
public?class?Solution?{
//與上題不同，因為要找最小步數(shù)所以不能隨便跳躍，需要在當前覆蓋范圍中尋找下次覆蓋范圍最大的位置進行跳躍，因此需要額外記錄下次跳躍范圍
????public?int?Jump(int[]?nums)
????{
????????int?curCover?=?0,count=0,nextCover=0;
????????if?(nums.Length==1)
????????{
????????????return?0;
????????}
????????for?(int?i?=?0;?i?<nums.Length-1;?i++)
????????{
//遍歷整個數(shù)組，終止條件設(shè)定為i<nums.Length-1，這樣在遍歷的時候會停在倒數(shù)第二位，如果這時當前覆蓋范圍不是下標說明最后一個數(shù)被覆蓋到，是下標說則根據(jù)判斷還要多走一步，這樣做就不需要考慮當移動下標到達當前覆蓋距離最遠下標時當前下標是不是集合終點。
????????????nextCover?=?Math.Max(i?+?nums[i],?nextCover);
//尋找當前覆蓋范圍內(nèi)的最大下次覆蓋范圍
????????????if?(i==curCover)
????????????{
//當前覆蓋范圍到頭了，需要多走一步才能到下次覆蓋范圍
????????????????count++;
????????????????curCover?=?nextCover;
//更新當前覆蓋范圍為最大的下次覆蓋范圍
????????????}
????????}
????????return?count;
????}
}
力扣134：加油站
public?class?Solution?{
????public?int?CanCompleteCircuit(int[]?gas,?int[]?cost)
????{
????????int[]?rest?=?new?int[gas.Length];
????????int?sum?=?0,start=0;
????????for?(int?i?=?0;?i?<?gas.Length;?i++)
????????{
????????????rest[i]?=?gas[i]?-?cost[i];
????????????sum?+=?rest[i];
????????}
????????if?(sum<0)
????????{
????????????return?-1;
//先判斷如果總耗油高于總油量說明走不完一圈
????????}
//油量-油耗大于等于0一定有走完一圈的解
????????int?curSum?=?0;
????????for?(int?i?=?0;?i?<?rest.Length;?i++)
????????{
????????????curSum?+=?rest[i];
//能走完一圈的話就找起點，如果當前油耗大于油量說明不能從這里出發(fā)，重置油耗差總和從下一個起點繼續(xù)開始找，循環(huán)結(jié)束時顯示的起點的位置就是要找的起點
????????????if?(curSum<0)
????????????{
????????????????start?=?i?+?1;
????????????????curSum?=?0;
????????????}
????????}
????????return?start;
????}
}
力扣135：分發(fā)糖果
public?class?Solution?{
????public?int?Candy(int[]?ratings)?{
????????int[]?candy=new?int[ratings.Length];
????????int?count?=?0;
????????candy[0]=1;
//循環(huán)中不會給首位賦值，因此在這里提前賦值為1
????????for?(int?i?=?1;?i?<?ratings.Length;?i++)
????????{
????????????candy[i]?=?1;
????????????if?(ratings[i]>ratings[i-1])
????????????{
????????????????candy[i]?=?candy[i?-?1]?+?1;
//從左向右遍歷，當前比左邊評分高就糖果數(shù)量+1
????????????}
????????}
????????count?+=?candy[candy.Length?-?1];
//循環(huán)中不會統(tǒng)計最后一個人得到的糖所以在這提前加上
????????for?(int?i?=?candy.Length-2;?i?>=0?;?i--)
????????{
????????????if?(ratings[i]>ratings[i+1])
????????????{
????????????????candy[i]?=?Math.Max(candy[i],?candy[i?+?1]?+?1);
//從右往左遍歷，當前比右邊評分高就將當前和右邊糖果數(shù)量+1取最大值作為當前糖果數(shù)量，這樣就能保證當前糖果數(shù)量比左右都多而且是最少所需要的
????????????}
????????????count?+=?candy[i];
//每次循環(huán)中將總糖果數(shù)量加到結(jié)果
????????}
????????return?count;
????}
}
力扣860：檸檬水找零
public?class?Solution?{
//從頭開始分別處理收到三種面值的情況即可
????public?bool?LemonadeChange(int[]?bills)
????{
????????int?five?=?0,?ten?=?0;
????????for?(int?i?=?0;?i?<?bills.Length;?i++)
????????{
????????????if?(bills[i]==5)
????????????{
????????????????five++;
//收到5就直接收下
????????????}
????????????else?if?(bills[i]==10)
????????????{
????????????????five--;
????????????????ten++;
????????????????if?(five<0)
????????????????{
????????????????????return?false;
//收到10就用5找零，找不了就return false
????????????????}
????????????}
????????????else?if?(bills[i]==20)
????????????{
????????????????if?(ten!=0)
????????????????{
????????????????????ten--;
????????????????????five--;
????????????????????if?(five<0)
????????????????????{
????????????????????????return?false;
????????????????????}
????????????????}
????????????????else
????????????????{
????????????????????five?-=?3;
????????????????????if?(five<0)
????????????????????{
????????????????????????return?false;
????????????????????}
//收到20就先嘗試用一張10和一張5找零，沒有10就用三張5找零，找不了就return false
????????????????}
????????????}
????????}
????????return?true;
????}
}
力扣452：用最少數(shù)量的箭引爆氣球
public?class?Solution?{
????public?int?FindMinArrowShots(int[][]?points)?{
????????Array.Sort(points,new?CompareMethod());
//使用接口實現(xiàn)對數(shù)組內(nèi)元素按下標為0的元素排序
????????if?(points.Length==0)
????????{
????????????return?0;
????????}
????????int?count?=?1;
//數(shù)組長度不為零，至少需要一支箭
????????for?(int?i?=?1;?i?<?points.Length;?i++)
????????{
????????????if?(points[i][0]>points[i-1][1])
????????????{
????????????????count++;
//如果新氣球在老氣球外面就需要多用一支箭
????????????}
????????????else
????????????{
????????????????points[i][1]?=?Math.Min(points[i][1],?points[i?-?1][1]);
//跟老氣球有重疊就更新下標
????????????}
????????}
????????return?count;
????}
}
public?class?CompareMethod?:?IComparer<int[]>
{
????public?int?Compare(int[]?x,?int[]?y)
????{
????????if?(x[0]>y[0])
????????{
????????????return?1;
????????}
????????else?if?(x[0]?==?y[0])
????????{
????????????return?0;
????????}
????????else?return?-1;
//實現(xiàn)接口，最開始的時候接口內(nèi)的實現(xiàn)為returnx[0]-y[0]，但是這樣會造成數(shù)據(jù)溢出，在x[0]和y[0]相減的結(jié)果會超出數(shù)據(jù)定義范圍的時候得到的結(jié)果就是不正確的，因此改為比較x[0]與y[0]的大小，按比較結(jié)果返回-1，0或1最終實現(xiàn)排序
????}
}
力扣56：合并區(qū)間
public?class?Solution?{
????public?int[][]?Merge(int[][]?intervals)?{
????????Array.Sort(intervals,new?CompareMethod());
????????if?(intervals.Length==0)
????????{
????????????return?null;
????????}
????????
????????IList<int[]>?list?=?new?List<int[]>();
????????int[]?temp?=?new?[]{intervals[0][0],intervals[0][1]};
????????if?(intervals.Length==1)
????????{
????????????list.Add(new?[]{intervals[0][0],intervals[0][1]});
//特殊情況，只有一組數(shù)就直接輸出
????????}
????????for?(int?i?=?1;?i?<?intervals.Length;?i++)
????????{
????????????if?(intervals[i][0]<=intervals[i-1][1])
????????????{
????????????????intervals[i][0]?=?intervals[i?-?1][0];
????????????????intervals[i][1]?=?Math.Max(intervals[i?-?1][1],?intervals[i][1]);
????????????????temp[0]?=?intervals[i][0];
????????????????temp[1]?=?intervals[i][1];
//能合并就先更新當前下標的數(shù)再將合并后的區(qū)間寫進temp里
????????????????if?(i==intervals.Length-1)
????????????????{
????????????????????list.Add(new?[]{temp[0],temp[1]});
//特殊情況只有兩組數(shù)需要額外加一次統(tǒng)計結(jié)果
????????????????}
????????????}
????????????else
????????????{
????????????????list.Add(new?int[]?{temp[0],temp[1]});
//發(fā)現(xiàn)不能合并了就將上一組的區(qū)間加入結(jié)果，注意加入結(jié)果時需要得到這個temp數(shù)組的引用而不能直接將temp加入結(jié)果
????????????????if?(i==intervals.Length-1)
????????????????{
????????????????????temp[0]?=?intervals[i][0];
????????????????????temp[1]?=?intervals[i][1];
????????????????????list.Add(new?[]{temp[0],temp[1]});
//如果是不能合并的新區(qū)間還是最后一組數(shù)就將這組也加入結(jié)果
????????????????}
????????????????temp[0]?=?intervals[i][0];
????????????????temp[1]?=?intervals[i][1];
//更新temp內(nèi)的數(shù)據(jù)
????????????}
????????}
????????int[][]?result?=?new?int[list.Count][];
????????for?(int?i?=?0;?i?<?list.Count;?i++)
????????{
????????????result[i]?=?list[i];
//將IList<int[]>轉(zhuǎn)換成int[][]數(shù)組形式作為結(jié)果
????????}
????????return?result;
????}
}
public?class?CompareMethod?:?IComparer<int[]>
{
????public?int?Compare(int[]?x,?int[]?y)
????{
????????if?(x[0]>y[0])
????????{
????????????return?1;
????????}
????????else?if?(x[0]?==?y[0])
????????{
????????????return?0;
????????}
????????else?return?-1;
????????
????}
}
力扣738：單調(diào)遞增的數(shù)字
using?System.Text;
public?class?Solution?{
????public?int?MonotoneIncreasingDigits(int?n)
????{
????????if?(n<10)
????????{
????????????return?n;
????????}
????????StringBuilder?str?=?new?StringBuilder();
????????str.Append(System.Convert.ToString(n));
//將給的int類型轉(zhuǎn)換成為StringBuilder類型方便操作
????????for?(int?i?=?str.Length-2;?i?>=?0;?i--)
????????{
//當遇到非首位的高一位比低一位大時高一位數(shù)字減一，后面所有數(shù)字變成9
????????????if?(str[i]>str[i+1])
????????????{
????????????????str[i]--;
????????????????if?(i!=0?||(i==0&&?str[i]!=0))
????????????????{
????????????????????for?(int?j=i+1;?j?<?str.Length;?j++)
????????????????????{
????????????????????????str[j]?=?'9';
????????????????????}
????????????????}
????????????????else
????????????????{
????????????????????str.Remove(0,?1);
????????????????????for?(int?j?=?0;?j?<?str.Length;?j++)
????????????????????{
????????????????????????str[j]?=?'9';
//首位特殊處理，這時候就要刪掉首位了
????????????????????}
????????????????}
????????????}
????????}
????????return?System.Convert.ToInt32(str.ToString());
//使用Convert只能將string類型轉(zhuǎn)換為int類型，不能直接轉(zhuǎn)換StringBuilder
????}
}
