当前位置：首页 > article >正文

【贪心算法1】

article 2025/3/9 10:38:00

力扣455.分发饼干

链接: link

思路

尽可能让更多人吃到饼干并且尽可能少的造成浪费，大尺寸饼干能满足大胃口的人就应该优先分给大胃口的人。所以先将饼干和胃口大小排序，然后从后往前遍历。但是这时候又有一个问题，饼干和胃口哪个作为for循环哪个作为if呢？答案是只能胃口作为for，饼干作为if，因为for循环的i是固定每次移动，而饼干index只有满足条件才会移动。这里可以举一个反例，如果最大胃口大于最大的饼干，以饼干为for循环，胃口为if，那么for循环遍历下来，所有人都分不到饼干。

方法1:

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int index = s.length - 1;
        int cnt = 0;
        // 遍历胃口
        for(int i = g.length - 1;i>=0;i--){
            if(index>=0&&s[index]>=g[i]){
                cnt++;
                index--;
            }
        }
        return cnt;
    }
}

376.摆动序列
链接: link

思路

这道题看起代码简单，但是要考虑的情况很多，直接参考链接内容吧

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        // 当前节点 - 前一个节点
        int pre = 0;
        // 后一个节点 - 当前节点
        int next = 0;
        int res = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            next = nums[i + 1] - nums[i];
            // 出现峰值
            if ((pre >= 0 && next < 0) || (pre <= 0 && next > 0)) {
                res++;
                pre = next;
            }
        }
        return res;
    }
}

53.最大子数组和
链接: link

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int cnt = 0;
        for(int i = 0;i<nums.length;i++){
            cnt += nums[i];
            if(cnt>=sum){
                sum = cnt;
            }
            if(cnt<0){ // 注意 只有区间和为负数时才会重置
                cnt = 0;
            }
        }
        return sum;
    }
}