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

news/2024/4/15 13:57:32

@ 代码随想录算法训练营第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.ppmy.cn/news/1338673.html

相关文章

15.Golang中的反射机制及应用

目录 概述实践基本应用复杂应用 结束 概述 Golang中的反射用法还是比较简单的 reflect.TypeOf(arg)reflect.ValueOf(arg) 实践 基本应用 package mainimport ("fmt""reflect" )func reflectNum(arg interface{}) {fmt.Println("type ", re…

Vue学习笔记(二)快速入门

Vue学习笔记&#xff08;二&#xff09;快速入门 vue小试牛刀 hello-vue3.html <body><div id"app"><h1>{{msg}}</h1></div><script type"module">import {createApp} from https://unpkg.com/vue3/dist/vue.esm-b…

c# cass10 获取宗地内所有封闭线段的面积

获取面积的主要流程如下&#xff1a; 获取当前AutoCAD应用中的活动文档、数据库和编辑器对象。创建一个选择过滤器&#xff0c;限制用户只能选择"宗地"图层上的LWPOLYLINE对象作为外部边界。提示用户根据上述规则进行实体选择&#xff0c;并获取选择结果。检查用户是…

Linux第39步_创建正点原子的uboot工作区和使用脚本编译

先看答案&#xff0c;再做题&#xff0c;为移植uboot做好充足的准备。这里需要修改两个“Makefile”文件&#xff0c;路数变了。 一、uboot移植前需要了解的相关知识 1、正点原子的uboot设备树文件。 路径如下&#xff1a; “uboot/alientek_uboot/arch/arm/dts/” 文件如…

LeetCode: 189.轮转数组

本篇目标了解&#xff0c;翻转数组的经典解法&#xff0c; 189. 轮转数组 - 力扣&#xff08;LeetCode&#xff09; 目录 基本方法概述&#xff1a; 1&#xff0c;翻转做法&#xff0c;推荐时O&#xff08;n&#xff09;&#xff0c;空&#xff08;1&#xff09; 2&#x…

Excel-Apache POI

Apache POI是用Java编写的免费开源的跨平台的Java API&#xff0c;Apache POI提供API给Java程 序对Microsoft Office格式档案读和写的功能&#xff0c;其中使用最多的就是使用POI操作Excel文 件。 Apache POI常用的类 HSSF &#xff0d; 提供读写Microsoft Excel XLS格式档案…

使用golang发送邮件

目前大多应用都是手机登录&#xff0c;但是作为开源的一个软件&#xff0c;或者是私有的一个应用&#xff0c;那么使用手机短信接收验证码成本比较高&#xff0c;使用邮箱相对更容易&#xff0c; 这里从tinode中取出发邮件的部分做一个测试&#xff0c; 其中邮箱一般需要设置…

Cache Lab:Part A【模拟出使用LRU策略的高速缓存存储器组织结构】

目录 任务描述 知识回顾 实验内容 测试结果 Cache Lab 对应《CS:APP》6.3节至第六章结束的内容。 任务描述 Your job for Part A is to fill in the csim.c file so that it takes the same command line arguments and produces the identical output as the reference …

Django如何调用机器学习模型进行预测

Django是一个流行的Python Web框架,它可以很方便地集成机器学习模型,进行预测和推理。我将介绍如何在Django项目中调用训练好的机器学习模型,并实现一个预测接口。 准备工作 首先我们需要一个训练好的机器学习模型。这里我们使用Scikit-Learn训练一个简单的线性回归模型作为示…

鸿蒙会取代Android吗?听风就是雨

现在说取代还谈不上&#xff0c;毕竟这需要时间。安卓作为全球第一的手机操作系统&#xff0c;短时间内还无法取代。持平iOS甚至超过iOS有很大可能&#xff0c;最终会呈现“三足鼎立”有望超过安卓基数。 作为全新的鸿蒙操作系统&#xff0c;其现在已经是全栈自研底座。按照鸿…

2024Node.js零基础教程(小白友好型),nodejs新手到高手,(三)NodeJS入门——http协议

033_HTTP协议_初识HTTP协议 hello&#xff0c;大家好&#xff0c;这个小节我们来认识一下 http协议。 http是几个单词的首字母拼写&#xff0c;全称为Hypertext Transfer Protocol 译为超文本传输协议&#xff0c;那么这个http协议是互联网上应用最广泛的协议之一。顺便说一下…

苹果提审被拒反馈崩溃日志.text | iOS 审核被拒crashLog

iOS审核人员拒绝后每个截图&#xff0c;只给了几个text文件&#xff0c;这种情况就是审核的时候运行你的代码&#xff0c;崩溃了。 仅仅看text文件&#xff0c;是看不出所以然来的&#xff0c;所以我们要将日志转换成.crash格式 1.将.text文件下载下来&#xff0c;将 .text手动…

【每日一题】 2024年1月汇编

&#x1f525;博客主页&#xff1a; A_SHOWY&#x1f3a5;系列专栏&#xff1a;力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_ 【1.4】2397.被列覆盖的最多行数 2397. 被列覆盖的最多行数https://leetcode.cn/problems/maximum-rows-covered-by-columns/ 这…

滇西科技师范学院食堂大宗物资采购项目(冰冻制品类)招标公告

滇西科技师范学院食堂大宗物资采购项目(冰冻制品类)招标公告 (招标编号&#xff1a;YDZOH20240158) 项目所在地区&#xff1a;云南省,临沧市,市辖区 一、招标条件 本滇西科技师范学院食堂大宗物资采购项目(冰冻制品类)已由项目审批/核准/备案机关批准&#xff0c;项目资金来源为…

C#网络爬虫之TianyaCrawler实战经验分享

互联网时代的到来带来了大量的数据&#xff0c;而网络爬虫技术成为了获取这些数据的重要途径之一。如果你是一名C#开发者&#xff0c;那么你可能会对TianyaCrawler这个强大的网络爬虫框架感兴趣。本文将带你深入了解TianyaCrawler&#xff0c;分享它的技术概况、使用场景&#…

数据结构(1)--> 顺序表

定义&#xff1a; 顺序表存储定义&#xff1a; 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构&#xff0c;顺序表功能的实现借助于数组&#xff0c;通过对数组进行封装&#xff0c;从而实现增删查改的功能&#xff0c;严格意义上来说&#xff08;数组无法实现…

线程池相关的类学习

Executor public interface Executor {//执行任务void execute(Runnable command); }ExecutorService public interface ExecutorService extends Executor {//关闭线程池&#xff0c;不能再向线程池中提交任务&#xff0c;已存在与线程池中的任务会继续执行&#xff0c;直到…

[word] word艺术字体如何设置? #知识分享#职场发展#媒体

word艺术字体如何设置&#xff1f; 在工作中有些技巧&#xff0c;可以快速提高工作效率&#xff0c;解决大部分工作&#xff0c;今天给大家分享word艺术字体如何设置的技巧&#xff0c;希望可以帮助到你。 1、设置艺术字 选中文字&#xff0c;然后点击菜单栏的【插入】按钮一一…

<网络安全>《11 网络安全审计系统》

1 概念 审计是对资料作出证据搜集及分析&#xff0c;以评估企业状况&#xff0c;然后就资料及一般公认准则之间的相关程度作出结论及报告。 国际互联网络安全审计&#xff08;网络备案&#xff09;&#xff0c;是为了加强和规范互联网安全技术防范工作&#xff0c;保障互联网…

讲一讲闭包

闭包的定义 MDN 对闭包的定义为&#xff1a;闭包就是那些能够访问自由变量的函数。 什么是自由变量呢&#xff1f; 自由变量是指在函数中使用&#xff0c;但既不是函数参数也不是函数局部变量的变量。 由此可见闭包包含两部分&#xff1a;函数函数能够访问的自由变量&#xf…
最新文章