代码随想录训练营day49, 买卖股票的最佳时机I/II

news/2024/3/29 22:54:12/文章来源:https://blog.csdn.net/Southside3amurai/article/details/128108271

买卖股票的最佳时机

这题的特点就是只能买卖股票一次: 在某一天买入然后在某一天卖掉

贪心解法: 这个比较容易理解, 就是取坐左边最小值, 然后取右边最大值, 直接拉代码

class Solution {public int maxProfit(int[] prices) {int low = Integer.MAX_VALUE;int result = 0;for(int i = 0; i < prices.length; i++){//找到左边最小的low = Math.min(low, prices[i]);//直接取值result = Math.max(result, prices[i] - low);}return result;}
}

动规:

  1. 数组定义: dp[i][0]表示第i天持有股票所得最多现金(一开始现金是0, 那么持有后就是-prices[i]), dp[i][1]表示第i天不持有股票所得最多现金
  2. 确定递推公式,
    1. 如果第i天持有股票, 即dp[i][0]
      1. 如果i-1天就持有股票, 那么维持现状, 现在的现金就是昨天持有股票的所得现金(dp[i-1][0])
      2. 第i天才买入股票, 那么就是股票的现金-price[i], 比较两者最大值
    2. 如果第i天不持有股票, 即dp[i][1]
      1. 如果i-1天就不持有股票, 那么维持现状, 就是昨天没股票的现金(dp[i-1][1])
      2. 如果第i天卖掉股票, 按照股票价格+之前只有股票的情况(prices[i] + dp[i-1][0])
  3. 初始化:可以看出来基础都是从dp[i][0]何dp[i][1]推出 , dp[0][0]表示第0天就持有股票了, 所以dp[0][0] -= prices[0], dp[0][1]不持有股票就肯定是0
  4. 从前向后遍历
  5. 最后的dp[len - 1][1]就是结果, 因为不持有股票的情况肯定比持有时有钱
class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(prices == null || len == 0){return 0;}//创建一个二维dp数组int[][] dp = new int[len + 1][2];//初始化dp[0][0] -= prices[0];dp[0][1] = 0;//开始遍历for(int i = 1; i < len; i++){//持有股票的情况dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);//不持有股票的情况dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
}

也可以简化为一维数组版本

class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(len == 0 || prices == null){return 0;}int[] dp = new int[2];//一样进行初始化dp[0] -= prices[0];dp[1] = 0;//开始遍历, 这里往后推了一天for(int i = 1; i <= len; i++){//有股票: 之前就有/今天买的dp[0] = Math.max(dp[0], -prices[i - 1]);//无股票: 本来就没有, 和今天卖掉的dp[1] = Math.max(dp[1], prices[i - 1] + dp[0]);}return dp[1];}
}

买卖股票的最佳时机II

上一题是只能买卖一次, 这里是可以无限买卖

贪心算法:

之前已经提过, 就是相当于每天都交易, 然后只要交易结果是正数就加起来

class Solution {public int maxProfit(int[] prices) {int res = 0;for(int i = 1; i < prices.length; i++){res += Math.max(prices[i] - prices[i-1], 0);}return res;}
}

动态规划:

这里的dp数组定义和上一题是一模一样的, 唯一不同的地方,就是推导dp[i][0]的时候,第i天买入股票的情况

第i天持有股票, 要么是之前就有, 要么是第i天才买, 对于后者: 需要用之前已经有的现金-第i天的price

第i天不持有股票, 要么是之前就无, 要么是第i天才卖掉, 对于后者: 也是今天价格+之前有的情况

class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(len == 0 || prices == null){return 0;}int[][] dp = new int[len + 1][2];dp[0][0] -= prices[0];dp[0][1] = 0;//开始遍历for(int i = 1; i < len; i++){//持有股票---之前就有/今天买的(要加上之前的钱)dp[i][0] = Math.max(dp[i - 1][0], -prices[i] + dp[i - 1][1]);//没有股票----之前就没/今天卖掉的dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
}

优化版, 记住两点:

  1. 全部变成一维数组里, 所以直接把第一个中括号里的东西全部砍掉
  2. 因为这里往后推了一天, 这里的遍历要≤len; 同时price的价格要-1才是对的
