Day31|贪心算法1

news/2024/4/24 17:57:57/文章来源:https://blog.csdn.net/WEnyue4261/article/details/136442758

贪心的本质是选择每一阶段的局部最优,从而达到全局最优。

无固定套路,举不出反例,就可以试试贪心。

一般解题步骤:

1.将问题分解成若干子问题

2.找出适合的贪心策略

3.求解每一个子问题的最优解

4.将局部最优解堆叠成全局最优解

分发饼干

思路:为了满足更多的小孩,就不要造成饼干尺寸的浪费,大尺寸的饼干既可以满足胃口大的孩子,也可以满足胃口小的孩子,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略,先将饼干数组和小孩数组进行排序。然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。

class Solution{
public:int findContentChildren(vector<int>&g,vector<int>& s){sort(g.begin(),g.end());sort(s.begin(),s.end());int index = s.size() - 1;int result = 0;for(int i = g.size() - 1;i >= 0; i--){if(index >= 0 && s[index] >= g[i]){result++;index--;}}return result;}
};

从代码中可以看出,index用来控制饼干数组的遍历,遍历饼干没有再起一个循环,而是采用自减的方式,这是常用的技巧。

不可以先遍历比骨干再遍历胃口,因为外面for,i是固定移动的,if的index才是符合条件移动的。

 反过来,先满足胃口小的,从小到大去满足:

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 < size(); i++){if(index < g.size() && g[index] <= s[i]){index++;}}return index;}
};
//思路一
class Solution{public int findContentChildren(int[] g, int[] s){Arrays.sort(g);Arrays.sort(s);int start = 0;int count = 0;for(int i = 0; i < s.length && start < g.length; i++){if(s[i] >= g[start]){start++;count++;}}return count;}
}
class Solution{public int findContentChildren(int[] g,int[] s){Arrays.sort(g);//排序胃口Arrays.sort(s);//排序饼干int count = 0;int start = s.length - 1;//胃口数组长度,从start开始遍历,倒着遍历,先考虑胃口大的//遍历胃口,从大到小for(int index = g.length - 1;index >= 0;index--){if(start >= 0 && g[index] <= s[start]){start--;//从大到小count++;//满足一个计数+1}}return count;//返回计数}
}

摆动序列

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

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

思路:

贪心

删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值。

整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列。

实际操作中,删除操作都不用,因为题目要求的是最长摆动子序列的长度,所以只需要统计数组的峰值数量就可以了(相当于是删除单一坡度上的节点,然后统计长度)

这就是贪心所贪的地方, 让峰值尽可能地保持峰值,然后删除单一坡度上的节点。

在计算是否有峰值的时候,大家知道遍历的下标i,计算presiff(nums[i] - nums[i - 1])和curdiff(nums[i + 1] - nums[i]),如果presiff < 0 && surdiff > 0或者prediff > 0 && curdiff < 0,此时就有波动就需要统计。

这是我们思考本题的一个大体思路,但本题还要考虑三种情况:

1.上下坡有平坡

[1,2,2,2,2,1]删除左边的三个2,或者删除右边的三个2,摆动长度为3

当i指向第一个2的时候,prediff > 0&&curdiff=0,当 i 指向最后一个2的时候,prediff=0 && curdiff <0.

如果采用删除左面三个2的规则,那么当prediff = 0&&curdiff < 0也要记录一个峰值,因为他是把之前相同的元素都删掉留下的峰值。

我们记录峰值的条件应该是:(preDiff <=0 &&curDiff > 0)||(preDiff >= 0&&curDiff < 0) 

2.数组首尾两端

本题统计峰值的时候,数组最左面和最右面如何统计。

当有两个不同的元素时,摆动序列也是2.

例如[2,5],如果靠统计差值来计算峰值个数,就需要考虑数组最左面和最右面的特殊情况。

因为我们在计算prediff(nums[i] - nums[i - 1])和curdiff(nums[i+1] - nums[i])的时候,至少需要三个数字才能计算,而数组只有两个数字。这里如果只有两个数字,且是不同的元素,那结果为2.

3.单调坡中有平坡

之前我们在讨论 情况一 :相同数字练习的时候,prediff = 0,curdiff < 0或者>0也记为波谷

为了统一规则。针对序列[2,5],可以假设为[2,2,5],这样就有了坡度,即preDiff = 0.

[2,2,5]

针对以上情形,result初始值为1,此时curDiff > 0&&preDiff<=0,那么result++(计算了左面的峰值),最后得到结果为2(峰值个数为2即摆动序列长度为2)

class Solution{
public:int wiggleMaxLength(vector<int>&nums){if(num.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;}};
}

3.在上面解法中,忽略了第三种情况,即如果在一个单调坡度上有平坡,例如[1,2,2,2,3,4]

图中我们可以看出,应该记录2,单调中的平坡不能算作峰值(摆动)

