代碼隨想錄-035期-算法訓練營【博客筆記匯總表】-CSDN博客

第八章 貪心算法 part01● 理論基礎 
● 455.分發餅干 
● 376. 擺動序列 
● 53. 最大子序和 貪心算法其實就是沒有什么規律可言，所以大家了解貪心算法 就了解它沒有規律的本質就夠了。 不用花心思去研究其規律， 沒有思路就立刻看題解。基本貪心的題目 有兩個極端，要不就是特簡單，要不就是死活想不出來。  學完貪心之后再去看動態規劃，就會了解貪心和動規的區別。詳細布置 理論基礎 https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html  455.分發餅干  https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html  376. 擺動序列  https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html  53. 最大子序和  https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html  往日任務
● day 1 任務以及具體安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任務以及具體安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任務以及具體安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任務以及具體安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任務以及具體安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任務以及具體安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任務以及具體安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任務以及具體安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任務以及具體安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任務以及具體安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任務以及具體安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任務以及具體安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任務以及具體安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任務以及具體安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任務以及具體安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任務以及具體安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任務以及具體安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任務以及具體安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任務以及具體安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任務以及具體安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任務以及具體安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任務以及具體安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任務以及具體安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任務以及具體安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ  
●day 29 任務以及具體安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 
●day 30 任務以及具體安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR

目錄

理論基礎

0455_分發餅干

0376_擺動序列

0053_最大子序和

---

理論基礎

貪心的本質是選擇每一階段的局部最優，從而達到全局最優。

0455_分發餅干

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;import java.util.Arrays;public class _0455_分發餅干 {
}class Solution0455 {//思路1：優先考慮餅干，小餅干先喂飽小胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int start = 0;int count = 0;for (int i = 0; i < s.length && start < g.length; i++) {if (s[i] >= g[start]) {start++;count++;}}return count;}
}class Solution0455_2 {//思路2：優先考慮胃口，先喂飽大胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int start = s.length - 1;//遍歷胃口for (int index = g.length - 1; index >= 0; index--) {if (start >= 0 && g[index] <= s[start]) {start--;count++;}}return count;}
}

0376_擺動序列

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;public class _0376_擺動序列 {
}class Solution0376 {public int wiggleMaxLength(int[] nums) {if (nums.length <= 1) {return nums.length;}int curDiff = 0;//當前差值int preDiff = 0;//上一個差值int count = 1;for (int i = 1; i < nums.length; i++) {//得到當前差值curDiff = nums[i] - nums[i - 1];//如果當前差值和上一個差值為一正一負//等于0的情況表示初始時的preDiffif ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {count++;preDiff = curDiff;}}return count;}
}class Solution0376_2 {//DPpublic int wiggleMaxLength(int[] nums) {// 0 i 作為波峰的最大長度// 1 i 作為波谷的最大長度int dp[][] = new int[nums.length][2];dp[0][0] = dp[0][1] = 1;for (int i = 1; i < nums.length; i++) {//i 自己可以成為波峰或者波谷dp[i][0] = dp[i][1] = 1;for (int j = 0; j < i; j++) {if (nums[j] > nums[i]) {// i 是波谷dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);}if (nums[j] < nums[i]) {// i 是波峰dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);}}}return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);}
}

0053_最大子序和

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;public class _0053_最大子序和 {
}class Solution0053 {public int maxSubArray(int[] nums) {if (nums.length == 1) {return nums[0];}int sum = Integer.MIN_VALUE;int count = 0;for (int i = 0; i < nums.length; i++) {count += nums[i];sum = Math.max(sum, count);//取區間累計的最大值（相當于不斷確定最大子序終止位置）if (count <= 0) {count = 0;//相當于重置最大子序起始位置，因為遇到負數一定是拉低總和}}return sum;}
}class Solution0053_2 {//DP方法public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE;int[] dp = new int[nums.length];dp[0] = nums[0];ans = dp[0];for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);ans = Math.max(dp[i], ans);}return ans;}
}