自学内容网 自学内容网

打卡第二十七天 455分发饼干 376摆动序列

第一题:

原题链接:455. 分发饼干 - 力扣(LeetCode)

思路:

将大的饼干来满足胃口大的孩子。

先将小孩子的胃口和饼干的尺寸进行排序。然后从后往前遍历胃口,饼干的尺寸也从后往前。如果饼干尺寸大于等于小孩胃口,res++,然后比较下一块饼干。

代码如下:

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int res = 0;
        int index = s.size() - 1;
        for(int i = g.size() - 1; i >= 0; i--){
            if(index >= 0 && s[index] >= g[i]){
                res++;
                index--;
            }
        }
        return res;
    }
};

第二题:

原题链接:376. 摆动序列 - 力扣(LeetCode)

思路:

首元素和尾元素都算摆动

考虑三种情况:

第一种是上下坡有平坡

第二种是首尾元素,直降将尾元素记录为1;

第三种是单调坡有平坡。

整体的思路是prediff >= 0 && curdiff < 0 || prediff <= 0 && curdiff > 0 就证明是摆动。

第三种情况就是当有坡度的时候才更行prediff的值。

代码如下:

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1) return 1;
        int res = 1;
        int prediff = 0;
        int curdiff = 0;
        for(int i = 0; i < nums.size() - 1; i++){
            curdiff = nums[i + 1] - nums[i];
            if(prediff >= 0 && curdiff < 0 ||
               prediff <= 0 && curdiff > 0){
                res++;
                prediff = curdiff;
            }
        }
        return res;
    }
};

第三题:

原题链接:53. 最大子数组和 - 力扣(LeetCode)

思路:

当前连续子数组的和如果小于0就直接从下一个元素进行计算。切记不能遇到负数就跳过。用res记录每次的遍历的最大和。

代码如下:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int count = 0;
        for(int i = 0; i < nums.size(); i++){
            count += nums[i];
            if(count > res) res = count;
            if(count < 0) count = 0;
        }
        return res;
    }
};


原文地址:https://blog.csdn.net/weixin_44593575/article/details/140164162

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!