 需要在坡度摆动变化时,更新prediff,这样prediff在单调区间有平坡的时候就不会发生变化,造成误判。

class Solution{
public:int wiggleMaxLength(vctor<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;}}return result;}
};

用动态规划求解

思路:

对于我们当前考虑的这个数,要么是作为山峰(nums[i] > nums[i - 1]),要么是作为山谷(即nums[i] < nums[i-1])

设dp状态dp[i][0],表示考虑前i个数,第i个数作为山峰的摆动子序列的最长长度。

设dp状态为dp[i][1],表示考虑前i个数,第i个数作为山谷的摆动子序列的最长长度

//设dp状态dp[i][0],表示考虑前i个数,第i个数作为山峰的摆动子序列的最长长度
//设dp状态dp[i][1],表示考虑前i个数,第i个数作为山谷的摆动子序列的最长长度
class Solution{
public:int wiggleMaxLength(vector<int>&nums){memset(dp,0,sizeof dp);dp[0][0] = dp[0][1] = 1;for(int i = 1;i < nums.size(); ++i){dp[i][0] = dp[i][1] = 1;for(int j = 0;j < i;++j){if(nums[j] > nums[i])dp[i][1] = max(dp[i][1],dp[j][0]+1);}for(int j = 0;j < i; ++j){if(nums[j] < nums[i])dp[i][0] = max(dp[i][0],dp[j][1] + 1);}}return max(dp[nums.size() - 1][0],dp[nums.size() - 1][1]);}
};

最大子序和

