贪心算法入门(二)

相关文章

贪心算法入门(一)-CSDN博客

1.什么是贪心算法?

        贪心算法是一种解决问题的策略,它将复杂的问题分解为若干个步骤,并在每一步都选择当前最优的解决方案,最终希望能得到全局最优解。这种策略的核心在于“最优”二字,意味着我们追求的是以最少的时间和精力,快速获得正确的结果。

        然而,“希望得到全局最优解”就表示贪心算法并不意味着一定能得到全局最优解。实际上,并不是所有问题都可以通过贪心策略解决。为了确保贪心策略的有效性,需要对其进行严格的证明。而且,不同的问题往往需要采用不同的贪心策略。

        如果你觉得这一点仍然比较抽象,接下来我将通过五道具体的例题来详细说明贪心算法的应用及其背后的思路。

2.递增的三元子序列

334. 递增的三元子序列 - 力扣(LeetCode)

这道题跟在贪心算法入门(一)中的最长递增子序列的思路是一样的。在最长递增子序列中使用了贪心加二分的策略。

回顾一下上题的贪心策略:选用链表接收子序列。依次检索数组中的每个值,如果扫描的值大于链表中的最后一个值则添加到链表末尾,如果小于则用二分寻找合适的位置插入,插入的位置要严格保证大于链表左边的值。最后返回链表的大小,就是最长递增子序列的长度。

而该题已经确定了最长递增子序列的长度,只需要判断在数组中是否存在这样的三元递增子序列即可,所以可以省略用链表表示变量,用两个int型变量a,b表示三元连续递增的第一个位置和第二个位置代替,如果检索到某个值大于b时直接返回true。

注意a,b的初始化,a的初始化就是数组下标0的值,b的值可以初始化为一个最大值。

2.1 代码实现

class Solution {public boolean increasingTriplet(int[] nums) {int n = nums.length;int a  = nums[0], b = Integer.MAX_VALUE;for(int i = 1; i < n; i++){if(nums[i] > b) return true;else if(nums[i] > a) b = nums[i];else a = nums[i];}return false;}
}

该题把值插入到正确位置使用了两个条件判断,如果大于第二个位置b的值说明改值可以接在b后面组成三元递增序列,所以这里就知道为什么要把b初始化为最大值了。如果第一个条件不成立则判断是否大于a,如果成立则说明a < x <= b,则把b更新为x,否则说明x比a第一个位置的还小,更新a位置的值。

3.最长连续递增序列

674. 最长连续递增序列 - 力扣(LeetCode)

 从给出的示例1看,这道题跟最长递增子序列的区别就是找出的递增序列是不能被间隔的。

那么这道题同样也可以用上道题的思路做,但是不用这么麻烦,因为这道题的要求更简单。

从下标为1的位置开始检索,判断是否大于前一个位置的数,如果满足则是递增的,此时len加1(len表示最长递增子序列的长度,初始化为1,因为单独的一个数也可以看成一个递增子序列),直到扫描的位置不满足大于前一个位置为止,更新ret为ret和len的较大值。这时无需再跳回去以第一个位置为起点计算,因为前面扫描过的位置中无论以哪个位置为起点的最长连续递增自序列的长度都不会超过刚刚的计算出的len值。

3.1 代码实现

class Solution {public int findLengthOfLCIS(int[] nums) {int ret = 1, tmp = 1;for(int i = 1; i < nums.length; i++){if(nums[i] > nums[i - 1]) tmp++;else tmp = 1;ret = Math.max(ret,tmp);}return ret;}
}

4.买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣(LeetCode)

理解题目: 选择一天买入股票,再选择一天卖出股票,买入肯定要在卖出之前(对应数组下标前后关系),且要利润最大,就说明希望以选择买入的值最小,选择卖出的最大。

这道题跟递增序列的思路也很像,我们只需一次扫描数组,找到所有的二元递增序列,并找到差值最大的那个就是答案了。只不过这道题每次更新的结果值不是长度,而是a,b之间的差值。

4.1 代码实现

class Solution {public int maxProfit(int[] prices) {int ret = 0, a = prices[0];for(int x : prices){if(x > a) ret = Math.max(ret, x - a);else a = x;}return ret;}
}

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

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

该题与上一题的区别就是不限制你买入的次数和卖出的次数,所以可以进行多次交易,然后求最大利润。

这道题的思路相比1会更简单,因为我们只需把所有上升的部分相加起来就是最大利润。数组我们可以把它映射到折线图中:

5.1 代码实现

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int ret = 0;for(int i = 1; i < n; i++){if(prices[i] > prices[i - 1]) ret += prices[i] - prices[i - 1];}return ret;}
}

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

