代码随想录Day.31 | 455. 分发饼干、376. 摆动序列、53. 最大子序和

455. 分发饼干

1. LeetCode链接

455. 分发饼干 - 力扣(LeetCode)

2. 题目描述

3. 解法

        贪心法,首先想到的是,局部最优:让每个孩子尽可能拿能拿到的最小饼干尺寸。为了方便查找,这就要求至少饼干尺寸是从小到大排列的。

        两个for循环解决。把小孩按照胃口也从小到大排列更快。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {vector<bool> used(s.size(), false);int sum = 0;// sort(g.begin(), g.end());sort(s.begin(), s.end());for (int i = 0; i < g.size(); i++) {for (int j = 0; j < s.size(); j++) {if (used[j]) continue;if (s[j] >= g[i]) {sum++;used[j] = true;break;}}}return sum;}
};

但是很明显,还是太慢了。

        假如说,小孩的胃口和饼干的尺寸都从小到大排序。可以着么想。加入某个小孩i和某个饼干j匹配成功了,后面一个小孩i+1就只能去匹配后面的饼干(> j),前面的饼干完全不需要考虑。所以只用一个for循环就可以搞定。

        

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

其中,for循环时由饼干的数组控制的,原因在于,如果当前小孩和饼干不匹配的话,即当前饼干不是能满足小孩的最小尺寸饼干,应该用下一块饼干去匹配当前小孩。

假如用,下一个小孩去匹配当前饼干,而在当前小孩都不匹配的情况下,下一个胃口更大的小孩更不可能匹配,这就导致在一个for循环下,找不到任何一对匹配的。

376. 摆动序列

1. LeetCode链接

376. 摆动序列 - 力扣(LeetCode)

2. 题目描述

3. 解法

贪心,局部最优:每次找最近的一对相邻的数字,且两数之差与上一个不一样。

详细来说,摆动序列要求序列数组成上坡——下坡交替状。

而一般的数组在一对上下坡之间,要不是有一堆单调坡,要不是有平路。

摆动序列,即找峰值点旁边的上下坡。

代码解读:

        首先,要找到合适的初值,主要是防止前n项都为相同的值。int cha的作用是记录第一对相邻但不相等的差值。找到初值后,初始化bool turn,turn == true表示前一个差值是正数,否则是负数。

        找到初值并初始化turn后,接下来就开始找与上一个差值不同的相邻两数,改变turn,如此往复。

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int cha = 0;bool turn = true;int len = 1;for (int i = 1; i < nums.size(); i++) {if (cha == 0 && nums[i] - nums[i - 1] != 0) {cha = nums[i] - nums[i - 1];turn = (cha > 0 ? true : false);len++;} else {if ((nums[i] - nums[i - 1] > 0 && turn == false) || (nums[i] - nums[i - 1] < 0 && turn == true)) {len++;turn = (turn == true ? false : true);}}}return len;}
};

53. 最大子数组和

1. LeetCode链接

53. 最大子数组和 - 力扣(LeetCode)

2. 题目描述

3. 解法

1. 我的解法

        首先考虑特殊情况,即数组中全是非正数,这就成了找最大值的题。

        需要遍历一遍,遍历完就输出最大值,遇到第一个正数则停止。

        将第一个正数累加到sum上。

        从一个正数的下一个开始开始,遇到下一个正数结束,为一个阶段。有两种情况:1. 该阶段中的负数累加到sum上后的值<0,则刷新累加和sum,和局部累加和sumb。此种情况要记录之前最大的sum;2. sumb>0,则sumb加到累加和上,sumb刷新。

比较之前记录的历史最大sum和当前的sum,输出较大的一个。

class Solution {
public:int maxSubArray(vector<int>& nums) {int sum = INT_MIN;int i = 0;for (; i < nums.size(); i++) {if (nums[i] > 0) break;else if (nums[i] > sum) sum = nums[i];}if (i == nums.size()) return sum;sum = nums[i];i++;int sumb = 0;int max = INT_MIN;for (; i < nums.size(); i++) {if (sum + sumb < 0) {if (sum > nums[i] && sum > max) max = sum; sum = 0;sumb = 0;}sumb += nums[i];if (sumb > 0) {sum += sumb;sumb = 0;}}return sum > max ? sum : max;}
};

1. 记录所有可能的连续和为正值的和,只保留最大值。

