455. 分配 Cookie
假設您是一位很棒的父母，想給您的孩子一些餅乾。但是，您最多應該給每個孩子一塊餅乾。
每個孩子 i 都有貪婪因子 g[i]，這是孩子會滿意的 cookie 的最小大小；每個 cookie j 的大小為 s[j]。如果 s[j] >= g[i]，我們可以將 cookie j 指派給子 i，而子 i 將是內容。您的目標是最大化內容子層級的數量並輸出最大數量。
範例1：
輸入：g = [1,2,3], s = [1,1]
輸出：1
說明：您有 3 個孩子和 2 個餅乾。 3個孩子的貪婪因子分別是1,2,3。
即使你有 2 個餅乾，由於它們的大小都是 1，所以你只能製作貪婪因子為 1 的孩子的內容。
您需要輸出 1.
範例2：
輸入：g = [1,2], s = [1,2,3]
輸出：2
說明：您有 2 個孩子和 3 個餅乾。 2個孩子的貪婪因子是1, 2。
你有 3 塊餅乾，它們的大小足以滿足所有孩子的需求，
你需要輸出2。
限制：
1
0
1
public int findContentChildren(int[] g, int[] s) {
// avoid null pointer
if(g.length == 0 || s.length ==0){
return 0;
}
// 2 * nlogn
Arrays.sort(g);
Arrays.sort(s);
int i = 0;
int j = 0;
int count = 0;
while(i < g.length && j < s.length){
if(g[i] <= s[j]){
i++;
j++;
count++;
} else{
j++;
}
}
return count;
}
登入後複製
時間：n`logn
另一個版本的for迴圈
`
public int findContentChildren(int[] g, int[] s) {
// 避免空指標
if(g.length == 0 || s.length ==0){
回傳 0;
}
// 2 * nlogn
Arrays.sort(g);
Arrays.sort(s);
int j = 0;
int count = 0;
for(int i=0; i<s.length && j<g.length; i++){
if(s[i] >= g[j]){
j++;
count++;
}
}
return count;
}
登入後複製
`
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
解釋：有幾個子序列可以達到這個長度。
一個是 [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
0
跟進：你能在 O(n) 時間內解決這個問題嗎？
`
public int wiggleMaxLength(int[] nums) {
if(nums.length == 0){
回傳 0;
}
整數計數 = 1;
int preFlag = 0;
int pre = nums[0];
for(int i=1; i<nums.length; i++){
if(nums[i]-nums[i-1] != 0){
int flag = (nums[i]-nums[i-1])/Math.abs(nums[i]-nums[i-1]);
if(flag == -preFlag || preFlag == 0){
preFlag = flag;
count++;
}
}
}
return count;
}
登入後複製
`
53. 最大子數組
給定一個整數數組 nums，求
子數組
最大的和，並返回其和。
範例1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：子數組 [4,-1,2,1] 的和最大為 6。
範例2：
輸入：nums = [1]
輸出：1
解釋：子數組 [1] 的和最大為 1。
範例 3：
輸入：nums = [5,4,-1,7,8]
輸出：23
解釋：子數組 [5,4,-1,7,8] 的和最大為 23。
限制：
1
-104
後續：如果您已經找到了 O(n) 解決方案，請嘗試使用分而治之的方法編寫另一個解決方案，這種方法更微妙。
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
回傳 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0;我
if(nums[i] > 0){
if(總和
sum = nums[i];
}其他{
sum += nums[i];
}
max = Math.max(max, sum);
}else{
if(sum<0){
sum = nums[i];
}else{
sum += nums[i];
}
max = Math.max(max, sum);
}
}
return max;
}
登入後複製
`
improve code
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0; i
if(sum < 0){
sum = nums[i];
}else{
sum += nums[i];
}
max = Math.max(max, sum);
}
return max;
}
登入後複製
`
Another way for greedy
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
// int sum = Integer.MIN_VALUE;
int sum = 0;
for(int i=0; i<nums.length; i++){
sum+= nums[i];
if(max < sum){
max = sum;
}
if(sum <0){
sum = 0;
}
// if(sum < 0){
// sum = nums[i];
// }else{
// sum += nums[i];
// }
// max = Math.max(max, sum);
}
return max;
}
登入後複製
`
以上是LeetCode Day 貪心演算法 第 1 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！
