代碼隨想錄：貪心2-4

455.分發餅干

題目

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子?i，都有一個胃口值?g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干?j，都有一個尺寸?s[j]?。如果?s[j]?>= g[i]，我們可以將這個餅干?j?分配給孩子?i?，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值。

示例?1:

輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋: 
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應該輸出1。

示例?2:

輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋: 
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數量和尺寸都足以讓所有孩子滿足。
所以你應該輸出2.

代碼（控制餅干，從小到大分）

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g); //胃口Arrays.sort(s); //餅干int index = 0;  //胃口int count = 0;  //滿足的小孩數量//用for循環控制餅干1357的原因是：從小到大，給每一個餅干找小孩//如果這個餅干可以滿足小孩就給出去，如果滿足不了，餅干太小了就輪空不給//不管餅干有沒有被分出去，都需要判斷下一個餅干了//從小到大分餅干，for循環控制餅干，1357for(int i=0; i < s.length; i++){//這個餅干可以滿足胃口if(index  < g.length && g[index] <= s[i]){ //while控制胃口246count++;index++; //胃口滿足，往后給下一個小孩}//如果餅干太小滿足不了，比如餅干1不要了，i++，從下一個餅干開始給}return count;}
}

代碼（控制胃口，從大到小分）

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g); //胃口Arrays.sort(s); //餅干int index = s.length - 1;  //餅干int count = 0;  //滿足的小孩數量//用for控制胃口1357的原因是，從大到小，對每一個小孩找餅干//如果有足夠大餅干就給他，沒有的話這個小孩就被輪空不吃//小孩的胃口不過有沒有滿足，都需要找下一個小孩子了//for循環控制胃口，從大到小滿足小孩胃口for(int i = g.length-1; i >= 0; i--){ //胃口1357//有滿足當前最大胃口的餅干if(index >= 0 && g[i] <= s[index]){    //控制餅干246，從后往前給餅干count++;index--;  //餅干分出去了，往前指向前一個餅干}//胃口太大，沒有滿足的餅干，別吃了，比如胃口7，i--直接找下一個小孩}return count;}
}

總結

? ? ? ? 兩種邏輯，一種是控制胃口，從大到小分，一種是控制餅干，從小到大分。

? ? ? ? 1、控制胃口，從大到小分

????????用for控制胃口1357的原因是，從大到小，對每一個小孩找餅干246。如果有足夠大餅干就

他，沒有的話這個小孩就被輪空不吃。小孩的胃口不管有沒有滿足，都需要找下一個小孩子了。

? ? ? ? 比如第一個小孩胃口7，餅干6滿足不了，他就被輪空吃不到，for循環i--，找下一個胃口小

孩。但是餅干沒有分出去還是指向6。

? ? ? ? 2、控制餅干，從小到大分

????????用for控制餅干1357的原因是，從小到大，對每一個餅干找小孩246。如果這個餅干可以滿足

當前小孩就分出去，滿足不了的話這個餅干就被輪空分不出去。餅干不管有沒有分出去，都需要找

下一個餅干了。

? ? ? ? 比如第一個餅干1，小孩胃口2滿足不了，餅干就被輪空分不出去，for循環i++，找下一個餅

干。但是小孩沒有拿到餅干指向2。

總結：for循環控制的邏輯就是，被輪空的不用管的在for循環里。

從大到小從胃口找餅干，大胃口可能被輪空，需要用for循環控制，胃口太大就算了不吃了。

從小到大從餅干找胃口，小餅干可能被輪空，需要用for循環控制，餅干太小就算了不分了。

????????

? ? ??

376.擺動序列

題目

如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為?擺動序列。第一個差（如果存在的話）可能是正數或負數。僅有一個元素或者含兩個不等元素的序列也視作擺動序列。

例如，?[1, 7, 4, 9, 2, 5]?是一個?擺動序列?，因為差值?(6, -3, 5, -7, 3)?是正負交替出現的。
相反，[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5]?不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零。

子序列?可以通過從原始序列中刪除一些（也可以不刪除）元素來獲得，剩下的元素保持其原始順序。

給你一個整數數組?nums?，返回?nums?中作為?擺動序列?的?最長子序列的長度?。

示例 1：

輸入：nums = [1,7,4,9,2,5]
輸出：6
解釋：整個序列均為擺動序列，各元素之間的差值為 (6, -3, 5, -7, 3) 。

示例 2：

輸入：nums = [1,17,5,10,13,15,10,5,16,8]
輸出：7
解釋：這個序列包含幾個長度為 7 擺動序列。
其中一個是 [1, 17, 10, 13, 10, 16, 8] ，各元素之間的差值為 (16, -7, 3, -3, 6, -8) 。

代碼

class Solution {public int wiggleMaxLength(int[] nums) {//nums長度為1直接返回if(nums.length == 1){return 1;}int count = 1; //i=0是長度直接算上int pre = 0;int cur = 0;for(int i=1; i < nums.length; i++){cur = nums[i] - nums[i-1];//這里要特別注意，不能寫成pre*cur<0或pre*cur<=0//如果寫成pre*cur<0，i=1，pre為0，前兩個數就判斷失敗了//如果寫成pre*cur<=0，可能序列是133333，是cur=0，不能算是滿足條件的序列//所以不僅僅要求pre和cur異號，還要考慮前兩個數判斷時pre=0的情況，但cur不能為0if(pre <= 0 && cur > 0 || pre >= 0 && cur < 0){count++;pre = cur;  //更新pre為當前的差值}//如果當前i的cur不滿足條件，這個nums[i]就自動不算在序列中了}return count;}
}

總結

? ? ? ? 用pre和cur分別表示前面的差值和當前的差值。如果pre和cur滿足條件，就讓count++，表示

序列長度加1，但是如果不滿足條件，就跳過當前序列位置，繼續往后面判斷。比如1543218。154

滿足count=3，但是321的cur和54的pre同號都小于0，所有321都不能算，count不會計數，最后8

滿足，54的pre<0,48的cur大于0，滿足條件，最后count=4。

? ? ? ? 我們希望pre和cur是異號的，簡單考慮是pre*cur<0，但這樣寫會出錯。因為序列132,初始

count=1，從3開始遍歷，pre=0，cur=3-1=2，這最開始的兩個數字，pre=0，需要單獨考慮。也不

能簡單寫成pre*cur<=0,因為我們不運行cur=0，即序列1322222,后面重復的2都不能算。

? ? ? ? 所以判斷序列滿足條件應該寫成pre <= 0 && cur > 0 || pre >= 0 && cur < 0，然后count++，

再令pre=cur,序列繼續往后判斷。

53.最大子數組和

題目

給你一個整數數組?nums?，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

子數組

是數組中的一個連續部分。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組?[4,-1,2,1] 的和最大，為?6 。

示例 2：

輸入：nums = [1]
輸出：1

示例 3：

輸入：nums = [5,4,-1,7,8]
輸出：23

代碼

class Solution {public int maxSubArray(int[] nums) {int res = Integer.MIN_VALUE;  //初始化res為最小整數int count = 0;for(int i=0; i < nums.length;i++){count += nums[i];  //count是序列累加和//如果累加和大于res，更新resif(count > res){res = count;}//如果count小于0，說明前面的序列起副作用，不要了if(count < 0){count = 0;}}return res;}
}