贪心算法-

代码随想录

什么是贪心

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

这么说有点抽象,来举一个例子:

例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?

指定每次拿最大的,最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。

再举一个例子如果是 有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。

什么时候用贪心 

贪心算法、动态规划、机器学习都属于优化算法。当题目要求最优解的时候基本上都是贪心算法或者动态规划

贪心算法并没有固定的套路

所以唯一的难点就是如何通过局部最优,推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢?有没有什么固定策略或者套路呢?

不好意思,也没有! 靠自己手动模拟,如果模拟可行,就可以试一试贪心策略,如果不可行,可能需要动态规划。

有同学问了如何验证可不可以用贪心算法呢?

最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧

可有有同学认为手动模拟,举例子得出的结论不靠谱,想要严格的数学证明。

一般数学证明有如下两种方法:

  • 数学归纳法
  • 反证法

看教课书上讲解贪心可以是一堆公式,估计大家连看都不想看,所以数学证明就不在我要讲解的范围内了,大家感兴趣可以自行查找资料。

面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了

举一个不太恰当的例子:我要用一下1+1 = 2,但我要先证明1+1 为什么等于2。严谨是严谨了,但没必要。

虽然这个例子很极端,但可以表达这么个意思:刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心

贪心一般解题步骤

贪心算法一般分为如下四步:

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

这个四步其实过于理论化了,我们平时在做贪心类的题目 很难去按照这四步去思考,真是有点“鸡肋”。

做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。

题目

455.分发饼干

455. 分发饼干_侯孟禹的博客-CSDN博客

53. 最大子序和

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

思路:1.因为求最大和,第一个数就是正数才能成为优解,所以当第一个数是负数的时候就跳过

           2.求和时,一旦当前和为负数则直接放弃(新加上的数肯定是负数),从下一个数作为第一个数重新开始。
 

代码:

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;//不能设成0,否则序列[-1]会返回空,正确返回-1int 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;}
};

 本题动态规划解法:代码随想录

122.买卖股票的最佳时机 II

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

思路:

如果想到其实最终利润是可以分解的,那么本题就很容易了!

如何分解呢?

假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度,而不是从 0 天到第 3 天整体去考虑!

那么根据 prices 可以得到每天的利润序列:(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

class Solution {
public:int maxProfit(vector<int>& prices) {int result = 0;for (int i = 1; i < prices.size(); i++) {result += max(prices[i] - prices[i - 1], 0);}return result;}
};

55. 跳跃游戏

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

我的想法:

        第一版:从后往前推,sum计算从后往前的和,nums[len-2]>1;nums[len-2] + nums[len-3]>2;

代码:

class Solution {
public:bool canJump(vector<int>& nums) {if(nums.size() == 1) return true;if(nums[0] == 0) return false;int index = nums.size() - 2;int sum = 0;int count = 1;for(int i = index; i >= 0; i--){sum += nums[i];if(sum < count){return false;}count++;}return true;}
};

存在的问题:[2,0,0]这样是过不了的

正确答案:

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点!

每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。

贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点

代码:

class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;if (nums.size() == 1) return true; // 只有一个元素,就是能达到for (int i = 0; i <= cover; i++) { // 注意这里是小于等于covercover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了}return false;}
};

 45.跳跃游戏 II

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

思路:

        1.其实就是一个更新最大范围的过程,只需要统计通过多少次更新就可以达到最大长度

curDistance表示0-2这个范围

nextDistance表示遍历下标0-2后的最大范围即max(nums[0]+0, nums[1]+3, nums[2]+1) =下标4

当遍历到下标2的时候就表示要在走一步了,此时步数count++,下一步走的范围就是nextDistance的范围。当nextDistance>=最大长度的时候就表示够了

class Solution {
public:int jump(vector<int>& nums) {int count = 0;int curDistance = 0;int nextDistance = 0;for(int i = 0; i < nums.size() - 1; i++){nextDistance = max(nextDistance, nums[i] + i);if(i == curDistance){curDistance = nextDistance;count++;if(curDistance >= nums.size() - 1) return count;}}return count;}
};

1005.K次取反后最大化的数组和

 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

我的想法:1.排序 2.从左到右遇到负数取反,同时k-- 3.剩下k-i%2取余 4.排序,对最小的如果取余为1则取反否则不变 5.求和

我的代码:

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int i = 0;for(; i < k && i < nums.size(); i++){if(nums[i] < 0){nums[i] = 0 - nums[i];}else{break;}}sort(nums.begin(), nums.end());if((k-i)%2 == 1){nums[0] = 0 - nums[0];}int sum = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i];}return sum;}
};

 随想录思想:

         1.对我的想法中排序为绝对值排序,从右往左遇到负数取反k--,剩余在第一个元素(最小的)上处理,可以减少一次排序 

