首页 > 编程语言 >代码随想录算法训练营第三十一天 | 455.分发饼干 376.摆动序列 53.最大子数组和

代码随想录算法训练营第三十一天 | 455.分发饼干 376.摆动序列 53.最大子数组和

时间:2024-06-07 22:23:23浏览次数:29  
标签:nums int 随想录 455 53 ++ startIndex 差值 size

455.分发饼干

题目链接 文章讲解 视频讲解

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = 0;
        // 从最小的饼干开始遍历
        for(int i = 0; i < s.size(); ++i) {
            // 尽量选取胃口小的小朋友,如果满足那么进行到下一个小朋友(++index)
            if(index < g.size() && g[index] <= s[i]) {
                ++index;
            }
            // 如果不满,选取下一块更大的饼干
        }
        return index;
    }
};

376.摆动序列

题目链接 文章讲解 视频讲解

思路:
如果nums.size() == 1; 则返回1
找到第一组差值不为0的元素,如果全部差值均为0,返回1
否则初始化length和maxLength为2(因为已经有一组差值不为0的元素,所以初始化为2)
如果当前差值和前一个差值相乘为负数则length++更新maxLength
否则跳过,继续循环;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1) return 1;

        // 记录前一个差值
        int pre;
        // 记录第一个插值不为0的起始位置
        int startIndex = 1;
        // 从第一个插值不为零的地方开始
        for(; startIndex < nums.size(); ++startIndex) {
            if(pre = nums[startIndex] - nums[startIndex - 1]) break;
        }
        // 如果插值全部为零,则返回1
        if(startIndex == nums.size()) return 1;


        int length = 2;
        int maxLength = 2;
        for(int i = startIndex; i < nums.size(); ++i) {
            int temp = nums[i] - nums[i - 1];
            // 前一个差值和后一个差值相乘为负数则说明是摆动序列
            if(temp * pre < 0) {
                length++;
                if(length > maxLength) maxLength = length;
                pre = temp;
            } 
            // 如果不是摆动的则直接跳过     
        }
        return maxLength;
    }
};

53.最大子数组和

题目链接 文章讲解 视频讲解

思路:如果连续和为负数的话,直接从下一个数开始,因为此时 连续和 + 当前值 < 当前值;所以将连续和置为当前值,继续累加

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = INT_MIN;
        // 记录连续和
        int sum = 0;
        for(int i = 0; i < nums.size(); ++i) {
            // 如果连续和小于0则,重新开始记录
            if(sum < 0) sum = 0;
            sum += nums[i];
            maxSum = max(sum, maxSum);
        }
        return maxSum;
    }
};

标签:nums,int,随想录,455,53,++,startIndex,差值,size
From: https://www.cnblogs.com/cscpp/p/18237949

相关文章

  • 代码随想录第3天 | 链表 203.移除链表元素,707.设计链表,206.反转链表
    题目:203.移除链表元素思路:主要是头节点的删除问题,一种是直接在原链表上后移头节点设置虚拟头结点,指向原链表的头结点,在设置一个cur指针指向当前节点,虚拟头节点初始化后就不移动了,使用cur进行移动不要忘记释放删除节点的内存,自行设置的虚拟头节点也要释放时间复杂度:O(n)空......
  • 代码随想录训练营第三天 | 203.移除链表元素 707.设计链表 206.反转链表
    python定义链表val:数据域,节点存储的元素。next:指针域,指向下一个节点的指针,最后一个节点指向None表示空指针。点击查看代码classListNode:def__init__(self,val,next=None):self.val=valself.next=next203.移除链表元素题目:给你一个链表的......
  • 代码随想录算法训练营第30天|回溯复习篇
    回溯基础理论1.回溯的本质是利用递归进行暴力搜索,将符和条件的结果集搜索出来2.回溯法常见的问题:组合问题:N个数里面按一定规则找出k个数的集合排列问题:N个数按一定规则全排列,有几种排列方式切割问题:一个字符串按一定规则有几种切割方式子集问题:一个N个数的集合里有多少符合......
  • SCT53600TVB具有反向电流保护的理想二极管控制器
     4.7V至65V工作范围· –65V反向额定电压· 用于外部N沟道MOSFET的电荷泵· 20mV正向压降调节· 12V栅极驱动电压· 带启用输入· 驱动高侧外部N沟道MOSFET· 1μA关断电流(EN=低)· 60μA工作静态电流(EN=高)· 2.3-A峰值门关断电流· 0.75us内快......
  • 代码随想录算法训练营第三十天 | 51.N 皇后
    51.N皇后题目链接文章讲解视频讲解递归三部曲递归函数参数需要传入当前chessBoard和棋盘大小n,以及当前要放置皇后的行数rowvoidbacktracking(vector<string>&chessBoard,intn,introw);递归终止条件当最后一个皇后放置好后结束if(row==n){result.push_b......
  • 1053页!企业数字化转型、数字驾驶舱、数据中台、数据湖、数据治理体系数字化平台方案WO
    企业数字化转型不仅意味着引入新的技术,更是一种战略选择,旨在提升效率、优化运营、挖掘新价值,以及构建持续竞争优势。本文将深入探讨企业数字化转型的重要性、挑战和关键策略。本文获取方式见文末。1053页为五篇WORD文档页数总和,获取方式见文末。企业数字化转型、数字驾驶舱......
  • LED大屏调试 异形灯板P1.53_208x104-52s
    模组信息:P1.53_INC2065+INC2018_208x104-52s智能设置:一.112*52区域1.选定芯片-译码-分辨率-芯片数72.3.4.5.6.7.查看灯板--保存灯板二.96*52区域选定芯片-译码-分辨率-芯片数6重复以上步骤,保存灯板三.构造箱体......
  • 代码随想录算法训练营第七天 | 四数之和、赎金信、三数之和、四数之和2
    代码随想录算法训练营第七天383赎金信https://leetcode.cn/problems/ransom-note/submissions/537782865/383赎金信代码随想录https://programmercarl.com/0383.赎金信.html#思路四数之和2https://leetcode.cn/problems/4sum-ii/四数之和2代码随想录https://programmerca......
  • 代码随想录算法训练营第八天 | 字符串:344反转字符串、
    反转字符串https://leetcode.cn/problems/reverse-string/反转字符串代码随想录https://programmercarl.com/0344.反转字符串.html#算法公开课反转字符串题目编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外......
  • 代码随想录算法训练营 第三天 链表 Leetcode203 移除链表元素 Leetcode707 设计链表 L
    Leetcode203移除链表元素 题目链接注意为了使后续节点方式统一 要人为设置链表头节点链表的处理一定要明白如何找前置节点/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*L......