1005. K 次取反后最大化的数组和 - 力扣(LeetCode)

这道题的思路也很简单,要最后的和最大,首先尽量把数组中原本的负数取反变为正数,如果k小于等于数组中原本的负数个数,那么让这些负数全部取反为正即和最大。如果还有剩余次数,此时数组中都是非负整数了,如果剩余次数为偶数则可以维持不变,如果为奇数就说明要选取一个最小的非负整数取反才能最大。

6.1 代码实现

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {int min = 200, m = 0, sum = 0;for(int x : nums){if(x  < 0) m++;min = Math.min(min, Math.abs(x));}if(m > k){ Arrays.sort(nums);for(int i = 0; i < k; i++) sum += -nums[i];for(int i = k; i < nums.length; i++) sum += nums[i];}else{for(int i = 0; i < nums.length; i++) sum += Math.abs(nums[i]);if((k - m) % 2 == 1) sum -= 2 * min;}return sum;}
}

 该题使用了一些优化,当负数个数大于k的时候才需要使用Arrays.sort(nums);进行排序,将负数归到最前,然后计算结果值。如果负数小于k的时候就无需sort,直接用Math.abs(nums[i]);函数将数组中的值相加,最后再判断剩余次数的奇偶性进行后续操作。

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

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

相关文章

Autosar CP 基于CAN的时间同步规范导读

Autosar CP 基于CAN的时间同步规范主要用途 实现精确时间同步 提供了一种在CAN总线上准确分发时间信息的机制&#xff0c;确保连接到CAN网络的各个电子控制单元&#xff08;ECU&#xff09;能够共享精确的公共时间基准&#xff0c;对于需要精确时间协调的汽车系统功能&#xff…

前端常用布局模板39套,纯CSS实现布局

前端常用布局模板39套&#xff0c;纯CSS实现布局 说明 写博客、官网、管理后台都可以参考以下布局模板&#xff0c;实现模板布局的方式包含&#xff1a;flex、CSS、HTML5、Layout。 不需要下载积分&#xff0c;没有特殊库引用&#xff0c;不用安装任何插件&#xff0c;打开资源…

jmeter常用配置元件介绍总结之后置处理器

系列文章目录 安装jmeter jmeter常用配置元件介绍总结之后置处理器 8.后置处理器8.1.CSS/JQuery提取器8.2.JSON JMESPath Extractor8.3.JSON提取器8.4.正则表达式提取器8.5.边界提取器8.5.Debug PostProcessor8.6.XPath2 Extractor8.7.XPath提取器8.8.结果状态处理器 8.后置处理…

边缘计算在智能交通系统中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 边缘计算在智能交通系统中的应用 边缘计算在智能交通系统中的应用 边缘计算在智能交通系统中的应用 引言 边缘计算概述 定义与原…

Vue 项目打包后环境变量丢失问题(清除缓存),区分.env和.env.*文件

Vue 项目打包后环境变量丢失问题&#xff08;清除缓存&#xff09;&#xff0c;区分.env和.env.*文件 问题背景 今天在导报项目的时候遇到一个问题问题&#xff1a;在开发环境中一切正常&#xff0c;但在打包后的生产环境中&#xff0c;某些环境变量&#xff08;如 VUE_APP_B…

十三、注解配置SpringMVC

文章目录 1. 创建初始化类&#xff0c;代替web.xml2. 创建SpringConfig配置类&#xff0c;代替spring的配置文件3. 创建WebConfig配置类&#xff0c;代替SpringMVC的配置文件4. 测试功能 1. 创建初始化类&#xff0c;代替web.xml 2. 创建SpringConfig配置类&#xff0c;代替spr…

(干货)Jenkins使用kubernetes插件连接k8s的认证方式

#Kubernetes插件简介 Kubernetes 插件的目的是能够使用 Kubernetes 配合&#xff0c;实现动态配置 Jenkins 代理&#xff08;使用 Kubernetes 调度机制来优化负载&#xff09;&#xff0c;在执行 Jenkins Job 构建时&#xff0c;Jenkins Master 会在 kubernetes 中创建一个 Sla…

俏美韵从心出发,与女性一道为健康生活贡献力量

近期发布的《2025 全球食品与饮料》报告中显示&#xff0c;“回归本源”为2025年食品饮料赛道的趋势之一&#xff0c;消费者对于产品成分要求越来越严格&#xff0c;尤其是女性消费者&#xff0c;对成分是否自然&#xff0c;营养含量等方面越来越看重&#xff0c;俏美韵品牌从产…