代码:

class Solution {
static bool cmp(int a, int b) {return abs(a) > abs(b);
}
public:int largestSumAfterKNegations(vector<int>& A, int K) {sort(A.begin(), A.end(), cmp);       // 第一步for (int i = 0; i < A.size(); i++) { // 第二步if (A[i] < 0 && K > 0) {A[i] *= -1;K--;}}if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步int result = 0;for (int a : A) result += a;        // 第四步return result;}
};

134. 加油站

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

代码随想录

 理解不过来

135. 分发糖果 

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

官方思路及解法

我们可以将「相邻的孩子中,评分高的孩子必须获得更多的糖果」这句话拆分为两个规则,分别处理。

左规则:当 ratings[i−1]<ratings[i]时,i 号学生的糖果数量将比 i−1 号孩子的糖果数量多。

右规则:当 ratings[i]>ratings[i+1]时,i 号学生的糖果数量将比 i+1号孩子的糖果数量多。

我们遍历该数组两次,处理出每一个学生分别满足左规则或右规则时,最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。

class Solution {
public:int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(), 1);// 从前向后for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;}// 从后向前for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] ) {candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);}}// 统计结果int result = 0;for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];return result;}
};

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

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

相关文章

linux驱动之input子系统简述

文章目录 一、什么是input子系统二、内核代码三、代码分析 一、什么是input子系统 Input驱动程序是linux输入设备的驱动程序&#xff0c;我们最常见的就按键&#xff0c;触摸&#xff0c;插拔耳机这些。其中事件设备驱动程序是目前通用的驱动程序&#xff0c;可支持键盘、鼠标…

邮件营销方案

互联网的快速发展&#xff0c;使得新媒体营销、短视频营销、微信营销等新型营销方式成为主流。但是邮件营销仍然是性价比很高的营销方式之一&#xff0c;它不仅可以帮助你与潜在客户建立联系、传达信息并促进销售&#xff0c;同时也是维系老客户的重要手段之一。特别是对于外贸…

解答嵌入式和单片机的关系

嵌入式系统是一种特殊的计算机系统&#xff0c;用于特定任务或功能。而单片机则是嵌入式系统的核心部件之一&#xff0c;是一种在单个芯片上集成了处理器、内存、输入输出接口等功能的微控制器。刚刚好我这里有一套单片机保姆式教学&#xff0c;里面有编程教学、问题讲解、语言…

C++:优先级队列模拟实现和仿函数的概念使用

文章目录 使用方法Compare仿函数一些场景模板参数和函数参数 本篇总结优先级队列 使用方法 首先在官网查看它的一些用法 template <class T, class Container vector<T>,class Compare less<typename Container::value_type> > class priority_queue;从…

【golang】深入理解Go语言垃圾回收(GC)

垃圾回收 垃圾回收版本1.3之前标记-清除&#xff08;mark and sweep&#xff09;算法标记-清除&#xff08;mark and sweep&#xff09;的缺点 版本1.5的三色并发标记法没有STW的三色标记法屏障机制强-弱 三色不等式插入屏障删除屏障 版本1.8的混合写屏障&#xff08;hybrid wr…

【计算机网络】——数据链路层(应用:局域网、广域网、设备 )

//仅做个人复习和技术交流&#xff0c;图片取自王道考研&#xff0c;侵删 一、大纲 1、介质访问控制 信道划分介质访问控制 随机访问介质访问控制 2、局域网 3、广域网 4、数据链路层设备 二、局域网 1、局域网基本概念和体系结构 局域网(LocalArea Network): 简称LAN&…

[maven] 实现使用 plugin 及 properties 简述

[maven] 实现&使用 plugin 及 properties 简述 这章内容&#xff0c;我个人感觉可看可不看……&#xff1f; 不过课都上了&#xff0c;笔记 &#x1f4d2; 补完才对得起自己嘛 plugins 主要讲一下 maven 的 plugin 时怎么实现的&#xff0c;以及项目中怎么调用自己实现…

实现电商跨平台订单每日自动对账

场景描述&#xff1a; 多数商家都存在多电商平台同时经营的情况&#xff0c;而进行订单对账则是相关业务或财务人员的每日必修课。比如商家在天猫&#xff0c;苏宁&#xff0c;1号店&#xff0c;京东等均有运营店铺&#xff0c;每天需要通过各电商后台系统抓单打单&#xff0c…

