LeetCode 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.
思路
這是一道十分典型貪心算法入門題目，題目要求每個孩子隻能給一塊餅幹，并且要求滿足較多的孩子，是以，我們可從最小的餅幹來滿足需求量最小的孩子開始配置設定，也就是将餅幹數組以及孩子需求數組進行從小到大的排序，并用 i，j 來分别訓示兩數組的目前下标，若可以滿足，則消耗一個餅幹，同時去除一個孩子，若不滿足，則根據常識，孩子是需求方，餅幹是消耗方，應停留在目前孩子，同時選下一個較大的餅幹（不能直接選下一個孩子，因為下一個孩子的需求更大），最終，隻要有一個數組周遊結束，那麼就需要結束并傳回結果。
這⾥的局部最優就是小餅⼲喂給需求小的，充分利⽤餅⼲尺⼨喂飽⼀個，全局最優就是喂飽盡可能多的⼩孩。
實作
public class TX1分發餅幹 {
public int findContentChildren(int[] g, int[] s) {
int num = 0;
int i = 0;
int j = 0;
Arrays.sort(g);
Arrays.sort(s);
while (i < g.length && j < s.length) {
if (g[i] <= s[j]) {
i++;
j++;
num++;
} else {
j++;
}
}
return num;
}
} 
LeetCode 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) 。
示例 3：
輸入：nums = [1,2,3,4,5,6,7,8,9]
輸出：2
思路
此題比較容易想到的思路就是先求出差集數組，判斷此差集數組的正負交替情況，并統計結果，但這種方法需要周遊兩次數組，但完全可以在一次周遊的同時，進行求差，正負擺動情況的統計，是以，我們周遊數組的同時，計算出目前一對數的內插補點，并事先記錄好前一對數的內插補點，進行符号相異的判斷，判斷成功則記錄一次序列數量，因為兩兩判斷，考慮首或尾的單獨情況，還應再多記錄一次。
下面實作中的：pre >=0 和 pre <= 0，僅是為第一次判斷時提供周遊，進而使代碼更統一。
而更新前一對的內插補點，也就是：pre = now，必須放在 if 判斷的裡面，也就是在成功記錄一次序列數量時才可以執行，放在外面的話送出就不會通過，對于這一點我是十分想不通。
局部最優：删除單調坡度上的節點（不包括單調坡度兩端的節點），那麼這個坡度就可以有兩個局部峰值。
整體最優：整個序列有最多的局部峰值，從⽽達到最⻓擺動序列。
實際操作上，其實連删除的操作都不⽤做，因為題⽬要求的是最⻓擺動⼦序列的⻓度，是以隻需要統計數組的峰值數量就可以了（相當于是删除單⼀坡度上的節點，然後統計⻓度）這就是貪⼼所貪的地⽅，讓峰值盡可能的保持峰值，然後删除單⼀坡度上的節點——此部分解釋，學習自公衆号：代碼随想錄。
實作
public class TX2擺動序列 {
public int wiggleMaxLength(int[] nums) {
int len = nums.length;
if (len <= 1) {
return len;
}
int count = 1;
int now = 0; //目前這對的內插補點
int pre = 0; //前一對的內插補點
//周遊的同時，求差，統計
for (int i = 0; i < len - 1; i++) {
//得到目前對的內插補點
now = nums[i + 1] - nums[i];
//與前一對的內插補點進行判斷
if ((now > 0 && pre <= 0) || (now < 0 && pre >= 0)) {
count++;
//更新前一對的內插補點
pre = now;
}
}
return count;
}
public static void main(String[] args) {
TX2擺動序列 s = new TX2擺動序列();
System.out.println("s.wiggleMaxLength(new int[]{1,2,3,4,5,6,7,8,9}) = " + s.wiggleMaxLength(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}));
System.out.println("s.wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8}) = " + s.wiggleMaxLength(new int[]{1, 17, 5, 10, 13, 15, 10, 5, 16, 8}));
//子序列為：[1, 17, 5, 15, 5, 16, 8]
System.out.println("s.wiggleMaxLength(new int[]{1,7,4,9,2,5}) = " + s.wiggleMaxLength(new int[]{1, 7, 4, 9, 2, 5}));
System.out.println("s.wiggleMaxLength(new int[]{0,0,0}) = " + s.wiggleMaxLength(new int[]{0, 0, 0}));
}
}