//记录局部最优,推出全局最优,相当于暴力求解+调整子区间起始位置,用了一个result来更新和记录最大结果count
class Solution{public:int maxSubArray(vector<int>&nums){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.luyixian.cn/news_show_998510.aspx

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

相关文章

HarmonyOS ArkTS工程目录结构(Stage模型)

1. ArkTS工程目录结构&#xff08;Stage模型&#xff09; 官方文档&#xff08;https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V2/start-with-ets-stage-0000001477980905-V2&#xff09; 1.1. AppScope AppScope > app.json5&#xff1a;应用的全局配…

spring cloud 之 Netflix Eureka

1、Eureka 简介 Eureka是Spring Cloud Netflix 微服务套件中的一个服务发现组件&#xff0c;本质上是一个基于REST的服务&#xff0c;主要用于AWS云来定位服务以实现中间层服务的负载均衡和故障转移,它的设计理念就是“注册中心”。 你可以认为它是一个存储服务地址信息的大本…

鸿蒙Harmony应用开发—ArkTS声明式开发(通用属性:焦点控制)

自定义组件的走焦效果&#xff0c;可设置组件是否走焦和具体的走焦顺序&#xff0c;tab键或者方向键切换焦点。 说明&#xff1a;从API Version 8开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 focusable focusable(value: boolean) 设…

目标检测——摩托车头盔检测数据集

一、简介 首先&#xff0c;摩托车作为一种交通工具&#xff0c;具有高速、开放和稳定性差的特点&#xff0c;其事故发生率高&#xff0c;伤亡率排在机动车辆损伤的首位。因此&#xff0c;摩托车乘员头盔对于保护驾乘人员头部安全至关重要。在驾乘突发状况、人体受冲击时&#…

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:Blank)

空白填充组件&#xff0c;在容器主轴方向上&#xff0c;空白填充组件具有自动填充容器空余部分的能力。仅当父组件为Row/Column/Flex时生效。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件…

昇腾ACL应用开发之硬件编解码dvpp

1.前言 在我们进行实际的应用开发时&#xff0c;都会随着对一款产品或者AI芯片的了解加深&#xff0c;大家都会想到有什么可以加速预处理啊或者后处理的手段&#xff1f;常见的不同厂家对于应用开发的时候&#xff0c;都会提供一个硬件解码和硬件编码的能力&#xff0c;这也是抛…

Redis核心数据结构之字典(二)

字典 解决键冲突 当有两个或以上数量的键被分配到了一个哈希表数组的同一个索引上面&#xff0c;我们称这些键发生了冲突(collision)。 Redis的哈希表使用链地址法(separate chaining)来解决键冲突&#xff0c;每个哈希表节点都有一个next指针&#xff0c;多个哈希表节点可以…

Vue.js 实用技巧:深入理解 Vue.mixin

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

flink重温笔记(十):Flink 高级 API 开发——flink 四大基石之 State(涉及Checkpoint)

Flink学习笔记 前言&#xff1a;今天是学习 flink 的第 10 天啦&#xff01;学习了 flink 四大基石之 State &#xff08;状态&#xff09;&#xff0c;主要是解决大数据领域增量计算的效果&#xff0c;能够保存已经计算过的结果数据状态&#xff01;重点学习了 state 的类型划…

力扣hot100:240.搜索二维矩阵II(脑子)

吉大21级算法分析与设计的一道大题&#xff0c;由于每一行都是排好序的直接逐行二分 可以达到&#xff1a;O(mlogn)。但是这里追求更广的思路可以使用其他方法。 矩阵四分&#xff1a; 在矩阵中用中心点比较&#xff0c;如果target大于中心点的值&#xff0c;则由于升序排列&am…

超全Chat GPT论文修改指令

文献综述指令润色修改指令论文选题指令论文大指令研究理论指令论文致谢指令参考文献指令论文润色整体逻辑论文整体优化提问指令 1&#xff0e;文献综述指令 请你帮我写一份关于&#xff08;研究主题&#xff09;的文献综述。我的论文选题方向是 XXXX &#xff0c;我已经找到了…

一次电脑感染Synaptics Pointing Device Driver病毒的经历,分享下经验

没想到作为使用电脑多年的老司机也会电脑中病毒&#xff0c;周末玩电脑的时候突然电脑很卡&#xff0c;然后自动重启&#xff0c;奇怪&#xff0c;之前没出现这个情况。 重启后电脑开机等了几十秒&#xff0c;打开任务管理器查看开机进程&#xff0c;果然发现有个Synaptics Po…

C语言实现回调函数

C语言实现回调函数 一、回调函数概念1.1 什么叫函数指针 二、回调函数案例 一、回调函数概念 回调函数就是一个被作为参数传递的函数。在C语言中&#xff0c;回调函数只能使用函数指针实现&#xff0c;在C、Python、ECMAScript等更现代的编程语言中还可以使用仿函数或匿名函数…

应用层DDoS防护:理解、必要性与实现策略

一、应用层简介 应用层&#xff0c;也称作第七层&#xff0c;是OSI&#xff08;开放系统互联&#xff09;模型中的最高层。在这一层&#xff0c;数据以特定的应用程序协议格式进行传输&#xff0c;如HTTP、FTP、SMTP等。应用层的主要职责是为用户提供网络服务&#xff0c;如文…

[嵌入式系统-37]:龙芯1B 开发学习套件 -6-协处理器CP0之CPU异常处理与外部中断控制器的中断处理

目录 一、MPIS CPU Core与32个异常exception 1.1 龙芯1B的MIPS CPU IP Core 1.2 MIP32指令系统 1.3 MIPS CPU寄存器 1.4 MIPS CPU的异常向量与异常向量号 1.5 龙芯异常exception与中断interrupt的区别 二、协议处理器CP0的中断控制与8个中断 2.1 CP0概述 2.2 协处理器…

【C++精简版回顾】18.文件操作

1.文件操作头文件 2.操作文件所用到的函数 1.文件io 1.头文件 #include<fstream> 2.打开文件 &#xff08;1&#xff09;函数名 文件对象.open &#xff08;2&#xff09;函数参数 /* ios::out 可读 ios::in 可…

类与对象(三)--static成员、友元

文章目录 1.static成员1.1概念&#x1f3a7;面试题✒️1.2static的特性&#x1f3a7;1.3思考&#x1f3a7; 2.友元2.1什么是友元&#xff1f;&#x1f3a7;2.2两种友元关系&#xff1a;&#x1f3a7; 1.static成员 1.1概念&#x1f3a7; &#x1f50e; static关键字用于声明类…

IO接口 2月5日学习笔记

1.fgetc 用于从文件中读取一个字符&#xff0c;fgetc 函数每次调用将会返回当前文件指针所指向的字符&#xff0c;并将文件指针指向下一个字符。 int fgetc(FILE *stream); 功能: 从流中读取下一个字符 参数: stream:文件流指针 返回值: …

【Docker】若依ruoyi项目部署

一 搭建局域网 1 # 搭建net-ry局域网&#xff0c;用于部署若依项目docker network create net-ry --subnet172.68.0.0/16 --gateway172.68.0.1 # 注意1&#xff1a;关闭宿主机的防火墙&#xff0c;否者容器内部的MySQL、redis等服务&#xff0c;外部访问不了&#xff1b;开放…

Linux 文件系列:深入理解文件描述符fd,重定向,自定义shell当中重定向的模拟实现

Linux 文件系列:深入理解文件fd,重定向,自定义shell当中重定向的模拟实现 一.预备知识二.回顾C语言中常见的文件接口跟重定向建立联系1.fopen函数的介绍2.fclose函数的介绍3.代码演示1.以"w"(写)的方式打开2.跟输出重定向的联系3.以 "a"(追加)的方式打开4.…