若依cloud -【 100 ~ 103 】

100 分布式日志介绍 | RuoYi 分布式日志就相当于把日志存储在不同的设备上面。比如若依项目中有ruoyi-modules-file、ruoyi-modules-gen、ruoyi-modules-job、ruoyi-modules-system四个应用&#xff0c;每个应用都部署在单独的一台机器里边&#xff0c;应用对应的日志的也单独存…

springboot如何接入netty,实现在线统计人数?

springboot如何接入netty&#xff0c;实现在线统计人数&#xff1f; Netty 是 一个异步事件驱动的网络应用程序框架 &#xff0c;用于快速开发可维护的高性能协议服务器和客户端。 Netty ​ 是一个 NIO 客户端服务器框架 ​&#xff0c;可以快速轻松地开发协议服务器和客户端等…

微表情识别API + c++并发服务器系统

微表情识别API c并发服务器系统 该项目只开源c并发服务器程序&#xff0c;模型API部分不开源 地址&#xff1a;https://github.com/lin-lai/-API- 更新功能 4.1版本 改用epoll实现IO多路复用并发服务器 项目介绍 本项目用于检测并识别视频中人脸的微表情 目标任务: 用户上…

【李沐深度学习笔记】线性代数

课程地址和说明 线性代数p1 本系列文章是我学习李沐老师深度学习系列课程的学习笔记&#xff0c;可能会对李沐老师上课没讲到的进行补充。 线性代数 标量 标量&#xff08;scalar&#xff09;&#xff0c;亦称“无向量”。有些物理量&#xff0c;只具有数值大小&#xff0c…

基于微信小程序的校园失物招领系统设计与实现(源码+lw+部署文档+讲解等)

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…

Qt创建线程(使用moveToThread方法创建子线程)

1.moveTothread方法: &#xff08;1&#xff09;要使用moveToThread方法必须继承与QObject类 &#xff08;2&#xff09;创建任务对象时不能指定父对象 例子&#xff1a; MyWork* work new MyWork(this); // error MyWork* work new MyWork; // ok &#xff08;3&#…

北工大汇编题——分支程序设计

题目要求 信息检素程序设计&#xff1a;在数据区&#xff0c;有9个不同的信息&#xff0c;编号 0-8&#xff0c;每个信息包括20 个字符。从键盘接收 0-8 之间的一个编号&#xff0c;然后再屏幕上显示出相应编号的信息内容&#xff0c;按“q”键退出 完整代码 DATAS SEGMENTn0…

搭建SpringBoot项目三种方式(超详细版)

目录 一、官网下载压缩包解压 二、通过Idea脚手架搭建 三、Spring Boot项目结构 3.1 pom.xml文件 3.2 启动类 3.3 配置文件 四、通过创建Maven项目添加依赖 一、官网下载压缩包解压 接下来我们搭建一个SpringBoot项目&#xff0c;并引入SpringMVC的功能&#xff0c;首先…

自学WEB服务器搭建01-安装Express+Node.js框架完成Hello World!

一、前言&#xff0c;网站开发扫盲知识 1.网站搭建开发包括什么&#xff1f; 前端、后端&#xff08;服务端&#xff09;数据库 前端开发主要涉及用户界面&#xff08;UI&#xff09;和用户体验&#xff08;UX&#xff09;&#xff0c;负责实现网站的外观和交互逻辑。前端开发…

多线程进阶:常见的锁策略、CAS

之前我们所了解的属于多线程的初阶内容。今天开始&#xff0c;我们进入多线程进阶的学习。 锁的策略 乐观锁 悲观锁 这不是两把具体的锁&#xff0c;应该叫做“两类锁” 乐观锁&#xff1a;预测锁竞争不是很激烈&#xff08;这里做的工作可能就会少一些&#xff09; 悲观锁…

3.6+铁死亡+WGCNA+机器学习

今天给同学们分享一篇3.6铁死亡WGCNA机器学习的生信文章“Identification of ferroptosis related biomarkers and immune infiltration in Parkinsons disease by integrated bioinformatic analysis”&#xff0c;这篇文章于2023年3月14日发表在BMC Med Genomics期刊上&#…

Mac电脑信息大纲记录软件 OmniOutliner 5 Pro for Mac中文

OmniOutliner 5 Pro是一款专业级的Mac大纲制作工具&#xff0c;它可以帮助用户更好地组织和管理信息&#xff0c;以及制作精美的大纲。以下是OmniOutliner 5 Pro的主要功能和特点&#xff1a; 强大的大纲组织和管理功能。OmniOutliner 5 Pro为用户提供了多层次的大纲结构&…