class Solution {public int maxProfit(int[] prices) {int len = prices.length;if(len == 0 || prices == null){return 0;}int[] dp = new int[2];dp[0] -= prices[0];dp[1] = 0;//开始遍历for(int i = 1; i <= len; i++){//持有股票---之前就有/今天买的(要加上之前的钱)dp[0] = Math.max(dp[0], -prices[i - 1] + dp[1]);//没有股票----之前就没/今天卖掉的dp[1] = Math.max(dp[1], prices[i - 1] + dp[0]);}return dp[1];}
}

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

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

相关文章

【Rust日报】2022-11-29 Wirefish:基于 Tauri 的跨平台数据包嗅探器

Wirefish&#xff1a;基于 Tauri 的跨平台数据包嗅探器作者 stefanodevenuto 通过 Rust Tauri 实现&#xff0c;构建了一个类似 Wireshark 的跨平台数据包嗅探器。这个应用离生产阶段当然还很远&#xff0c;功能和页面上还有很多改善的空间&#xff0c;但是代码组织良好&#…

基于 Hive 的 Flutter 文档类型存储

基于 Hive 的 Flutter 文档类型存储 原文 https://medium.com/gytworkz/document-type-storage-in-flutter-using-hive-a18ea9659d84 前言 长久以来&#xff0c;我们一直使用共享首选项以键对格式在本地存储中存储数据&#xff0c;或者使用 SQLite 在 SQL 数据库中存储数据。 存…

【收藏】安科瑞企业微电网能效管理系统云平台演示账号

安科瑞 李亚俊 Acrel8757 1、AcrelCloud-1000变电所电力运维云平台 网址&#xff1a;https://acrelcloud.cn/ 演示账号&#xff1a;acrel 密码:123456 2、SCADA电力监控系统 网址&#xff1a;http://scada.acrel-eem.com/ 演示账号&#xff1a;acrel 密码:…

Android——使用ContentProvider共享数据

实验名称&#xff1a; 使用ContentProvider共享数据 实验目的&#xff1a; &#xff08;1&#xff09;能使用ContentProvider共享数据 &#xff08;2&#xff09;能使用内容观察者观察其他程序的数据变化 实验内容及原理&…

Kamiya丨Kamiya艾美捷小鼠血红蛋白ELISA说明书

Kamiya艾美捷小鼠血红蛋白ELISA预期用途&#xff1a; 小鼠血红蛋白ELISA是一种高灵敏度的双位点酶联免疫分析&#xff08;ELISA&#xff09;小鼠生物样品中血红蛋白的测定。仅供研究使用。 引言 血红蛋白&#xff08;HM&#xff09;是红细胞中的含铁氧转运蛋白。它吸收肺部的…

第10讲:Python列表对象查操作之通过切片获取列表中的元素

文章目录1.切片获取列表中的技术要点1.1切片获取列表中的概念总结1.2.切片的语法格式以及含义3.使用切片方法获取列表中元素3.1.定义一个原始列表列表3.2.当step步长为正数时切片的案例3.3.当step步长为负数时切片的案例3.4.使用负数索引作为切片范围4.将切片后的列表赋值给新的…

【LeetCode】No.103. Binary Tree Zigzag Level Order Traversal -- Java Version

题目链接&#xff1a;https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ 1. 题目介绍&#xff08;Binary Tree Zigzag Level Order Traversal&#xff09; Given the root of a binary tree, return the zigzag level order traversal of its nodes’…

【学习笔记67】JavaScript中的闭包

一、认识函数的过程 1. 定义 在堆内存中开辟一段内存空间(XF001)把函数体的内容&#xff0c;完全百分百的照抄一份&#xff0c;存放在内存空间中(XF001)把内存空间的地址(XF001) 赋值给函数名2. 调用 根据函数名内存储的地址 (XF001) &#xff0c;去堆内存中找到对应函数会去…

R语言法国足球联赛球员多重对应分析(MCA)

数据集 fooball球员在场上的位置 数据来自国际足联的视频游戏FIFA 。游戏的特点是在游戏的各个方面评价每个球员的能力。等级是量化变量&#xff08;介于0和100之间&#xff09;&#xff0c;但我们将它们转换为分类变量。所有能力都被编码在4个等级&#xff1a;1.低/ 2.平均/ …

基于单片机技术的自动停车器的设计

目 录 摘 要 I Abstract II 1绪论 1 1.1课题研究背景 1 1.2国内外发展现状 1 1.3汽车自动停车器的研究目的 2 1.4课题研究的意义 2 2汽车停车器的功能设计 3 2.1汽车自动停车器的设计要求 3 2.2停车器的主要功能 3 3汽车自动停车器的硬件设计 5 3.1汽车自动停车器的硬件组成 5 …

数据存储——存储视频

数据存储——存储视频视频的数字化一、视频采样二、视频量化总结&#xff1a;视频数字化的过程视频的数字化 1.视频是图像&#xff08;帧&#xff09;在时间上的表示 图象是离散的视频&#xff0c;视频是连续的图像 2.视频储存 每一帧图像或帧被转化为位模式并加以储存 一、视…

三年城市NOH落地100城,毫末智行内部信剑指2025

11月29日&#xff0c;毫末智行董事长张凯、CEO顾维灏联合发布《毫末智行三周岁&#xff1a;三年磨一剑 利刃开新篇》的内部信&#xff0c;提到毫末愿景及战略目标&#xff1a;“让机器智能移动&#xff0c;给生活更多美好。”未来成长为一家产品矩阵覆盖全无人驾驶、机器人等多…

【Android App】Vulkan实现宇宙中旋转雷达动画效果(附源码和原始视频 超详细必看)

需要源码请点赞关注收藏后评论区留言私信~~~ 一、Vulkan简介 Vulkan是一个跨平台的图形绘制接口&#xff0c;被称为下一代OpenGL&#xff0c;因为尽管OpenGL提供了丰富的图形API&#xff0c;但他在底层实现的C代码早已封装起来&#xff0c;由于开发者修改不了底层代码&#xf…

​GENIUS: 根据草稿进行文本生成的预训练模型,可用于多种NLP任务的数据增强...

©PaperWeekly 原创 作者 | 郭必扬 单位 | 上海财经大学信息管理与工程学院AI Lab论文标题&#xff1a;GENIUS: Sketch-based Language Model Pre-training via Extreme and Selective Masking for Text Generation and Augmentation论文作者&#xff1a;Biyang Guo, Yeyu…

多线程,了解-概念-实现方式-常见方法-安全问题-死锁-生产者消费者

了解 简单了解多线程 是指从软件或者硬件上实现多个线程并发执行的技术。 具有多线程能力的计算机因有硬件支持而能够在同一时间执行多个线程&#xff0c;提升性能。 简单了解多线程 简单了解多线程 简单了解多线程 简单了解多线程 概念 线程相关的概念 并行&#xff1a;在同…

【车载开发系列】UDS诊断---电控单元复位 ($0x11)

【车载开发系列】UDS诊断—电控单元复位&#xff08;$0x11&#xff09; UDS诊断---电控单元复位&#xff08;$0x11&#xff09;【车载开发系列】UDS诊断---电控单元复位&#xff08;$0x11&#xff09;一.概念定义二.应用场景三.报文格式1&#xff09;请求2&#xff09;肯定响应…

Spark 3.0 - 8.ML Pipeline 之决策树原理与实战

目录 一.引言 二.决策树基础-信息熵 三.决策树的算法基础 - ID3 算法 四.ML 中决策树的构建 1.信息增益计算 2.连续属性划分 五.ML 决策树实战 1.Libsvm 数据与加载 2.StringIndexer 3.VectorIndexer 4.构建决策树与 Pipeline 5.测试与评估 6.获取决策树 六.总结…

基于PHP+MySQL企业网络推广平台系统的设计与实现

企业网络推广平台系统具有很强的信息指导性特征,采用PHP开发企业网络推广平台系统 给web带来了全新的动态效果,具有更加灵活和方便的交互性。在Internet中实现数据检索越来越容易,可以及时、全面地收集、存储大量的企业资源信息以及进行发布、浏览、搜索相关的信息。让企业、个…

C++ Reference: Standard C++ Library reference: Containers: list: list: cend

C官网参考链接&#xff1a;https://cplusplus.com/reference/list/list/cend/ 公有成员函数 <list> std::list::cend const_iterator cend() const noexcept; 返回结束的常量迭代器 返回一个指向容器结束后元素的const_iterator。 const_iterator是指向const内容的迭代…