@ 代码随想录算法训练营第5周(C语言)|Day31(贪心算法)

@ 代码随想录算法训练营第5周(C语言)|Day31(贪心算法)

Day31、贪心算法(包含题目 455.分发饼干 376. 摆动序列 53. 最大子序和 )

455.分发饼干

题目描述

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

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

题目解答

void quicksotr(int *nums,int left,int right){if(left>right){return;}int left1=left;int right1=right;int k=nums[left1];while(left1<right1){//做快排的时候一定要注意这个left1<right1条件while(left1<right1&&k<=nums[right1]){right1--;}nums[left1]=nums[right1];while(left1<right1&&k>=nums[left1]){left1++;}nums[right1]=nums[left1];}nums[left1]=k;quicksotr(nums,left,left1-1);quicksotr(nums,left1+1,right);return;
}
int findContentChildren(int* g, int gSize, int* s, int sSize) {quicksotr(g,0,gSize-1);quicksotr(s,0,sSize-1);int gi=0;for(int i=0;i<sSize;i++){if(gi<gSize&&g[gi]<=s[i]){gi++;}}return gi;}

题目解答

做快排的时候一定要注意这个left1<right1条件。

376. 摆动序列

题目描述

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

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

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

题目解答

int wiggleMaxLength(int* nums, int numsSize){if(numsSize==1){return 1;}if(numsSize==2){return nums[0]!=nums[1]?2:1;}int prediff=0;int curdiff=0;int res=1;for(int i=1;i<numsSize;i++){curdiff=nums[i]-nums[i-1];if((prediff>=0&&curdiff<0)||(prediff<=0&&curdiff>0)){res++;prediff=curdiff;}}return res;
}

题目总结

利用摆动序列的性质一高一低就计数加一,从零开始,终点不算。

53. 最大子序和

题目描述

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

题目解答

int max(int a,int b){return a>b?a:b;
}
int maxSubArray(int* nums, int numsSize) {int dp[numsSize];dp[0]=nums[0];int res=nums[0];for(int i=1;i<numsSize;i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);res=max(res,dp[i]);}return res;
}

题目总结

用动态规划,dp数组为前i项(包含nums[i]的)最大的连续子序列之和。

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

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

相关文章

安全基础~通用漏洞3

文章目录 知识补充文件上传&#xff08;1&#xff09;ctfshow 文件上传靶场练习150-161 文件上传&#xff08;2&#xff09;ctfshow 文件上传靶场练习162-170 文件上传总结文件包含 知识补充 url编码&#xff1a;0a 换行&#xff1b;20空格&#xff1b;3c左尖括号&#xff1b;…

研发日记,Matlab/Simulink避坑指南(八)——else if分支结构Bug

文章目录 前言 背景介绍 问题描述 分析排查 解决方案 总结归纳 前言 见《研发日记&#xff0c;Matlab/Simulink避坑指南(三)——向上取整Bug》 见《研发日记&#xff0c;Matlab/Simulink避坑指南(四)——transpose()转置函数Bug》 见《研发日记&#xff0c;Matlab/Simuli…

IP 层转发分组的过程

目录 IP 层转发分组的过程 1.1 基于终点的转发 1.2 最长前缀匹配 转发表中的 2 种特殊的路由 主机路由 (host route) 默认路由 (default route) 路由器分组转发算法 1.3 使用二叉线索查找转发表 IP 层转发分组的过程 1.1 基于终点的转发 分组在互联网中是逐跳转发的。…

VMware vCenter告警:vSphere UI运行状况警报

vSphere UI运行状况警报 不会详细显示告警的具体内容&#xff0c;需要我们自己进一步确认告警原因。 vSphere UI运行状况警报是一种监控工具&#xff0c;用于检测vSphere环境中的潜在问题。当警报触发时&#xff0c;通常表示系统遇到了影响性能或可用性的问题。解决vSphere UI…

【LVGL源码移植】

LVGL源码移植 ■ LVGL源码移植一&#xff1a;下载LVGL源码二&#xff1a;修改LVGL文件夹1: 将这5个文件&#xff0c;复制到一个新的文件夹2: 简化文件&#xff0c;减少内存消耗&#xff08;去除不必要的文件&#xff09;3: 为了规范化&#xff0c;我们将下列文件进行重命名 三&…

Apache POI 处理excel文件 记录用法

