买卖股票的各种最佳时机问题

买卖股票的最佳时机

分析

根据题意可知，我们只需要找出来一个最小价格的股票和一个最大价格的股票，并且最小价格的股票出现在最大价格的股票之前。

如果尝试使用暴力解法，时间复杂度为O(N^2)，对于题目中给的长度，显然是会超时的，因此我们需要另寻它法。

我们可以使用一次遍历，在经过每个值时，计算出包含该值之前的股票的最低价格和最大利润，该种方法的时间复杂度为O(N)，显然是可解的。

初始化：由于在确定价格最小值时涉及到min求最小值，而且根据题目所给价格的范围，我们可以使用 0x3f3f3f3f 来初始化minprice；根据题意，由于利润最小为0，不涉及到为负的情况，因此初始化 profit 为0即可。

填表顺序：从左到右。

返回值：profit

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int profit=0,minprice=0x3f3f3f3f;
        for(int price:prices){
            profit=max(profit,price-minprice);
            minprice=min(price,minprice);
        }
        return profit;
    }
};
买卖芯片的最佳时机

分析

根据题意，只需找到一个最低价格和一个最高价格，并且最低价格出现在最高价格之前，显然与上面的题意是一样的，解法显而易见也是一样的。

代码

class Solution {
public:
    int bestTiming(vector<int>& prices) {
        int n=prices.size();
        int profit=0,minprice=0x3f3f3f3f;
        for(int price:prices){
            profit=max(profit,price-minprice);
            minprice=min(price,minprice);
        }
        return profit;
    }
};
买卖股票的最佳时机II

分析

如果以以往经验，对于本题，我们可以定义一个 dp 表，dp[i] 表示以 i 位置为结尾，能获取的最大利润，即：

由于题目中涉及到该天“买股票”和“卖股票”的问题，因此，仅仅使用一维 dp 是不能解决问题的，因此可以尝试使用二维 dp 来解决，dp[i][0] 表示手里没股票的时候能获取的最大利润，dp[i][1]表示手里有股票的时候能获取的最大利润（易知这里说的有股票指的是“一张股票”）。

状态转移方程：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])

                         dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])

初始化：由于只会用到前一行的值，因此只需初始化第一行的值即可，dp[0][0]表示第1天手里没股票的最大利润，为0；dp[0][1]表示第一天手里有股票的最大利润，为 -prices[0]。

填表顺序：从上到下。

返回值：dp[n-1][0]，因为最后一天手里有股票肯定是比最后一天没股票要亏。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2));
        dp[0][1]=-prices[0];
        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
};
买卖股票的最佳时机含手续费

分析

 如果以以往经验，对于本题，我们可以定义一个 dp 表，dp[i] 表示以 i 位置为结尾，能获取的最大利润，即：

由于题目涉及到该天“买股票”和“卖股票”这两种情况，显然只表示该天为结尾能获取的最大利润，是非常模糊的，那么问题也得不到解决。

因此考虑使用二维 dp 来解决问题，dp[i][0]表示第 i 天手里没股票的时候能获取的最大利润；dp[i][1]表示第 i 天手里有股票的时候能获取的最大利润（显然，根据题意，这里所说的有股票指的是“一张股票”）。

状态转移方程：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);

                         dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);

初始化：由于只会用到前一行的值，因此只需初始化第一行的值即可，dp[0][0]表示第1天手里没股票的最大利润，为0；dp[0][1]表示第一天手里有股票的最大利润，为 -prices[0]。

填表顺序：从上到下。

返回值：dp[n-1][0]，因为最后一天手里有股票肯定是比最后一天没股票要亏。

解法一

代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2));
        //dp[i][0] 表示没股票的最大利润
        //dp[i][1] 表示有股票的最大利润
        dp[0][1]=-prices[0];
        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
};
解法二

根据解法一的状态转移方程可知，每一次填写只会用到前一行的两个值，因此我们可以只定义几个变量来解决问题。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        int a=0,b=-prices[0];
        //a 表示没股票的最大利润
        //b 表示有股票的最大利润
        for(int i=1;i<n;i++){
            int a1=max(a,b+prices[i]-fee);
            int b1=max(b,a-prices[i]);
            a=a1,b=b1;
        }
        return a;
    }
};
解法三（贪心）

仔细分析前两种解法，不难发现，都是在卖出股票的时候进行决策优劣的，我们不妨尝试在买入股票的时候进行优劣的决策。

