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

455.分发饼干

题目

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

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

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1 解释:你有三个孩子和两块小饼干,3 个孩子的胃口值分别是:1,2,3。虽然你有两块小饼干,由于他们的尺寸都是 1,你只能让胃口值是 1 的孩子满足。所以你应该输出 1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释:你有两个孩子和三块小饼干,2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.

解题思路

  • 对两个数组进行排序
  • 为尽量满足更多的小孩的胃口,优先用小饼干满足胃口最小的小孩。

代码

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++) { // 饼干if(index < g.size() && g[index] <= s[i]){ // 胃口index++;}}return index;}
};

376.摆动序列

题目

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。

例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

解题思路

  • 其实就是,数字相邻之前要一大一小。类似于正弦函数图,波峰波谷交替
    在这里插入图片描述
  • 那只要记录当前差值和上一次比较的差值,如果满足两者互为正负数,那么记录结果的长度即可

代码

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size();int curDiff = 0; // 当前一对差值int preDiff = 0; // 前一对差值int result = 1;  // 记录峰值个数,序列默认序列最右边有一个峰值for (int i = 0; i < nums.size() - 1; i++) {curDiff = nums[i + 1] - nums[i];// 出现峰值if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {result++;preDiff = curDiff; // 注意这里,只在摆动变化的时候更新prediff}}return result;}
};

53. 最大子序和

题目

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6

解题思路

  • 使用暴力for循环可以解决,滑动窗口找到所有的子序列,然后找最大和的子序列即可
  • 如果使用贪心算法,那此题的关键是:找到局部最优解
  • 如果当前循环中,连续数组的和为负数,那只会让后面的数更小,也即会拖累后面的数。
  • 题目示例中,[-2,1]子序列和为-1,与其让-2 “拖累” 1,不如从1重新开始。

