代碼隨想錄算法訓(xùn)練營(yíng)day31 | 題目455、題目376、題目53

題目一描述

455. 分發(fā)餅干

假設(shè)你是一位很棒的家長(zhǎng)，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。

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

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

示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個(gè)孩子和三塊小餅干，2個(gè)孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿(mǎn)足。
所以你應(yīng)該輸出2.

提示：

1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

解題思路

貪心，統(tǒng)計(jì)能喂飽的人數(shù)即可。

代碼實(shí)現(xiàn)

方法一：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0;
        int j = 0;

        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                i++;
                j++;
            } else {
                j++;
            }
        }
        return i;
    }
}

題目二描述

376. 擺動(dòng)序列

如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替，則數(shù)字序列稱(chēng)為 擺動(dòng)序列 。第一個(gè)差（如果存在的話(huà)）可能是正數(shù)或負(fù)數(shù)。僅有一個(gè)元素或者含兩個(gè)不等元素的序列也視作擺動(dòng)序列。

例如， [1, 7, 4, 9, 2, 5] 是一個(gè) 擺動(dòng)序列 ，因?yàn)椴钪?(6, -3, 5, -7, 3) 是正負(fù)交替出現(xiàn)的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是擺動(dòng)序列，第一個(gè)序列是因?yàn)樗那皟蓚€(gè)差值都是正數(shù)，第二個(gè)序列是因?yàn)樗淖詈笠粋€(gè)差值為零。
子序列 可以通過(guò)從原始序列中刪除一些（也可以不刪除）元素來(lái)獲得，剩下的元素保持其原始順序。

給你一個(gè)整數(shù)數(shù)組 nums ，返回 nums 中作為 擺動(dòng)序列 的 最長(zhǎng)子序列的長(zhǎng)度 。

示例 1：
輸入：nums = [1,7,4,9,2,5]
輸出：6
解釋?zhuān)赫麄€(gè)序列均為擺動(dòng)序列，各元素之間的差值為 (6, -3, 5, -7, 3) 。

示例 2：
輸入：nums = [1,17,5,10,13,15,10,5,16,8]
輸出：7
解釋?zhuān)哼@個(gè)序列包含幾個(gè)長(zhǎng)度為 7 擺動(dòng)序列。
其中一個(gè)是 [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

提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000

進(jìn)階：你能否用 O(n) 時(shí)間復(fù)雜度完成此題?

解題思路

貪心，只統(tǒng)計(jì)有效的數(shù)量即可。

代碼實(shí)現(xiàn)

方法一：

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 1)
            return 1;
        int res = 1;
        int preFlag = -1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                if (preFlag == -1) {
                    preFlag = check(nums[i], nums[i - 1]);
                    res++;
                }
                if (preFlag != check(nums[i], nums[i - 1])) {
                    res++;
                }
                preFlag = check(nums[i], nums[i - 1]);
            }
        }
        return res;
    }

    private int check(int a, int b) {
        if (a - b > 0) { // 遞減
            return 0;
        } else { // 遞增
            return 1;
        }
    }
}

題目三描述

53. 最大子數(shù)組和

給你一個(gè)整數(shù)數(shù)組 nums ，請(qǐng)你找出一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
子數(shù)組 是數(shù)組中的一個(gè)連續(xù)部分。

示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋?zhuān)哼B續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。

示例 2：
輸入：nums = [1]
輸出：1

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

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

進(jìn)階：如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的 分治法 求解。

解題思路

貪心法，每次子序列之和為負(fù)數(shù)就停止增加新的元素，從下一個(gè)元素開(kāi)始重新尋找子序列，因?yàn)樨?fù)數(shù)加任何數(shù)都更小。
也可以用滑動(dòng)窗口，窗口縮小的條件就是窗口內(nèi)和為負(fù)，本質(zhì)是一樣的。

代碼實(shí)現(xiàn)

方法一：

class Solution {
    public int maxSubArray(int[] nums) {
        int curSum = 0;
        int res = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            res = Math.max(curSum, res);
            if (curSum < 0) {
                curSum = 0;
            }
        }
        return res;
    }
}

方法二：

class Solution {
    public int maxSubArray(int[] nums) {
        int curSum = 0;
        int res = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;

        while (right < nums.length) {
            curSum += nums[right];
            right++;

            res = Math.max(res, curSum);

            while (curSum < 0) {
                curSum -= nums[left];
                left++;
            }

        }
        return res;
    }
}