定义buy表示买入价格（含手续费），当某天价格+手续费 < buy 的时候，表示我们可以用更低成本卖股票，则更新 buy=prices[i]+fee。

定义profit表示能获取的最大利润，当prices[i] > buy的时候，我们会卖出股票，但是这里需要注意的是，如果我们这个时候卖出股票，可能不是最优的，因为可能之后的价格更高，即一张股票可以赚更高的利润，因此我们可以尝试以下策略：先卖掉，并把 buy 更新为 prices[i]，那么在之后遇到更高价格之后，只需加上差价即可，即：我们是提供了一种“可以反悔”的操作。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        int buy=prices[0]+fee;
        int profit=0;
        for(int i=1;i<n;i++){
            if(prices[i]+fee < buy)
                buy=prices[i]+fee;
            else if(prices[i] > buy){
                profit+=prices[i]-buy;
                buy=prices[i];
            }
        }
        return profit;
    }
};
买卖股票的最佳时期含冷冻期

分析

  如果以以往经验，对于本题，我们可以定义一个 dp 表，dp[i] 表示以 i 位置为结尾，能获取的最大利润，即：

由于题目涉及到该天“买股票”，“卖股票”和“冷冻期”这三种情况，显然只表示该天为结尾能获取的最大利润，是非常模糊的，那么问题也得不到解决。

因此考虑使用二维 dp 来解决问题，dp[i][0]表示第 i 天手里有股票的时候能获取的最大利润（显然，根据题意，这里所说的有股票指的是“一张股票”）；dp[i][1]表示手里没股票，当天处于冷冻期的最大利润；dp[i][2]表示手里没股票，当天不处于冷冻期的时候所能获取的最大利润。

状态转移方程：dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);

                         dp[i][1]=dp[i-1][0]+prices[i];

                         dp[i][2]=max(dp[i-1][1],dp[i-1][2]);

初始化：根据状态转移方程可知，每次填值只会用到上一行的值，因此只需初始化第一行即可，

              dp[0][0]= -prices[0]，dp[0][1]=0，dp[0][2]=0。

填表顺序：从上到下。

返回值：max(dp[n-1][1],dp[n-1][2]).因为最后一天手里有股票肯定是比最后一天手里没股票要亏的.

解法一

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(3));
        dp[0][0]=-prices[0];
        //dp[i][0] 手里有股票的最大利润
        //dp[i][1] 手里没股票，处于冷冻期的最大利润
        //dp[i][2] 手里没股票，不处于冷冻期的最大利润
        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1]=dp[i-1][0]+prices[i];
            dp[i][2]=max(dp[i-1][1],dp[i-1][2]);
        }
        return max(dp[n-1][1],dp[n-1][2]);
    }
};
解法二

根据解法一可知，每次填值只会用到上一行的三个值，因此可以尝试用几个变量来解决，时间复杂度为O(N)。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int a=-prices[0],b=0,c=0;
        //a 手里有股票的最大利润
        //b 手里没股票，处于冷冻期的最大利润
        //c 手里没股票，不处于冷冻期的最大利润
        for(int i=1;i<n;i++){
            int a1=max(a,c-prices[i]);
            int b1=a+prices[i];
            int c1=max(b,c);
            a=a1,b=b1,c=c1;
        }
        return max(b,c);
    }
};
买卖股票的最佳时机III

分析

   如果以以往经验，对于本题，我们可以定义一个 dp 表，dp[i] 表示以 i 位置为结尾，能获取的最大利润，即：

由于该题涉及“买股票”，“卖股票”和“交易次数”的问题，显然使用一维dp是不能解决问题的。

我们可以使用三维 dp 来解决，dp[i][j][k]，i 表示第 i 天，j 表示处于手里有股票还是没股票，k 表示已交易次数，这样看来，三维的有点头疼。

我们不妨可以使用两个二维dp来解决，f[i][j]表示手里没股票，已交易 j 次能获取的最大利润，g[i][j]表示手里有股票，已交易 j 次能获取的最大利润。

