day 27 第八章 贪心算法 part01
第一题：455.分发饼干
解题思路
本题的核心目标是在给定孩子的胃口值数组 g 和饼干尺寸数组 s 的情况下，尽可能多地满足孩子的胃口，也就是找到能满足孩子数量的最大值。解题思路主要是基于贪心算法，以下是具体的分析：
-
整体思路：
贪心算法的核心在于在每一步选择中，都做出当前状态下的最优选择，希望通过局部最优解最终达到全局最优解。对于这道题，我们的贪心策略是优先尝试用较大尺寸的饼干去满足胃口较大的孩子，这样能最大程度地利用饼干，满足更多的孩子。 -
数组排序预处理：
首先对孩子的胃口值数组g和饼干尺寸数组s分别进行排序（通过Arrays.sort方法）。排序的目的是为了方便后续按照从大到小的顺序去匹配饼干和孩子，使得贪心策略能够更有序地实施。经过排序后，胃口值较大的孩子在g数组的后面部分，尺寸较大的饼干在s数组的后面部分。 -
遍历匹配过程：
从胃口值最大的孩子开始遍历g数组（通过for循环，从g.length - 1开始，逐步往前遍历，索引i递减），对于每一个孩子，去寻找是否有合适的饼干可以满足他的胃口。这里合适的意思就是饼干的尺寸s[j]要大于等于孩子的胃口值g[i]。同时，我们从尺寸最大的饼干开始找起，用一个变量start来标记当前可供选择的最大饼干的索引，初始化为s.length - 1（也就是s数组的最后一个元素的索引）。 -
匹配与计数：
在循环中，每次检查当前孩子（索引为i的孩子）时，如果start大于等于 0（表示还有饼干可供选择）且当前最大尺寸的饼干（索引为start的饼干）尺寸s[start]大于等于这个孩子的胃口值g[i]，那就说明可以用这块饼干来满足这个孩子。此时，将start的值减 1（表示这块饼干已经被使用了，下一次要考虑尺寸稍小一点的饼干了），同时将满足的孩子数量计数器count加 1，表示又多满足了一个孩子。 -
最终结果返回：
当遍历完所有孩子或者已经没有合适的饼干可供选择时（也就是for循环结束），count中记录的就是能够满足的孩子的最大数量，直接将其返回即可。
代码
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = s.length - 1;
for(int i = g.length - 1;i >= 0;i--){
if(start >= 0 && s[start] >= g[i]){
start--;
count++;
}
}
return count;
}
}第二题：376. 摆动序列
解题思路
本题要求找出给定整数数组 nums 中作为摆动序列的最长子序列的长度，解题思路主要基于贪心算法，通过依次比较相邻元素的差值来确定摆动序列的长度，以下是详细说明：
-
整体思路：
贪心算法在这里的体现就是，我们希望尽可能多地保留那些能让序列呈现出摆动特性（差值正负交替）的元素，每遇到一次符合摆动特征的相邻元素对，就认为可以增加摆动序列的长度。 -
边界情况处理：
首先判断如果输入的nums数组长度为 1，根据定义仅有一个元素的序列也视作摆动序列，所以直接返回 1 即可。 -
初始化变量：
定义prediff（前一个差值）和curdiff（当前差值）两个变量，初始时prediff设为 0，因为在还没开始比较差值时可以看作差值不存在或者说初始差值为 0。同时定义result用于记录摆动序列的长度，初始值设为 1，这是考虑到即使数组中只有一个元素或者从第二个元素开始就不符合摆动条件了，最少也有 1 个元素构成摆动序列（符合摆动序列定义中仅有一个元素也算的情况）。 -
遍历数组比较差值：
通过for循环从数组的第一个元素开始，依次遍历到倒数第二个元素（索引为i，循环条件是i < nums.length - 1），在循环中计算当前相邻两个元素的差值curdiff，即curdiff = nums[i + 1] - nums[i]。 -
判断摆动条件并更新长度与差值记录：
接着判断当前差值curdiff和前一个差值prediff是否满足摆动序列的条件，也就是判断(prediff >= 0 && curdiff <= 0) || (prediff <= 0 && curdiff >= 0)是否成立。如果成立，说明当前这对相邻元素构成了摆动特性（差值正负交替了），那么就将摆动序列的长度result加 1，表示找到了一个可以增加摆动序列长度的元素对。同时，把当前的curdiff赋值给prediff，因为下一次比较时，这次的curdiff就变成前一个差值了，这样不断更新来持续判断后续元素是否还能继续构成摆动序列。 -
最终结果返回：
当循环遍历完整个数组（除了最后一个元素，因为是通过比较相邻元素的差值来判断，最后一个元素没办法再往后比较差值了）后，result中记录的就是整个数组nums中作为摆动序列的最长子序列的长度，直接返回result即可。
代码
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length == 1){
return 1;
}
int prediff = 0;
int curdiff = 0;
int result = 1;
for(int i = 0;i < nums.length - 1;i++){
curdiff = nums[i + 1] - nums[i];
if( (prediff >=0 && curdiff <= 0) ||(prediff <=0 && curdiff >= 0) ){
result++;
prediff = curdiff;
}
}
return result;
}
}第三题：53. 最大子序和
解题思路
本题要求找出给定整数数组 nums 中具有最大和的连续子数组，并返回其最大和，解题思路主要基于贪心算法，核心思想是在遍历数组的过程中，尽可能选择能让累加和变得更大的连续部分，以下是详细说明：
-
整体思路：
贪心算法在此处的体现是，我们在遍历数组时，每一步都基于当前的情况做出局部最优选择，即只要当前连续子数组的累加和是正数，就有可能对后续形成更大的和有帮助，那就继续累加；而一旦累加和变为负数了，那它对于后续求最大和就没有好处了，此时就舍弃之前的累加结果，重新开始计算新的连续子数组的和，通过这样不断地选择，最终找到整个数组中的最大子数组和。 -
边界情况处理：
首先判断如果输入的nums数组长度为 1，那么这个唯一的元素构成的子数组就是我们要找的子数组，直接返回这个元素（也就是nums[0]）即可。 -
初始化变量：
定义sum用于记录当前找到的最大子数组和，初始化为Integer.MIN_VALUE，这样做是为了确保后续计算得到的任何和都能与它比较并更新，无论初始的数组元素情况如何。定义count用于记录当前连续子数组的累加和，初始值为 0。 -
遍历数组并更新累加和与最大和：
通过for循环从数组的第一个元素开始，依次遍历整个数组（索引为i）。在循环中，先将当前元素nums[i]累加到count中（通过count += nums[i]），表示当前连续子数组的和在不断更新。 -
比较并更新最大子数组和：
接着比较当前的累加和count与已记录的最大子数组和sum的大小，如果count大于sum，那就说明找到了一个更大的子数组和，将sum更新为count的值（通过if(count > sum) sum = count;），这样sum始终记录着到当前位置为止所发现的最大子数组和。 -
处理累加和为负的情况：
然后判断如果当前的累加和count小于 0，意味着从当前位置往前的这部分连续子数组对后续求最大和已经没有积极作用了（因为加上它只会让和变小），所以将count重置为 0（通过if(count < 0) { count = 0; }），相当于舍弃这部分连续子数组，重新开始寻找新的可能构成更大和的连续子数组。 -
最终结果返回：
当循环遍历完整个数组后，sum中记录的就是整个数组nums中具有最大和的连续子数组的和，直接返回sum即可。
代码
class Solution {
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 > sum) sum = count;
if(count < 0){
count = 0;
}
}
return sum;
}
}
原文地址：https://blog.csdn.net/m0_72789504/article/details/144041725
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！