代碼隨想錄算法訓(xùn)練營(yíng)day31 | 題目455、題目376辞色、題目53
題目一描述
假設(shè)你是一位很棒的家長(zhǎng)克伊，想要給你的孩子們一些小餅干伴栓。但是嚼鹉，每個(gè)孩子最多只能給一塊餅干袁滥。
對(duì)每個(gè)孩子 i星虹，都有一個(gè)胃口值 g[i]零抬，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j宽涌，都有一個(gè)尺寸 s[j] 平夜。如果 s[j] >= g[i]，我們可以將這個(gè)餅干 j 分配給孩子 i 卸亮，這個(gè)孩子會(huì)得到滿足忽妒。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值兼贸。
示例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個(gè)孩子和兩塊小餅干段直，3個(gè)孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干溶诞，由于他們的尺寸都是1鸯檬，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1螺垢。
示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個(gè)孩子和三塊小餅干喧务，2個(gè)孩子的胃口值分別是1,2赖歌。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(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;
}
}
題目二描述
如果連續(xù)數(shù)字之間的差嚴(yán)格地在正數(shù)和負(fù)數(shù)之間交替，則數(shù)字序列稱為 擺動(dòng)序列 坎穿。第一個(gè)差（如果存在的話）可能是正數(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è)差值為零隙袁。
子序列 可以通過從原始序列中刪除一些（也可以不刪除）元素來獲得痰娱，剩下的元素保持其原始順序。
給你一個(gè)整數(shù)數(shù)組 nums 菩收，返回 nums 中作為 擺動(dòng)序列 的 最長(zhǎng)子序列的長(zhǎng)度 梨睁。
示例 1：
輸入：nums = [1,7,4,9,2,5]
輸出：6
解釋：整個(gè)序列均為擺動(dòng)序列娜饵，各元素之間的差值為 (6, -3, 5, -7, 3) 坡贺。
示例 2：
輸入：nums = [1,17,5,10,13,15,10,5,16,8]
輸出：7
解釋：這個(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;
}
}
}
題目三描述
給你一個(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
解釋：連續(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è)元素開始重新尋找子序列，因?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;
}
}
