day31 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

● 455.分发饼干
● 376. 摆动序列
● 53. 最大子序和

在本次的题目中，我们使用了贪心算法来解决三个问题：分发饼干、摆动序列、最大子序和。这三个问题都可以使用贪心算法来解决，而且贪心算法的时间复杂度相对较低，能够在较短的时间内得出解决方案。

1. 分发饼干

题目描述：有一群孩子和一些饼干，每个孩子有一个贪心因子g，每个饼干有一个大小s。只有当一个孩子的贪心因子小于等于饼干的大小时，这个孩子才能获得这个饼干。求最多能满足多少个孩子。

贪心思路：首先将孩子的贪心因子g和饼干的大小s从小到大排序，然后从贪心因子最小的孩子开始，依次判断每个孩子是否能够获得一块饼干。如果可以获得，则将饼干的大小s++，继续判断下一个孩子是否能够获得饼干。如果不能获得，则继续寻找下一个大小更大的饼干，直到找到一个能够满足当前孩子的饼干或者没有更大的饼干为止。

Java代码如下：

public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int i = 0, j = 0;int count = 0;while (i < g.length && j < s.length) {if (g[i] <= s[j]) {count++;i++;j++;} else {j++;}}return count;
}

2. 摆动序列

题目描述：给定一个整数序列，你的任务是找到其中最长的摆动子序列的长度。摆动序列的定义：如果连续元素之间的差的正负性交替出现，则称这样的序列为摆动序列。

贪心思路：从序列的第一个数开始，判断当前数与下一个数之间的差的正负性。如果这两个数之间的差为正，则说明下一个数应该比当前数大；如果这两个数之间的差为负，则说明下一个数应该比当前数小。如果这两个数之间的差为0，则说明这两个数相等，直接跳过。通过这样的方式，每次找到一个摆动序列的峰值或者谷值，最终就能得到最长的摆动子序列的长度。

Java代码如下：

public int wiggleMaxLength(int[] nums) {if (nums.length < 2) {return nums.length;}int preDiff = 0;int curDiff = 0;int count = 1;for (int i = 1; i < nums.length; i++) {curDiff = nums[i] - nums[i - 1];if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {count++;preDiff = curDiff;}}return count;
}

3. 最大子序和

题目描述：给定一个整数序列，找到一个具有最大和的连续子序列（至少包含一个数）。

贪心思路：从序列的第一个数开始，依次将每个数加到当前的子序列中，并记录当前子序列的最大值和当前子序列的和。如果当前子序列的和小于0，则说明当前子序列已经不可能是最大的连续子序列了，需要重新开始寻找从下一个数开始的子序列。通过这样的方式，每次找到一个最大的连续子序列的和，最终就能得到整个序列中的最大子序和。

Java代码如下：

public int maxSubArray(int[] nums) {int maxSum = nums[0];int curSum = 0;for (int i = 0; i < nums.length; i++) {curSum += nums[i];if (curSum > maxSum) {maxSum = curSum;}if (curSum < 0) {curSum = 0;}}return maxSum;
}

贪心算法理论知识总结

贪心算法是一种解决最优化问题的算法，它是一种启发式算法，通过每一步的最优选择来达到整体的最优解。贪心算法的具体实现方法就是在每一步选择中都采取当前状态下最优的选择，从而希望得到全局最优解。

贪心算法的时间复杂度通常比较低，因为它每次只考虑当前状态下的最优解，不需要考虑全局的情况。但是，贪心算法并不能保证得到全局最优解，因为它每次都只考虑局部最优解，可能会导致整体上的局部最优解并不是全局最优解。

因此，在使用贪心算法时，需要确定一个贪心策略，即确定每一步的最优选择，以保证最终得到的解是全局最优解。同时，需要证明所采用的贪心策略是正确的，即证明每一步的最优选择可以推导出全局最优解。