Leecode 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(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end()); // 將餅干量和需求量進行排序
        sort(s.begin(), s.end());
        int i = 0; 
        int j = 0;
        int result = 0;
        while(i < g.size() && j < s.size()){ // 按照需求順序分配
            if(g[i] <= s[j++]){ // 如果滿足分配條件那就分配
                i++;
                result++;
            }
        }
        return result;
    }
};

Leecode 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

解題思路與代碼展示

本題要求序列中單調性反轉的次數，需要特別注意的是出現數相同的時候，并沒有發生反轉，如何處理其中的每種情況需要仔細討論。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size(); // 當數組中的個數小于等于1時的特殊情況
        int result = 1; // 反轉的最少次數就是1
        int up = 1; // 初始化up和down變量為1
        int down = 1;
        for(int i = 1; i < nums.size(); i++){ // 遍歷所有數組
            if(nums[i] > nums[i-1]) up = down + 1; // 每次兩個數只要不相等，那么就說明有可能出現反轉。但如果上一次的大小關系和本次一致，會導致up/down的值不變
            if(nums[i] < nums[i-1]) down = up + 1;
        }
        return max(up, down); // 最終的反轉次數就是up和down中的最大值
    }
};

使用上面代碼可以巧妙地計算出擺動序列的長度。

Leecode 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(vector<int>& nums) {
        int result = INT32_MIN; // 初始化為int類型中的最小值
        int count = 0; // 當子數組中沒有元素時，當前子數組和為0
        for(int i = 0; i < nums.size(); i++){ 
            count += nums[i]; // 每次都將一個新的數納入當前子數組中進行合并
            if(count > result) result = count; // 每次都將新的子數組的和與結果進行比較并保留最大值
            if(count <= 0) count = 0; // 如果當前子數組求和為0，那么說明此時往左的這一半子數組都不用再考慮，重置count=0相當于使得子數組為空
        }
        return result;
    }
};

上面代碼非常巧妙地解決了最大子數組和的問題。而且時間復雜度為\(O(n)\)。

今日總結

感覺這部分貪心的算法都很難想，難度有點大。另外，最近事情突然多起來了，馬上有兩場考試，同時還有論文的二審結果下來還需要進行小修，非常非常忙。這邊Leecode只能暫時擱置，現在就盡可能每天刷一道保持鋪地板吧...

今日Leecode已經95了，盡量在這周破100吧，再接再厲！