2. 改变连续子区间的起点和终点,在子区间累加和<0后,使子区间累加和=0,相当于重新设置起点;重点是使得累加和>=0的所有,都可以成为终点,保留最大子区间和。

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/236434.html

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

相关文章

shell中的正则表达式、编程-grep、编程-SED、以及编程-AWK

正则表达式RE 用来处理文本 正则表达式(Regular Expression, RE)是一种字符模式, 用于在查找过程中匹配指定的字符. 在大多数程序里, 正则表达式都被置于两个正斜杠之间; 例如/l[oO]ve/就是由正斜杠界定的正则表达式, 它将匹配被查找的行中任何位置出现的相同模式. 在正则表达…

react antd EditableProTable - 可编辑表格

与编辑表格外的内容联动 value 同 dataSource&#xff0c;传入一个数组,是 table 渲染的元数据 T[] undefined onChange dataSource 修改时触发&#xff0c;删除和修改都会触发,如果设置了 value&#xff0c;Table 会成为一个受控组件。 (value:T[])>void undefined recordC…

[易语言]使用易语言部署工业级人脸检测模型

【框架地址】 https://github.com/ShiqiYu/libfacedetection 【算法介绍】 Libfacedetection是一个开源的计算机视觉库&#xff0c;主要用于实时的人脸检测。它利用深度学习技术&#xff0c;特别是卷积神经网络&#xff08;CNN&#xff09;&#xff0c;实现了高精度的脸部定位…

GlusterFS

一. 概念 1. 介绍 gluster是一个横向扩展的分布式文件系统&#xff0c;可将来自多个服务器的磁盘存储资源整合到一个全局名称空间中&#xff0c;可以根据存储消耗需求快速调配额外的存储。它将自动故障转移作为主要功能. 分布式存储系统.集群式NAS存储.无集中式元数据服务,采…

ChatGLM2-6B 大语言模型本地搭建

ChatGLM模型介绍&#xff1a; ChatGLM2-6B 是清华 NLP 团队于不久前发布的中英双语对话模型&#xff0c;它具备了强大的问答和对话功能。拥有最大32K上下文&#xff0c;并且在授权后可免费商用&#xff01; ChatGLM2-6B的6B代表了训练参数量为60亿&#xff0c;同时运用了模型…

Python笔记08-面向对象

文章目录 类和对象构造方法内置方法封装继承类型注解多态 类只是一种程序内的“设计图纸”&#xff0c;需要基于图纸生产实体&#xff08;对象&#xff09;&#xff0c;才能正常工作 这种套路&#xff0c;称之为&#xff1a;面向对象编程 类和对象 定义类的语法如下&#xff…

K8S集群重新初始化--详细过程

K8S集群重新初始化 0、当前环境1、master节点1.1、在master节点执行下面reset命令&#xff1a;1.2、手动清除配置信息&#xff0c;这一步很关键&#xff1a;1.3、重新引导集群1.4、创建配置目录&#xff0c;并复制权限配置文件到用户目录下&#xff1a;1.5 查看集群状态1.6 安装…

提升测试效率,轻松并行运行测试——探秘Pytest插件pytest-xdist

在软件开发中&#xff0c;测试是确保代码质量的重要一环。然而&#xff0c;随着项目规模的增大&#xff0c;测试用例的数量也随之增多&#xff0c;测试的执行时间可能成为一个瓶颈。为了解决这个问题&#xff0c;Pytest提供了丰富的插件生态系统&#xff0c;其中 pytest-xdist …

从vue小白到高手,从一个内容管理网站开始实战开发第八天,登录功能后台功能设计--业务逻辑层基础接口和基础服务实现

上一篇我们介绍了项目后续要使用到的工具类,关于工具类的创建可以查看 从vue小白到高手,从一个内容管理网站开始实战开发第七天,登录功能后台功能设计--通用分页、枚举以及相关工具类-CSDN博客文章浏览阅读2次。本次内容主要介绍了项目后续用到的部分工具类,这些工具类,在…

基于博弈树的开源五子棋AI教程[3 极大极小搜索]

基于博弈树的开源五子棋AI教程[3 极大极小搜索] 引子极大极小搜索原理alpha-beta剪枝负极大搜索尾记 引子 极大极小搜索是博弈树搜索中最常用的算法&#xff0c;广泛应用于各类零和游戏中&#xff0c;例如象棋&#xff0c;围棋等棋类游戏。算法思想也是合乎人类的思考逻辑的&a…

