Day27- 贪心算法part01

发布时间:2024年01月15日

一、分发饼干

题目一:455. 分发饼干

455. 分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子?i,都有一个胃口值?g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干?j,都有一个尺寸?s[j]?。如果?s[j]?>= g[i],可以将这个饼干?j?分配给孩子?i?,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

算法的思路是尽可能地满足胃口最小的孩子,这样可以尽可能多地满足更多的孩子。

首先对孩子的胃口值和饼干尺寸进行排序。

然后遍历每块饼干,尝试找到能够满足当前胃口最小孩子的饼干。

如果找到了,就将这个孩子从列表中移除,并继续到下一块饼干,否则就检查下一块饼干。

g 是一个整数向量,表示每个孩子的胃口值

s 是另一个整数向量,表示每块饼干的尺寸。函数返回能满足的孩子的最大数量。

/*
 * @lc app=leetcode.cn id=455 lang=cpp
 *
 * [455] 分发饼干
 */

// @lc code=start
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        std::sort(g.begin(), g.end()); 
        std::sort(s.begin(), s.end()); 

        int child = 0, cookie = 0;
        while (child < g.size() && cookie < s.size()) {
            if (g[child] <= s[cookie]) {
                child++;
        }
        cookie++;
        }
        return child; 
    }
};
// @lc code=end

二、摆动序列

题目一:376. 摆动序列

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为?摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如,?[1, 7, 4, 9, 2, 5]?是一个?摆动序列?,因为差值?(6, -3, 5, -7, 3)?是正负交替出现的。

  • 相反,[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5]?不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

子序列?可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组?nums?,返回?nums?中作为?摆动序列?的?最长子序列的长度?。

贪心算法的核心思想是遍历数组,记录每次数字序列摆动的变化(即差值由正变负或由负变正),不需要关心摆动的具体大小,只需要知道它是上升还是下降。

nums 是一个整数数组,函数返回作为摆动序列的最长子序列的长度。

首先检查数组长度,如果长度小于2,则直接返回数组长度。

然后使用两个变量,一个用来存储前一个差值 prevDiff,另一个用于计数摆动序列的长度。

接着遍历数组,对于每个新的差值,如果它和前一个差值构成摆动,就更新计数器和 prevDiff

最后返回计数器的值作为最长摆动序列的长度。

/*
 * @lc app=leetcode.cn id=376 lang=cpp
 *
 * [376] 摆动序列
 */

// @lc code=start
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2) {
            return nums.size();
        }
        int prevDiff = nums[1] - nums[0];
        int count = prevDiff != 0 ? 2 : 1;
        for (int i = 2; i < nums.size(); ++i) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
                count++;
                prevDiff = diff;
            }
        }
        return count;
    }
};
// @lc code=end

三、最大子数组和

题目一:53. 最大子数组和

53. 最大子数组和

给你一个整数数组?nums?,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组?是数组中的一个连续部分。

贪心算法的实现更加强调在和变为负数时的决策。当当前子数组的和小于0时,意味着它对于后续子数组的和只会有负面影响,因此应该从下一个元素开始重新计算子数组的和。

在这段代码中,遍历数组 nums,不断更新 currentSum

如果 currentSum 变成负数,将其重置为0,并从下一个元素开始计算新的子数组和。

同时持续追踪并更新遇到的最大子数组和 maxSum

最后返回 maxSum 作为答案。

/*
 * @lc app=leetcode.cn id=53 lang=cpp
 *
 * [53] 最大子数组和
 */

// @lc code=start
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int currentSum = 0;

        for (int num : nums) {
            currentSum += num;
            maxSum = std::max(maxSum, currentSum);

            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        return maxSum;
    }
};
// @lc code=end

文章来源:https://blog.csdn.net/m0_66690787/article/details/135601900
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。