状态转移方程：f[i][j]=max(f[i-1][[j]，g[i-1][j-1]+prices[i])【注意：使用g[i-1][j-1]须满足 j >=1】

                         g[i][j]=max(g[i-1][j]，f[i-1][j]-prices[i]).

初始化：对于f[i][j]来说，会用到上一行的值，因此只需初始化第一行即可，由于第一行表示第一天，因此最多交易0次，对于高于0次的情况并不可能出现，初始化为 -0x3f3f3f3f.

              对于g[i][j]来说，会用到上一行的值，也可能用到前一行前一列的值（左上方）【因此不需要初始化】

填表顺序：从上到下，从左到右。

返回值：f[i][j]里面的最大值。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> f(n,vector<int>(3,-0x3f3f3f3f));
        vector<vector<int>> g(n,vector<int>(3,-0x3f3f3f3f));
        //f[i][j] 表示没股票的时候，已经交易j次，获取的最大利润
        //g[i][j] 表示有股票的时候，已经交易j次，获取的最大利润
        f[0][0]=0,g[0][0]=-prices[0];
        for(int i=1;i<n;i++){
            for(int j=0;j<=2;j++){
                f[i][j]=f[i-1][j];
                if(j>=1)
                    f[i][j]=max(f[i][j],g[i-1][j-1]+prices[i]);
                g[i][j]=max(g[i-1][j],f[i-1][j]-prices[i]);
            }
        }
        return *max_element(f[n-1].begin(),f[n-1].end());
    }
};
买卖股票的最佳时机IV

分析

这道题与上一道题相比，差异之处为：上一道题限制交易次数最多为两次，本题限制交易次数最多为k次，所以解法和代码同上一道题几乎    如出一辙。

   如果以以往经验，对于本题，我们可以定义一个 dp 表，dp[i] 表示以 i 位置为结尾，能获取的最大利润，即：

由于该题涉及“买股票”，“卖股票”和“交易次数”的问题，显然使用一维dp是不能解决问题的。

我们可以使用三维 dp 来解决，dp[i][j][k]，i 表示第 i 天，j 表示处于手里有股票还是没股票，k 表示已交易次数，这样看来，三维的有点头疼。

我们不妨可以使用两个二维dp来解决，f[i][j]表示手里没股票，已交易 j 次能获取的最大利润，g[i][j]表示手里有股票，已交易 j 次能获取的最大利润。

状态转移方程：f[i][j]=max(f[i-1][[j]，g[i-1][j-1]+prices[i])【注意：使用g[i-1][j-1]须满足 j >=1】

                         g[i][j]=max(g[i-1][j]，f[i-1][j]-prices[i]).

初始化：对于f[i][j]来说，会用到上一行的值，因此只需初始化第一行即可，由于第一行表示第一天，因此最多交易0次，对于高于0次的情况并不可能出现，初始化为 -0x3f3f3f3f.

              对于g[i][j]来说，会用到上一行的值，也可能用到前一行前一列的值（左上方）【因此不需要初始化】

填表顺序：从上到下，从左到右。

返回值：f[i][j]里面的最大值。

代码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> f(n,vector<int>(k+1,-0x3f3f3f3f));
        vector<vector<int>> g(n,vector<int>(k+1,-0x3f3f3f3f));
        //f[i][j] 表示没股票的时候，已经交易j次，获取的最大利润
        //g[i][j] 表示有股票的时候，已经交易j次，获取的最大利润
        f[0][0]=0,g[0][0]=-prices[0];
        for(int i=1;i<n;i++){
            for(int j=0;j<=k;j++){
                f[i][j]=f[i-1][j];
                if(j>=1)
                    f[i][j]=max(f[i][j],g[i-1][j-1]+prices[i]);
                g[i][j]=max(g[i-1][j],f[i-1][j]-prices[i]);
            }
        }
        return *max_element(f[n-1].begin(),f[n-1].end());
    }
};

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Go】编码结构体转换为json字符串

【Go】编码结构体转换为json字符串

结构体内字段命名大小写问题导致无法解析到 package mainimport ("encoding/json""fmt" ) // 定义一个结构体 type Music struct {name string json:"名称" // 字段大小写命名问题&#xff01;&#xff01;&#xff01;singer string json:&q…
阅读更多...
你会用Nginx的第三方模块吗？

你会用Nginx的第三方模块吗？

你好&#xff0c;我是赵兴晨&#xff0c;97年文科程序员。 你使用过Nginx的第三方模块吗&#xff1f;今天咱们来聊聊Nginx的第三方模块。 在深入了解Nginx的高性能与灵活性的过程中&#xff0c;我们不可避免地会接触到第三方模块。 这些模块是对Nginx原生功能的有力扩展&…
阅读更多...
学习笔记——IP地址网络协议——网络掩码(Netmask)

