代码随想录算法训练营第二十七天

LeetCode.455 分发饼干

题目链接 分发饼干

题解

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int count = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        for(int i = 0;i < s.length && count < g.length;i++){
            if(s[i] >= g[count]){
                count ++;
            }
        }
        return count;
    }
}

解题思路

这段代码实现了 "分发饼干" 问题的解决方案，其核心思路是使用贪心算法来最大化能够满足的孩子数量。

代码逻辑解析：

1. 首先对孩子的胃口数组g和饼干尺寸数组s进行排序
2. 然后使用双指针的思想：
   • count变量既表示已满足的孩子数量，也作为指向当前需要满足的孩子的指针
   • 遍历饼干数组s，对于每个饼干s[i]
   • 如果当前饼干能满足当前孩子的胃口（s[i] >= g[count]），则满足这个孩子（count++）
   • 继续检查下一个饼干能否满足下一个孩子

这种解法的时间复杂度是 O (n log n + m log m)，其中 n 和 m 分别是两个数组的长度，主要消耗在排序操作上。空间复杂度是 O (1) 或 O (log n + log m)，取决于排序算法的实现。

该算法的贪心策略体现在：总是用最小的能满足孩子胃口的饼干去满足这个孩子，这样可以保留更大的饼干去满足可能有更大胃口的孩子，从而最大化满足的孩子总数。

LeetCode.376 摆动序列

题目链接 摆动序列

题解

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        int preDiff = 0;
        int curDiff = 0;
        int count = 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)){
                count ++;
                preDiff = curDiff;
            } 
        }
        return count;
    }
}

解题思路

这段代码实现了求解 "摆动序列" 最长长度的功能，所谓摆动序列是指序列中相邻元素的差值正负交替出现。

代码逻辑解析：

1. 边界处理：如果数组长度小于等于 1，直接返回数组长度（单个元素或空数组都是摆动序列）
2. 定义两个变量：
   • preDiff：记录前一对元素的差值
   • curDiff：记录当前对元素的差值
   • count：记录摆动序列的长度，初始值为 1（至少有一个元素）
3. 遍历数组，计算当前差值curDiff
4. 核心判断：如果当前差值与前一个差值符号相反（一正一负或一负一正），说明形成了摆动
   • 此时增加计数count++
   • 并更新preDiff为当前差值
5. 最后返回最长摆动序列的长度

这种解法的时间复杂度是 O (n)，只需要遍历一次数组；空间复杂度是 O (1)，只使用了几个额外变量。

算法的巧妙之处在于通过记录前后差值的符号变化来判断是否形成摆动，不需要额外存储整个序列，高效地完成了计算。

LeetCode.53 最大子序和

题目链接 最大子序和

题解

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            res = Math.max(sum,res);
            if(sum < 0) {
                sum = 0;
            }
        }
        return res;
    }
}

解题思路

这段代码实现了求解 "最大子数组和" 问题的解决方案，采用的是经典的贪心算法思路（也可以理解为 Kadane 算法的简化版本）。

代码逻辑解析：

1. 初始化res为数组的第一个元素，用于保存最大子数组和的结果
2. 初始化sum为 0，用于累积当前子数组的和
3. 遍历数组中的每个元素：
   • 将当前元素加入到sum中
   • 比较sum和res，更新res为两者中的较大值
   • 如果sum小于 0，说明继续累积当前子数组会导致和变小，因此重置sum为 0，从下一个元素开始重新累积

这种解法的时间复杂度是 O (n)，只需要遍历一次数组；空间复杂度是 O (1)，只使用了常数个额外变量。

算法的贪心策略体现在：当累积和为负数时，果断放弃当前子数组，重新开始计算，因为负数只会拉低后续子数组的和。这种策略确保了我们总能找到和最大的连续子数组。

例如，对于数组[-2,1,-3,4,-1,2,1,-5,4]，该算法会正确找到最大子数组[4,-1,2,1]，其和为 6。