貪心算法：由局部最優->全局最優
貪心算法一般分為如下四步：
- 將問題分解為若干個子問題
- 找出適合的貪心策略
- 求解每一個子問題的最優解
- 將局部最優解堆疊成全局最優解
一、擺動序列（理解難）
連續數字之間的差有正負的交替，則序列稱為擺動序列。返回的nums值是擺動序列中元素的個數
-
例如，?
[1, 7, 4, 9, 2, 5]?是一個?擺動序列?，因為差值?(6, -3, 5, -7, 3)?是正負交替出現的。 - 相反，
[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5]?不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零。 
思路：將數組想象成一個上上下下的圖表，定義curDiff=nums[i]-nums[i-1]；和preDiff=nums[i+1]-nums[i];
考慮數組兩端 :?假設在數組開頭元素再添加一個相同的元素(或者初始化preDiff==0)，這樣在遍歷第一個元素的時候，就不會發生數組越界問題。if(preDiff>=0&&curDiff<0||preDiff<=0&&curDiff>0)
前者對應的是先上再下，后者對應的是先下（可能為平坡）再上
考慮到末尾元素，直接讓result=1(默認最右邊有一個峰值)
單調坡度有平坡:?
不是每一次遍歷都要更新preDiff的值，而是當遇到峰值，前后波動的時候才去更新preDiff的值（為什么？）；
代碼：
class Solution {public int wiggleMaxLength(int[] nums) {// 根據nums的長度剪枝if (nums.length <= 1)return nums.length;// 定義preDiff 和 curDiff 根據循環加resultint preDiff = 0;int curDiff = 0;int result = 1;// 把最后的元素看成一個峰值 直接+1for (int i = 0; i < nums.length - 1; i++) {curDiff = nums[i + 1] - nums[i];if (preDiff <= 0 && curDiff > 0 || preDiff >= 0 && curDiff < 0) {result++;// 遇到峰值 前后波動preDiff = curDiff;}}return result;}
}二、最大子序和（貪心法/dp）
貪心法：
由局部最優推導出全局最優：連續和變為負數，下一個元素就不要加連續和。連續和為正數再加。
count+=nums[i] if(count>result)result=count; if(count<0)count=0;
代碼：
public int maxSubArray(int[] nums) {int result=Integer.MIN_VALUE;int count=0;for(int i=0;i<nums.length;i++){count+=nums[i];if(count>result)result=count;if(count<0)count=0;}return result;}Dp（動態規劃）:
dp[i]:表示以從0->i這段集合的最大值。
dp[i]=Math.max(dp[i-1]+nums[i],nums[i])。eg:以3為下標，如果dp[2]為負數那肯定不加，加上拖后腿。如果dp[i-1]為正數，那肯定加。
代碼：
class Solution {public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE;int[] dp = new int[nums.length];//dp[0]和nums[0]相等dp[0] = nums[0];ans = dp[0];for (int i = 1; i < nums.length; i++){dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);ans = Math.max(dp[i], ans);}return ans;}
}三、買賣股票的最佳時機(一次遍歷)
暴力法搜索的話會超時異常
所以使用一次遍歷：每次遍歷到下標為i的元素時，就更新minprice。然后計算出在該天賣出，可以賺多少錢。
之前的思想是：如果在今天買，什么時候賣可以賺更多的錢。
現在的思想：如果今天賣，什么時候買可以賺更多錢。那我們就計算出今天之前的最小值，然后在那天買，今天賣，就可以找出最大利潤。
代碼：
class Solution {public int maxProfit(int[] prices) {int minprice = Integer.MAX_VALUE;int maxprofit = 0;for (int i = 0; i < prices.length; i++) {if (prices[i] < minprice) {minprice = prices[i];} else if (prices[i] - minprice > maxprofit) {maxprofit = prices[i] - minprice;}}return maxprofit;}
}
四、買賣股票的最佳時機II
給你一個整數數組?prices?，其中?prices[i]?表示某支股票第?i?天的價格。
在每一天，你可以決定是否購買和/或出售股票。你在任何時候?最多?只能持有?一股?股票。你也可以先購買，然后在?同一天?出售。返回?你能獲得的?最大?利潤。
?要求最大利潤->就要求從第二天開始每一天的利潤。
局部利潤最大->全局利潤最大
代碼：
class Solution {public int maxProfit(int[] prices) {int sumProfit=0;for(int i=1;i<prices.length;i++){if(prices[i]-prices[i-1]>0){sumProfit+=prices[i]-prices[i-1];}}return sumProfit;}
}五、跳躍游戲(回溯/貪心)
回溯法：
寬度為nums[i]的大小，表示可以最大跳多遠。for(int i=1;i<=nums[i]);i++)
深度就是跳到最后一個元素所經歷的節點個數。
返回值:boolean；參數:int[] nums,int startIndex,boolean[] used
終止條件：當startIndex==nums.length-1的時候，代表已經跳到了最后一個元素。如果>的話就跳超了，直接return false;
單層遞歸邏輯：
1.首先判斷該點是不是遇到過(去重)if(used[startIndex]==true)return false;
2.然后使用一個boolean的變量接收下一層遍歷的返回值，如果下一層返回true，那么這一層也返回true。如果下一層返回false,說明下一個不行，直接used[i+startIndex]=true
代碼：
class Solution {public boolean canJump(int[] nums) {if (nums.length == 1)return true;// 只有一個元素的時候boolean[] used = new boolean[nums.length];return backTracking(nums, 0, used);}public boolean backTracking(int[] nums, int startIndex, boolean[] used) {if (startIndex == nums.length - 1)return true;if (startIndex > nums.length - 1)return false;if (used[startIndex])return false;// 之前已經來過這個下標位置 已經試過這種情況了 就直接返回falsefor (int i = 1; i <= nums[startIndex]; i++) {boolean flag = backTracking(nums, startIndex + i, used);if (flag == true) {return true;} else {used[startIndex + i] = true;}}used[startIndex] = true;return false;}
}貪心法：
將跳躍問題->范圍覆蓋問題，如果在某點上，位置覆蓋到nums.length-1，那么就說明可以跳到最后一個位置，返回true;
在每次coverRange的范圍里面，去更新coverRange的范圍。coverRange=Math.max(coverRange,i+nums[i]);
if(coverRange>=nums.length-1)。為什么是>=而不是==。因為如果是>=的話，最后一個節點在我跳躍的范圍里面。
代碼：
class Solution {public boolean canJump(int[] nums) {if(nums.length==1)return true;int coverRange=0;//覆蓋的范圍是元素的下標 所以下面的for循環可以使用=for(int i=0;i<=coverRange;i++){coverRange=Math.max(coverRange,i+nums[i]);if(coverRange>=nums.length-1)return true;}return false;}
}六、跳躍游戲II(貪心)在上一道題的基礎上求最小跳躍次數
給定一個長度為?n?的?0 索引整數數組?nums。初始位置為?nums[0]。
每個元素?nums[i]?表示從索引?i?向前跳轉的最大長度。
返回到達?nums[n - 1]?的最小跳躍次數。生成的測試用例可以到達?nums[n - 1]。
思路：整體最優解：在一個范圍里面,每次都往最遠的跳。方式：在0->cur這個范圍里面，找到下一次可以跳躍到的最遠距離，next=Math.max(next,i+nums[i]);
如果cur!=nums.length-1,說明還沒有到達終點,那我們就要cur=next（改變范圍），并且result++
如果next==nums.length，result++然后跳
代碼：
class Solution {public int jump(int[] nums) {if(nums.length<=1)return 0;// 定義變量 cur next resultint cur = 0, next = 0, result = 0;for (int i = 0; i < nums.length; i++) {// 每次都更新一個范圍里下次能跳到的最遠距離next = Math.max(i + nums[i], next);if(next>=nums.length-1){result++;break;} if(i==cur){result++;cur=next;}}return result;}
}? 七、K次取反后最大化的數組和
貪心策略的選擇：
1.如果有負數的話，先對絕對值更大的負數進行取反，直到k為0；
2.如果所有的負數都取反完后，k不為0并且為奇數，就對最小的非負數進行取反。如果k為偶數，不用變。
注意：將數組從小到大排序之后，負數取反的值可能比之前的正數小，所以在取反并且k！=0后，要將數組再次排序。
代碼：
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);//先對nums進行排序int startK=k;for(int i=0;i<nums.length;i++){if(nums[i]<0&&k>0){nums[i]*=-1;k--;}}//如果k不為0并且k為一個奇數，就選擇一個最小的正數去抵消它if(k%2!=0){Arrays.sort(nums);nums[0]*=-1;}return sumOfArr(nums);}public int sumOfArr(int[] nums){int sum=0;for(int i:nums){sum+=i;}return sum;}
}八、加油站(貪心)
卡爾哥的思路：一個加油站可以a升，但是去下一個加油站要消耗b升,一個加油站可以獲取/消耗的油為（a-b），
1.使用變量curSum將它們累加起來，如果curSum<0，就說明汽油不夠到達下一個加油站。那么此時將curSum置為零(i也會從下一個開始）,
2.再使用一個變量totalSum將所有加油站的盈余都加起來，如果<0,就說明無論從哪一個起點開始都無法回到起點。
代碼：
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int gasSum=0;int totalSum=0;int index=0;for(int i=0;i<gas.length;i++){gasSum+=gas[i]-cost[i];//當前的累積量 如果<0 說明以i為起點的 無法循環totalSum+=gas[i]-cost[i];//總的累積量 如果<0 絕對找不到一個起點if(gasSum<0){index=(i+1)%gas.length;gasSum=0;}}if(totalSum<0)return -1;return index;}
}九、分發糖果(貪心法)
n?個孩子站成一排。給你一個整數數組?ratings?表示每個孩子的評分。
- 每個孩子至少分配到?
1?個糖果。 - 相鄰兩個孩子評分更高的孩子會獲得更多的糖果。
請你給每個孩子分發糖果，計算并返回需要準備的?最少糖果數目?。
問題：一個孩子所分發的糖果是由兩邊人共同影響的。eg:2 5 3? 2 。所分的糖果為1,2 但是第三個位置就不知道怎么確定了。
思路：先從左邊遍歷，再從右邊遍歷，遍歷到相同的位置要取最大值(因為同時要滿足兩個)
代碼：
class Solution {public int candy(int[] ratings) {int[] candies=new int[ratings.length];//首先我們從左往右遍歷candies[0]=1;for(int i=1;i<ratings.length;i++){if(ratings[i]>ratings[i-1])candies[i]=candies[i-1]+1;else candies[i]=1;}//我們從右往左遍歷for(int i=ratings.length-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candies[i]=Math.max(candies[i],candies[i+1]+1);}}return sumOfArr(candies);}public int sumOfArr(int[] candies){int sum=0;for(int i:candies){sum+=i;}return sum;}
}十、檸檬水找零(暴力)
暴力法：對bills[i]進行分情況判斷,==5/==10/==20。使用一個map集合當做錢包
1.等于5的時候，直接往map集合中添加
2.等于10的時候，先判斷5的是否>=1，然后更新一下5和10的數量
3.等于20的時候，優先使用5和10的進行支付，然后選擇三個5的進行支付。(因為5還要去支付10的)
代碼：
class Solution {public boolean lemonadeChange(int[] bills) {//使用一個map集合存錢Map<Integer, Integer> map = new HashMap();map.put(5,0);map.put(10,0);for (int i = 0; i < bills.length; i++) {if (bills[i] == 5) map.put(5, map.get(5) + 1);else if (bills[i] == 10) {if (map.get(5) >= 1) {map.put(5, map.get(5) - 1);map.put(10, map.get(10) + 1);} else {return false;}} else if (bills[i] == 20) {if(map.get(10)>0&&map.get(5)>0){map.put(10,map.get(10)-1);map.put(5,map.get(5)-1);}else if(map.get(5)>=3){map.put(5,map.get(5)-3);}else{return false;}}}return true;}
}十一、根據身高重建隊列（貪心）
Arrays.sort()函數中可以自定義一個comparator規則，一般使用Lambda表達式簡化書寫(我感覺可讀性不高)。
匿名內部類：（當我們只需要用一次的時候，就不需要再創建一個類，而是通過匿名內部類來實現）
例如：
public class Demo {public static void main(String[] args) {//創建匿名內部類，直接重寫父類的方法，省去了創建子類繼承，創建子類對象的過程Fu fu= new Fu(){@Overridepublic void method() { //重寫父類method方法super.method();}};fu.method(); //調用method方法}思路：將people[][]二維數組，通過Arrays.sort()排序。排序規則為:根據身高h排，即people[i][0]。
如果身高相等那么，根據前面的人：people[i][1]來排，升序排
第一種是普通的寫法/第二種是使用lambda表達式簡化開發
Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if(o1[0]==o2[0])return o1[1]-o2[1];return o2[0]-o1[0];}}); Arrays.sort(people,((o1, o2) -> {if(o1[0]==o2[0])return o2[1]-o2[0];return o2[0]-o1[0];//降序排}));排序好之后，根據people[i][k]來進行排序，k為多少就插到下標為多少的位置。
java中的集合直接封裝好了add(int index,T element)方法；
add(peo[1],peo);
代碼：
public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)->{if(a[0]==b[0])return a[1]-b[1];//如果身高相同 就比k k越小應該在越前面 所以是a-breturn b[0]-a[0];//降序排 是b-a});LinkedList<int[]> queue=new LinkedList<>();for(int[] peo:people){queue.add(peo[1],peo);}return queue.toArray(new int[people.length][]);}