学习笔记——IP地址网络协议——网络掩码(Netmask)

三、网络掩码(Netmask) 1、网络掩码概述 网络掩码(Netmask)又称子网掩码(Subnet Mask)网络掩码为32 bit&#xff0c;与IP地址的位数一样&#xff0c;通常也以点分十进制数来表示。 子网掩码不能单独存在&#xff0c;它必须结合IP地址一起使用。子网掩码只有一个作用&#xf…
阅读更多...
北斗RTK+UWB定位的优势

北斗RTK+UWB定位的优势

在当今科技飞速发展的时代&#xff0c;定位技术的应用已渗透到我们生活的方方面面。从导航、物流到无人驾驶、智能制造&#xff0c;精准定位技术无处不在。而北斗RTK&#xff08;Real-Time Kinematic&#xff0c;实时动态&#xff09;和UWB&#xff08;Ultra-Wideband&#xff…
阅读更多...
JS 二进制文件处理与转换：Blob,FileReader,Base64,ArrayBuffer

JS 二进制文件处理与转换：Blob,FileReader,Base64,ArrayBuffer

转载&#xff1a;https://www.cnblogs.com/yinpengfei/p/17280585.html
阅读更多...
【CentOS 7】CentOS 7极致指南：高级部署PyCharm 2022.3.3专业版，实现定制化配置与无缝桌面集成

【CentOS 7】CentOS 7极致指南：高级部署PyCharm 2022.3.3专业版，实现定制化配置与无缝桌面集成

【CentOS 7】CentOS 7极致指南&#xff1a;高级部署PyCharm 2022.3.3专业版&#xff0c;实现定制化配置与无缝桌面集成 大家好 我是寸铁&#x1f44a; 总结了一篇CentOS 7极致指南&#xff1a;高级部署PyCharm 2022.3.3专业版&#xff0c;实现定制化配置与无缝桌面集成✨ 喜欢的…
阅读更多...
RN解析富文本内容的插件

RN解析富文本内容的插件