Apache POI 写excel public static void write() throws IOException {//再内存中创建了一个Excel文件XSSFWorkbook excel new XSSFWorkbook();//创建一个sheet页XSSFSheet sheet excel.createSheet("info");//这里创建行对象,这里的rownum 是从0开始的,类似于数…

大数据开发之离线数仓项目(用户行为采集平台)(可面试使用)

第 1 章&#xff1a;数据仓库概念 数据仓库&#xff0c;是为企业指定决策&#xff0c;提供数据支持的&#xff0c;可以帮助企业&#xff0c;改进业务流程、提高产品质量等。 数据仓库的输入数据通常包括&#xff1a;业务数据、用户行为数据和爬虫数据等。 业务数据&#xff1a…

维护管理Harbor,docker容器的重启策略

维护管理Harbor 通过HarborWeb创建项目 在 Harbor 仓库中&#xff0c;任何镜像在被 push 到 regsitry 之前都必须有一个自己所属的项目。 单击“项目”&#xff0c;填写项目名称&#xff0c;项目级别若设置为"私有"&#xff0c;则不勾选。如果设置为公共仓库&#…

【新书推荐】4.3节 键盘扫描码

本节内容&#xff1a;键盘扫描码。 ■键盘扫描码&#xff1a;8086计算机的键盘上的按键分为字符键、功能键和控制键。每一个按键都对应一个键盘扫描码。当按下按键时的扫描码称为通码&#xff0c;松开按键时的扫描码称为断码。如果按下的是字符键&#xff0c;则将其对应的一个…

假期刷题打卡--Day20

1、MT1173魔数 一个数字&#xff0c;把他乘以二&#xff0c;会得到一个新的数字&#xff0c;如果这个新数字依然由原数中那些数字组成&#xff0c;就称原数为一个魔数。输入正整数N&#xff0c;检查它是否是一个魔数&#xff0c;输出YES或者NO。 格式 输入格式&#xff1a; …

深度学习之反向传播

反向传播英文叫做Back Propagation。 为什么需要使用反向传播 对于简单的模型我们可以用解析式求出它的损失函数的梯度&#xff0c;例如&#xff0c;其损失函数的梯度就是&#xff0c;我们可以通过我们的数学知识很容易就得到其损失函数的梯度&#xff0c;继而进行使用梯度下…

网络原理,网络通信以及网络协议

​​​​&#x1f493; 博客主页&#xff1a;从零开始的-CodeNinja之路 ⏩ 收录专栏&#xff1a;网络原理,网络通信以及网络协议 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 文章目录 网络原理概念网络通信局域网LAN广域网WAN 网络通信IP地址端口号…

HBase介绍

一、HBase简介 1.1、HBase是什么 Google在200-2006发表了GFS、MapReduce、BigTable三篇 论文 &#xff0c;号称“三驾马车”&#xff0c;开启了大数据的时代。 GFS是Google File System&#xff0c;开源实现是HDFS&#xff08;Hadoop File System&#xff09;。 MapReduce…

深度学习-搭建Colab环境

Google Colab(Colaboratory) 是一个免费的云端环境&#xff0c;旨在帮助开发者和研究人员轻松进行机器学习和数据科学工作。它提供了许多优势&#xff0c;使得编写、执行和共享代码变得更加简单和高效。Colab 在云端提供了预配置的环境&#xff0c;可以直接开始编写代码&#x…

vue2 导入使用vue-codemirror详解

目录 vue2 导入使用vue-codemirror详解1 介绍2 安装使用2.1 安装 vue-codemirror2.2 使用 codemirror2.2.1 引入 3 配置详情3.1 语言模式配置3.2 自动高度设置3.4 主题配置 4 总结 vue2 导入使用vue-codemirror详解 1 介绍 vue-codemirror是一个基于Vue的代码在线编辑器组件&…

Linux部署DataEase数据分析工具并结合内网穿透实现任意设备远程查看数据

文章目录 前言1. 安装DataEase2. 本地访问测试3. 安装 cpolar内网穿透软件4. 配置DataEase公网访问地址5. 公网远程访问Data Ease6. 固定Data Ease公网地址 前言 DataEase 是开源的数据可视化分析工具&#xff0c;帮助用户快速分析数据并洞察业务趋势&#xff0c;从而实现业务…

线性表的链式表示【单链表】

目录 单链表的优缺点 单链表结点的定义 头插法新建链表 尾插法新建链表 按位查找 按值查找 i 位置插入元素 单链表的删除 单链表的优缺点 优点缺点 1. 插入和删除操作不需要移动元素&#xff0c;只需要修改指针 2. 不需要大量的连续存储空间 1. 单链表附加指针域&…

【昕宝爸爸小模块】日志系列之什么是分布式日志系统

➡️博客首页 https://blog.csdn.net/Java_Yangxiaoyuan 欢迎优秀的你&#x1f44d;点赞、&#x1f5c2;️收藏、加❤️关注哦。 本文章CSDN首发&#xff0c;欢迎转载&#xff0c;要注明出处哦&#xff01; 先感谢优秀的你能认真的看完本文&…

基于单片机温度控制系统的研究

摘 要&#xff1a;笔者基于单片机的温度控制系统&#xff0c;从单片机选择、传感器选择、系统框架设计等方面概述了单片机的温度控制系统内涵&#xff0c;分析了其运行原理&#xff0c;列举了单片机温度控制系统设计的实操方法&#xff0c;从硬件系统、软件系统、温度检测方法…

第一节课,用户管理--后端初始化,项目调通。二次翻工2

一、网址来源&#xff1a; 快速开始 | MyBatis-Plus (baomidou.com) 进程&#xff1a; ​ 二、[此处不看]添加测试类&#xff0c;看下效果 2.1 参考 一、第一节课&#xff0c;用户管理--后端初始化&#xff0c;项目调通-CSDN博客 ​ 2.2 新建 SampleTest ​ 2.3 复…