代码

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) {count += nums[i];if (count > result) { // 取区间累计的最大值(相当于不断确定最大子序终止位置)result = count;}if (count <= 0) count = 0; // 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和}return result;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/284776.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

wy的leetcode刷题记录_Day93

wy的leetcode刷题记录_Day93 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间&#xff1a;2024-3-23 前言 目录 wy的leetcode刷题记录_Day93声明前言2549. 统计桌面上的不同数字题目介绍思路代码收获 827. 最大人工岛题目介绍思路代码收获 200. 岛屿…

【Godot4.2】像素直线画法及点求取函数

概述 基于CanvasItem提供的绘图函数进行线段绘制只需要直接调用draw_line函数就可以了。 但是对于可以保存和赋值节点直接使用的纹理图片&#xff0c;却需要依靠Image类。而Image类没有直接提供基于像素的绘图函数。只能依靠set_pixel或set_pixelv进行逐个像素的填色。 所以…

数字乡村发展策略:科技引领农村实现跨越式发展

随着信息技术的迅猛发展和数字经济的崛起&#xff0c;数字乡村发展策略已经成为引领农村实现跨越式发展的重要手段。科技的力量正在深刻改变着传统农业的生产方式、农村的社会结构以及农民的生活方式&#xff0c;为农村经济发展注入了新的活力和动力。本文将从数字乡村的内涵、…

java每日一题——买啤酒(递归经典问题)

前言&#xff1a; 非常喜欢的一道题&#xff0c;经典中的经典。打好基础&#xff0c;daydayup!!!啤酒问题&#xff1a;一瓶啤酒2元&#xff0c;4个盖子可以换一瓶&#xff0c;2个空瓶可以换一瓶&#xff0c;请问10元可以喝几瓶 题目如下&#xff1a; 啤酒问题&#xff1a;一瓶…

基于图的在线社区假新闻检测建模

论文原文&#xff1a;Graph-based Modeling of Online Communities for Fake News Detection 论文代码&#xff1a;GitHub - shaanchandra/SAFER: Repository containing the official code for the paper Graph-based Modeling of Online Communities for Fake News Detectio…

KIMI爆了!对比文心一言和通义千问它到底有多强?

原文:赵侠客 前言 最近国产大模型KIMI爆了大部分人应该都知道了&#xff0c;从我个人的感受来看这次KIMI爆了我不是从技术领域接触到的&#xff0c;而是从各种金融领域接触到的。目前国内大模型可以说是百模大战&#xff0c;前几年新能源大战&#xff0c;今年资本割完韭菜后留…

java面向对象编程基础

对象&#xff1a; java程序中的对象&#xff1a; 本质上是一种特殊的数据结构 对象是由类new出来的&#xff0c;有了类就可以创建对象 对象在计算机的执行原理&#xff1a; student s1new student();每次new student(),就是在堆内存中开辟一块内存区域代表一个学生对象s1变…

Matlab DDPG

文章目录 1 rlSimulinkEnv1.1 说明1.2 例子1.2.1 使用工作空间Agent创建Simulink环境1.2.2 为Simulink模型创建强化学习环境1.2.3 创建Simulink多Agents环境2 创建Simulink环境和训练Agent2.1 创建环境接口2.2 创建DDPG Agent2.3 训练Agent2.4 验证已训练的Agent3 创建Simulink…

创建linux虚拟机系统:(安装Ubuntu镜像文件,包含语言设置、中文输入法、时间设置)

我下载的是清华大写开源软件镜像站中的ubuntu-20.04.6-desktop-amd64.iso这个镜像文件&#xff0c; 这个文件我下载完成之后没有解压&#xff0c;直接在创建虚拟机的时候选择的压缩包。 地址为&#xff1a;Index of /ubuntu-releases/20.04/ | 清华大学开源软件镜像站 | Tsin…

Git——IDEA中的使用详解

目录 Git1、IDEA中配置Git2、将本地项目推送到远程仓库2.1、创建项目远程仓库2.2、初始化本地仓库2.3、连接远程仓库2.4、提交到本地仓库2.5、推送到远程仓库 3、克隆远程仓库到本地4、基本操作4.1、代码提交到暂存区4.2、暂存区代码提交到本地库4.3、推送到远程仓库4.4、撤销本…

网络: 网络层

IP地址: 分为网络号和主机号. 用来标识主机 IP协议 IP协议报文 4位版本号(version): 指定IP协议的版本, 对于IPv4来说, 就是4.4位头部长度(header length): IP头部的长度是多少个32bit, 也就是 length * 4 的字节数. 4bit表示最大的数字是15, 因此IP头部最大长度是60字节. 8…

HarmonyOS NEXT应用开发案例集

概述 随着应用代码的复杂度提升&#xff0c;为了使应用有更好的可维护性和可扩展性&#xff0c;良好的应用架构设计变得尤为重要。本篇文章将介绍一个应用通用架构的设计思路&#xff0c;以减少模块间的耦合、提升团队开发效率&#xff0c;为开发者呈现一个清晰且结构化的开发…

YOLOv8:Roboflow公开数据集训练模型

Roboflow公开数据集 Roboflow是一个提供计算机视觉数据集管理和处理工具的平台。虽然Roboflow本身并不创建或策划公开数据集&#xff0c;但它提供了一系列功能&#xff0c;帮助用户组织、预处理、增强和导出计算机视觉数据集。 官方网站&#xff1a;https://universe.roboflow…

FOCUS-AND-DETECT: A SMALL OBJECTDETECTION FRAMEWORK FOR AERIAL IMAGES

摘要 为了解决小对象检测问题&#xff0c;提出了一个叫做 Focus-and Detect 的检测框架&#xff0c;它是一个两阶段的框架。 第 一阶段包括由高斯混合模型监督的对象检测器网络&#xff0c;生成构成聚焦区域的对象簇 。 第二阶段 也是一个物体探测器网络&#xff0c;预测聚焦…

Web框架开发-Ajax

一、 Ajax准备知识:json 1、json(Javascript Obiect Notation,JS对象标记)是一种轻量级的数据交换格式 1 2 它基于 ECMAScript (w3c制定的js规范)的一个子集,采用完全独立于编程语言的文本格式来存储和表示数据。 简洁和清晰的层次结构使得 JSON 成为理想的数据交换语言。…

谧林涓露门禁

原神武器升级材料谧林涓露和门禁好像聂。 difference(){union(){cylinder(2, 10,10, $fn365);hull(){translate([15,0,0])cylinder(1,2,2,$fn365);cylinder(1,10,10,$fn365);}}translate([15,0,-1])cylinder(4,1,1,$fn365); }

swagger3快速使用

目录 &#x1f37f;1.导入依赖 &#x1f32d;2.添加配置文件 &#x1f9c2;3.添加注解 &#x1f96f;4.访问客户端 1.导入依赖 引入swagger3的依赖包 <dependency><groupId>io.springfox</groupId><artifactId>springfox-boot-starter</artif…

智能驾驶域控制器行业介绍

汽车智能驾驶功能持续高速渗透&#xff0c;带来智能驾驶域控制器市场空间快速增 长。智驾域控制器是智能驾驶决策环节的重要零部件&#xff0c;主要功能为处理感知 信息、进行规划决策等。其核心部件主要为计算芯片&#xff0c;英伟达、地平线等芯 片厂商市场地位突出。随着消费…

【c语言】详解操作符(上)

1. 操作符的分类 2. 原码、反码、补码 整数的2进制表示方法有三种&#xff0c;即原码、反码、补码 有符号整数的三种表示方法均有符号位和数值位两部分&#xff0c;2进制序列中&#xff0c;最高位的1位是被当做符号位其余都是数值位。 符号位都是用0表示“正”&#xff0c;用…

二分算法(查找)

问题&#xff1a;在数组中查找某一个数字x4的下标 例&#xff1a;arr:1 3 4 6 10 20 21 22 显然&#xff0c;数字4的下标为3。 1、线性查找&#xff0c;一个个地去遍历&#xff0c;时间复杂度为O(n) 2、二分查找&#xff0…