每日一题-贪心算法

news/2025/1/11 18:09:21/

目录

前言

买入股票的最佳时机(1)

买入股票的最好时机(2)

前言

当你踏上算法>贪心算法的旅程,仿佛置身于一场智慧的盛宴,每一步都是对问题解决方案的审慎选择,每一次决策都是对最优解的向往。算法>贪心算法以其简洁高效的特性,被广泛运用于解决各类优化问题,无论是在算法竞赛的舞台上,还是在实际工程的应用中,都展现着其独特的魅力。

在这篇博客中,我将带领大家深入探索算法>贪心算法的精髓,从经典问题到实际案例,一一呈现其妙不可言喻之处。透过习题讲解,我们将一同揭开算法>贪心算法的神秘面纱,探寻其中的逻辑与技巧,希望能够为各位读者提供一份清晰的指南,助力你们在算法的海洋中航行无忧。

无论是初学者抑或是算法高手,都能从中收获不少启发与收获。让我们一起启程,探索算法>贪心算法的奥秘,开启算法之旅的新篇章!

买入股票的最佳时机(1)

. - 力扣(LeetCode)

我们可以按照以卖的点的位置进行思考,以 i 位置进行出售,就只需要求 0 ~ i - 1 位置内买入的最小值即可,然后把每个位置的最大值求出来,即可通过O(n)的复杂度解决这道问题。   

 

代码实现,我把上面的思路分析都用代码注释标注了

class Solution {public int maxProfit(int[] arr) {int min = Integer.MAX_VALUE;// 记录i - 1位置的最小值int max = Integer.MIN_VALUE;// 卖出股票会得到的最大利润for (int i = 0; i < arr.length - 1; i++) {min = Math.min(min, arr[i]);// 计算前面的最小值max = Math.max(max, arr[i + 1] - min);// 更新最大值}return Math.max(max, 0);}
}

买入股票的最好时机(2)

. - 力扣(LeetCode)

 算法>贪心算法的思想是在每一步都选择当前状态下的最优解,以期望最终获得全局的最优解。对于这个问题,我们可以通过找到股票价格的递增区间,并在每个递增区间内进行买入和卖出操作,以获得最大利润。

这一题的解决方案就和下图一样画出增长区间,求出所有增长区间的值之和,也就是最终答案。

  1. 遍历股票价格数组,从第二天开始。
  2. 如果当前股票价格比前一天高,说明可以在前一天买入,当前天卖出,获得利润。
  3. 将每次获得的利润累加起来,得到最终的总利润。

class Solution {public int maxProfit(int[] prices) {int result = 0;for(int i = 1;i < prices.length;i++){//从第二个位置开始if(prices[i] > prices[i - 1]){
//通过求每一段增长区间的值来求最终增长区间的值(每个增长区间我都要)result += prices[i] - prices[i - 1];}}return result;}
}

因为买入股票最好时机3和4都是动态规划实现的,我将在下一篇进行讲解 

总结

在这篇博客中,我们将深入探讨算法>贪心算法的精髓,从经典问题到实际案例,一一呈现其独特的魅力。通过习题讲解,我们将揭开算法>贪心算法的神秘面纱,探寻其中的逻辑与技巧,为读者提供清晰的指南。无论是初学者还是算法高手,都能从中获得启发与收获。让我们一起启程,探索算法>贪心算法的奥秘,开启算法之旅的新篇章!此外祝大家周末愉快。


http://www.ppmy.cn/news/1450996.html

相关文章

MySQL常见问题解决和自动化安装脚本

常见问题 MySQL密码正确但无法登录的情况 这种情况一般都是因为缓存&#xff0c;使用mysql -u root -p123456直到成功登陆为止&#xff0c;并且进入之后重新修改密码&#xff0c;多次重复修改密码的命令并且再一次清除缓存后退出。 ALTER USER rootlocalhost IDENTIFIED WIT…

Springboot+mybatis升级版(Postman测试)

一、项目结构 1.导入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apach…

ssm092基于Tomcat技术的车库智能管理平台+jsp

车库智能管理平台设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本车库智能管理平台就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短…

Ant Design助力:实现用户列表的优雅展示与管理

文章目录 概要前端讲解登录组件注册组件用户列表组件 后端讲解连接数据库db.js路由routes.jsexpress应用app.js 启动项目小结 概要 在上一篇博客&#x1f6aa;中&#xff0c;我们已经成功实现了登录注册系统的基本功能。现在&#xff0c;我们将进一步完善系统&#xff0c;实现…

Luminar开始为沃尔沃生产下一代激光雷达传感器

在自动驾驶技术的浪潮中&#xff0c;激光雷达&#xff08;LiDAR&#xff09;传感器以其高精度和强大的环境感知能力&#xff0c;逐渐成为了该领域的技术之星。Luminar&#xff08;路安达&#xff09;公司作为自动驾驶技术的领军企业&#xff0c;近日宣布已开始为沃尔沃汽车生产…

【数据结构】Map和Set(1)

&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;个人主页&#x1f388;&#x1f388;&#x1f388;&#x1f388;&#x1f388; &#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;&#x1f9e7;数据结构专栏&#x1f388;&#x1f388;&#x1f388;&…

数据结构--栈与队列【您的关注是我创作的动力!】

文章目录 栈什么是栈&#xff1f;栈的具体实现 队列什么是队列&#xff1f;队列的实现 栈 什么是栈&#xff1f; 栈也是顺序表的一种&#xff0c;栈的逻辑实现是先进后出&#xff08;后进先出&#xff09;就跟子弹夹一样。 具体逻辑就是它只允许在固定的一端进行数据的插入与…

校园管理系统的设计与实现 - 免费源码(私信领取)

1. 研究目的 本项目旨在设计并实现一个校园管理系统&#xff0c;旨在提高学校管理效率&#xff0c;优化校园资源配置&#xff0c;提升教育教学质量&#xff0c;以及提供便捷的信息服务平台。 2. 研究要求 a. 需求分析 通过深入了解学校管理流程和需求&#xff0c;以及教职员…