区块链技术在慈善捐赠中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 区块链技术在慈善捐赠中的应用 区块链技术在慈善捐赠中的应用 区块链技术在慈善捐赠中的应用 引言 区块链技术概述 定义与原理 发…

mongoDB的安装及使用

mongodb的安装参考&#xff1a; Centos系统中mongodb的安装详解_centos安装mongodb-CSDN博客 不要下载最新的版本&#xff0c;新的版本中mongo命令无法使用&#xff0c;也就是安装后不能通过mongo命令登录&#xff0c;我这里使用5.0.30版本&#xff1b; mongodb客户端demo: …

DNS面临的4大类共计11小类安全风险及防御措施

DNS在设计之初&#xff0c;并未考虑网络安全限制&#xff0c;导致了许多问题。DNS安全扩展(DNSSEC)协议的开发旨在解决DNS的安全漏洞&#xff0c;但其部署并不广泛&#xff0c;DNS仍面临各种攻击。接下来我们一起看下DNS都存在哪些安全攻击及缓解措施&#xff0c;旨在对DNS安全…

MySql结合element-plus pagination的分页查询

实现效果如下&#xff1a; 重点&#xff1a;使用mysql查询的limit和offset 原生SQL写法&#xff1a; select c.id as deptid,c.name as department,position,a.name staffname,2024-11 as shijian ,CASE WHEN b.shijian IS NULL THEN no ELSE yes END AS submit from fa_wecom…

ubuntu20.04安装FLIR灰点相机BFS-PGE-16S2C-CS的ROS驱动

一、Spinnaker 安装 1.1Spinnaker 下载 下载地址为&#xff1a; https://www.teledynevisionsolutions.com/support/support-center/software-firmware-downloads/iis/spinnaker-sdk-download/spinnaker-sdk–download-files/?pnSpinnakerSDK&vnSpinnakerSDK 在上述地址中…

什么是数字图像?

点赞 关注 收藏 学会了 什么是数字图像&#xff1f; 本文可在公众号「德育处主任」免费阅读 弄懂数字图像的概念对学习计算机视觉很有帮助。 那么&#xff0c;什么是数字图像&#xff1f; 字面意思&#xff0c;数字图像就是有数字组成图像。通常由像素&#xff08;Pixel&…

2024年11月13日

1.创业法律指南 留置权和其他三个权 定金和订金 一般保证和连带保证 1.案例 物权编之担保法律制度案例一 冯系养鸡专业户&#xff0c;为改建鸡会和引进良种需资金20万元。冯向陈借款10万元&#xff0c;以自己的一套价值10万元的音响设备抵押&#xff0c;双方立有抵押字据&a…

Android OpenGL ES详解——立方体贴图

目录 一、概念 二、如何使用 1、创建立方体贴图 2、生成纹理 3、设置纹理环绕和过滤方式 4、激活和绑定立方体贴图 三、应用举例——天空盒 1、概念 2、加载天空盒 3、显示天空盒 4、优化 四、应用举例——环境映射:反射 五、应用举例——环境映射:折射 六、应用…

2024版本IDEA创建Sprintboot项目下载依赖缓慢

目录 步骤一&#xff1a;在IDEA中搜索Maven(双击shift) 步骤二&#xff1a;找到Maven下的settings.xml文件修改镜像 ​编辑 ​编辑​编辑 步骤三&#xff1a;用VScode打开settings.xml文件修改镜像 ​编辑 步骤一&#xff1a;在IDEA中搜索Maven(双击shift) 步骤二&#xff…

Android Framework AMS(16)进程管理

该系列文章总纲链接&#xff1a;专题总纲目录 Android Framework 总纲 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;本章节主要解读AMS 进程方面的知识。关注思维导图中左上侧部分即可。 我们本章节主要是对Android进程管理相关知识有一个基本的了解。先来了解下L…

python购物计算 2024年6月青少年电子学会等级考试 中小学生python编程等级考试一级真题答案解析

目录 python购物计算 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序代码 四、程序说明 五、运行结果 六、考点分析 七、 推荐资料 1、蓝桥杯比赛 2、考级资料 3、其它资料 python购物计算 2024年6月 python编程等级考试一级编程题 一、题目要求 …

Pycharm PyQt5 环境搭建创建第一个Hello程序

第一步: 创建Pycharm项目,下载包: pip install PyQt5 -i https://pypi.tuna.tsinghua.edu.cn/simple/pip install PyQt5-tools -i https://pypi.tuna.tsinghua.edu.cn/simple/下载好了之后,可以看到相应包: PyQt5:PyQt5是一套Python绑定Digia QT5应用的框架。Qt库是最…