物理机搭建hive

一、修改Hadoop配置 修改core-site.xml 配置yarn-site.xml 分发文件&#xff0c;然后重启集群 二、 Hive解压安装 上传文件 添加hive环境便量&#xff0c;source生效 启动高可用集群&#xff0c;启动hive 三、配置mysql元数据库 检查当前系统是否安装过Mysql&#xf…

开启Android学习之旅-5-Activity全屏

Android 两种方式设置全屏&#xff1a; 1. 第一行代码中的方法 通过 getWindow().getDecorView()方法拿到当前Activity的DecorView,再调用 setSystemUiVisibility() 方法来改变系统UI的显示&#xff0c;这里传入了 View.SYSTEM_UI_FLAG_LAYOUT_FULLSCREEN 和 View.SYSTEM_UI_…

服务器部署项目,访问验证码出现Handler dispatch failed....InvocationTargeException

场景&#xff1a; 部署ruoyi-vue的jar。访问验证码接口时&#xff0c;出现异常。本地测试没有问题&#xff0c;起初使用的jdk8&#xff0c;怀疑jdk版本问题&#xff0c;但是本地使用11.0.15版本也没问题&#xff0c;后面也就没管&#xff0c;初步排除jdk版本的问题。之前项目也…

软考高级选择考哪个好?

&#x1f4d2;软考高级总共5个科目&#xff0c;同样是高级证书&#xff0c;认可度也有区别! 大家一般在「信息系统项目管理师」✔️和「系统架构设计师」✔️二选一 1️⃣信息系统项目管理师 ❤️信息系统项目管理师也叫「高项」&#xff0c;考试内容主要是「项目管理」相关&am…

el-tree多个树进行节点同步联动(完整版)

2024.1.11今天我学习了如何对多个el-tree树进行相同节点的联动效果&#xff0c;如图&#xff1a; 这边有两棵树&#xff0c;我们发现第一个树和第二个树之间会有重复的指标&#xff0c;当我们选中第一个树的指标&#xff0c;我们希望第二个树如果也有重复的指标也能进行勾选上&…

这6个免费素材网站,设计师们一定要知道!

设计师找素材就上这6个网站&#xff0c;免费下载&#xff0c;还可以商用&#xff0c;建议收藏好了~ 1、菜鸟图库 https://www.sucai999.com/?vNTYwNDUx 菜鸟图库是我推荐过很多次的网站&#xff0c;主要是站内素材多&#xff0c;像平面、UI、电商等超多设计素材都能找到&…

PLECS如何下载第三方库并导入MOSFET 的xml文件,xml库路径添加方法及相关问题

1. 首先xml库的下载&#xff0c;PLECS提供了一个跳转的链接。 https://www.plexim.com/download/thermal_models 2. 下载一个库&#xff08;以最后一个Wolfspeed为例&#xff0c;属于CREE的SiC MOSFET&#xff09; 下载这个就行&#xff0c;都包含了。不信自己可以试试再下载…

Win10子系统Ubuntu实战(一)

在 Windows 10 中安装 Ubuntu 子系统&#xff08;Windows Subsystem for Linux&#xff0c;简称 WSL&#xff09;有几个主要的用途和好处&#xff1a;Linux 环境的支持、跨平台开发、命令行工具、测试和验证、教育用途。总体而言&#xff0c;WSL 提供了一种将 Windows 和 Linux…

【Linux】Linux系统编程——ls命令

【Linux】Linux 系统编程——ls 命令 1.命令概述 ls 命令是 Linux 和其他类 Unix 操作系统中最常用的命令之一。ls 命令是英文单词 list 的缩写&#xff0c;正如 list 的意思&#xff0c;ls 命令用于列出文件系统中的文件和目录。使用此命令&#xff0c;用户可以查看目录中的…

刚买的助听器就弄丢了,不想白配,快来看看这8大助听器防丢小技巧

我们知道助听器可以让听损人士重新听到美妙的声音和享受沟通的乐趣。但是&#xff0c;助听器也是一种很贵的物品&#xff0c;如果不小心弄丢了&#xff0c;就会让人心痛不已。 更有甚者&#xff0c;有些人因为害怕丢失助听器&#xff0c;而不敢佩戴助听器&#xff0c;错过了听力…