安装插件 yarn add react-native-render-html使用 import HTML from react-native-render-html; import {View} from react-native; export default function () {return (<View style{{flex: 1}}><HTMLsource{{html: <p>功能介绍1</p><p>功能介绍…
阅读更多...
基于STC89C52单片机空气PM2.5系统设计资料

基于STC89C52单片机空气PM2.5系统设计资料

#include <reg52.h>#include <intrins.h>#define uint unsigned int#define uchar unsigned char //宏定义sbit RSP1^6;//液晶接口sbit ENP1^7;sbit LED P2^0;//粉尘传感器控制接口sbit ADCS P3^7;//AD0832接口sbit ADCLK P3^5;sbit ADDI P3^6;sbit ADDO P3^6;…
阅读更多...
Cesium项目报错An error occurred while rendering. Rendering has stopped.

Cesium项目报错An error occurred while rendering. Rendering has stopped.

一般就是本地打开会报错&#xff0c;改成用本地服务器打开 全局安装一个live-server sudo cnpm i live-server -g然后新增一个package.json文件 npm init -y然后在package.json的scripts中增加一个命令 "server": "live-server ./ --port8181 --hostlocalhos…
阅读更多...
一文了解如何安全有效的进行PB级别的大数据迁移

一文了解如何安全有效的进行PB级别的大数据迁移

在这个信息量爆炸的时代&#xff0c;处理PB级别的数据转移已成为常态&#xff0c;但对企业而言&#xff0c;这仍然是一个充满挑战的任务。今天&#xff0c;我们来探讨一下这个话题&#xff0c;看看在进行PB级数据转移时&#xff0c;需要留意哪些事项&#xff0c;可能会遇到哪些…
阅读更多...
【多模态】35、TinyLLaVA | 3.1B 的 LMM 模型就可以实现 7B LMM 模型的效果

【多模态】35、TinyLLaVA | 3.1B 的 LMM 模型就可以实现 7B LMM 模型的效果

文章目录 一、背景二、方法2.1 模型结构2.2 训练 pipeline 三、模型设置3.1 模型结构3.2 训练数据3.3 训练策略3.4 评测 benchmark 四、效果 论文&#xff1a;TinyLLaVA: A Framework of Small-scale Large Multimodal Models 代码&#xff1a;https://github.com/TinyLLaVA/T…
阅读更多...
11. MySQL 备份、恢复

11. MySQL 备份、恢复

文章目录 【 1. MySQL 备份类型 】【 2. 备份数据库 mysqldump 】2.1 备份单个数据表2.2 备份多个数据库2.3 备份所有数据库2.4 备份文件解析 【 3. 恢复数据库 mysql 】【 4. 导出表数据 OUTFILE 】【 5. 恢复表数据 INFILE 】 问题背景 尽管采取了一些管理措施来保证数据库的…
阅读更多...
文件传输新体验，这些中转站工具让你的职场生活更轻松

文件传输新体验，这些中转站工具让你的职场生活更轻松

不知道大家有没有体验过华为手机的中转站功能&#xff0c;可以一键抓取图片或文件&#xff0c;暂时放在中转站中然后可以再拖到指定文件夹中。 华为手机的中转站功能&#xff0c;以其独特的跨应用文件传输能力&#xff0c;为用户带来了极大的便利。无论是图片、视频还是文档&am…
阅读更多...
NineData云原生智能数据管理平台新功能发布｜2024年5月版

NineData云原生智能数据管理平台新功能发布｜2024年5月版

重点发布​ 数据库 DevOps - 表分组查询​ 在企业用户规模达到一定程度后&#xff0c;分库分表成为一种常见的数据库架构选择。在这种情况下&#xff0c;查询和维护数据需要高效的解决方案&#xff0c;以避免手动逐一查询、变更和汇总多个分库和分表的繁琐操作。 库分组变更…
阅读更多...
亚马逊测评自养号需要什么资源？

亚马逊测评自养号需要什么资源？

亚马逊测评自养号项目需要用到哪些资源呢&#xff1f; 1. 养号系统及软件 2. 代理IP资源 3. 收货地址及注册资料 4. 国外信用卡及礼品卡 5. 邮箱及手机号想做好这个项目以上的资源缺一不可 首先我们来说说养号的环境&#xff0c;养号的环境在以前的文章里也提到过&#x…
阅读更多...
快速排序——AcWing785.快速排序

快速排序——AcWing785.快速排序

AcWing785.快速排序 题目描述 785. 快速排序 - AcWing题库 运行代码 #include <iostream> #include <algorithm> using namespace std; const int N 1e66; int q[N]; void quick_sort(int q[], int l, int r) {if (l > r) return;int m l r >> 1;//…
阅读更多...
Linux网络编程：回顾网络通信

Linux网络编程：回顾网络通信

1.数据从应用层到数据链路层的本质 数据的封装&#xff1a; 用户在用户级缓冲区输入数据&#xff0c;经过应用层协议进行序列化成字节流数据&#xff0c;拷贝到传输层的缓冲区。而操作系统在传输层维护了sk_buff这一个结构体&#xff0c;然后data指针指向这段数据的开头&#x…
阅读更多...
用Conda配置Pytorch环境 (pytorch==2.2.1)

用Conda配置Pytorch环境 (pytorch==2.2.1)

用Conda配置Pytorch环境 (pytorch==2.2.1) 本文主要讲解: 如何用Conda搭建Pytorch环境，用Conda的方式安装，不需要单独去安装Cuda了。 1. 安装miniconda https://docs.anaconda.com/free/miniconda/index.html 2. 搭建虚拟环境 激活python虚拟环境 conda create -n env…
阅读更多...
618哪些品牌好入手？四款主流数码产品，必看！

618哪些品牌好入手？四款主流数码产品，必看！

随着618购物狂欢节的钟声逐渐敲响&#xff0c;你是否在面对繁多的商品时感到一丝迷茫&#xff0c;想要找到那些既引领潮流又极具实用价值的商品&#xff1f;团团精心为你准备了一份个人实测后的好物推荐清单。这些商品不仅紧跟时尚潮流&#xff0c;更是你生活中的得力助手&…
阅读更多...
全域外卖推广怎么做才能赚钱？

全域外卖推广怎么做才能赚钱？

当前&#xff0c;全域外卖行业的热度持续飙升&#xff0c;许多创业者在了解完全域外卖项目的基本信息之后&#xff0c;便开始将目光转向与全域外卖推广相关的各项事宜之中&#xff0c;誓要将全域外卖行业彻底摸清后再行入局。 从理论层面上来说&#xff0c;这种思路并没有任何问…
阅读更多...
最新文章

Copyright @ 2022~2023