代码随想录刷题|LeetCode 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II

简介: 代码随想录刷题|LeetCode 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II

121. 买卖股票的最佳时机

题目链接:力扣

思路

暴力解法

       暴力解答会超出时长

edeb09df506e467384876aae013f0ca8.png

贪心算法

       因为股票就买卖一次,贪心算法的想法是:取最左侧最小值,取最右侧的最大值,那么这个差值就是可以得到的最大利润


动态规划

       其实我们要做的是,就是两件事:

       在什么时候买入的时候最小

       在什么时候卖出的时候赚的最多


1、确定dp数组及其下标的含义


       dp[i][0] : 表示第 i 天持有股票所得最多现金的情况。一开始现金是0 ,如果买入就是负数

                     这里实际意义是: 保存买入的最小数

       dp[i][1]:表示第 i 天不持有股票所得最多现金

                     这里实际意义是:根据当前保存的最小买入数,保存当天卖出的话可获得的最大利润


2、确定递推公式


对于持有股票dp[i][0]:


如果在 i - 1 天就持有了股票,那就不能再买了,这种状态就是dp[i - 1][0]

如果要在 i 天买入,这种状态就是 -prices[i]

所以这个就是代表,怎么买入才能话最少的钱,所以应该选其中的最大值

因此 : dp[i][0] = Math.max( dp[i -1][0] , -prices[i] );

对于不持有股票dp[i][1]


如果在 i - 1天已经卖出股票了,那就保持之前的状态,就是dp[i-1][1]

如果前面没有卖出过,那就试试在 i 天卖出,这种状态就是:卖出的价格 - 前面买入的最小数,因此是:prices[ i ] - dp[i - 1][0]

所以这个就是代表,当天价格 - 之前获得的最小买入,保存的是获得的利润,所以应该选取其中的最大值,因此:dp[i][1] = Math.max(dp[i -1][1], prices[i] - dp[i- 1][0]);

3、初始化dp数组


       从递推公式可以看出,我们是需要对dp[0][0]和dp[0][1]进行初始化的


       dp[0][0] 表示如果在 第0天买入股票后,手中的现金为:dp[0][0] = 0 - prices[0] = -prices[0]

       dp[0][1] 表示如果在 第0天卖出股票后,手中的现金为:dp[0][1] = 0


4、遍历顺序


       显然,是从前向后遍历


买卖股票的最佳时机

贪心算法

class Solution {
    public int maxProfit(int[] prices) {
        // 最小值
        int left = Integer.MAX_VALUE;
        // 结果
        int result = 0;
        for (int i = 0; i < prices.length; i++) {
            left = Math.min(left,prices[i]);
            result = Math.max(result,prices[i]-left);
        }
        return result;
    }
}

动态规划

版本一:使用二维数组

class Solution {
    public int maxProfit(int[] prices) {
        // 创建dp数组
        int[][] dp = new int[prices.length][2];
        // 初始化dp[]数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        // 进行动态推算
        for (int i = 1; i < prices.length; 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[prices.length-1][1];
    }
}

版本二:使用二维滚动数组

class Solution {
    public int maxProfit(int[] prices) {
        // 创建dp数组
        int[][] dp = new int[2][2];
        // 初始化dp[]数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        // 进行动态推算
        for (int i = 1; i < prices.length; i++) {
            dp[i % 2][0] = Math.max(dp[(i-1) % 2][0],-prices[i]);  // 将最小买入位保存了下来
            dp[i % 2][1] = Math.max(dp[(i-1) % 2][1],prices[i] + dp[(i-1) % 2][0]);  // 不断获取什么时候卖出的之后最大
        }
        return dp[(prices.length-1) % 2][1];
    }
}

版本三:使用一维数组

class Solution {
    public int maxProfit(int[] prices) {
        // 创建dp数组
        int[] dp = new int[2];
        // dp[0]保存最小买入数
        dp[0] = Integer.MAX_VALUE;
        // dp[i]保存当前卖出可获得的最大利润
        dp[1] = 0;
        for (int i = 0; i < prices.length; i++) {
            // 更新最小买入
            dp[0] = Math.min(dp[0],prices[i]);
            // 获取当前卖出可获取的利润
            dp[1] = Math.max(dp[1],prices[i]-dp[0]);
        }
        return dp[1];
    }
}

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

题目链接:力扣

思路


 这道题目在贪心算法的时候做过,再使用动态规划完成,与121题目的区别是可以买卖多次,买入前必须卖出


       和121除了递推公式,其他都是一样的


分析递推公式

dp数组的含义:


dp[i][0] 表示第 i 天持有股票所得现金,就是买入股票后手中的现金

dp[i][1] 表示第 i 天不持有股票所得的最多现金,就是卖出股票后手中的现金

其实这两个,代表的都是手中有的现金数

怎么推导dp[i][0]:


如果第 i-1 天持有股票,表示已经买入股票了,就不能再买入了,保持前面的状态就可以,也就是:dp[i - 1][0]

如果第 i-1 天没有持有股票,表示可以买入股票了,那么就买入,手中的现金就是,dp[i - 1][1] - prices[i]

怎么推导dp[i][1]:


如果第 i-1 天不持有股票了,那就不可以卖,那么就是保持现状,dp[i - 1][1]

如果第 i-1 天持有股票,那就可以卖了,dp[i - 1][0] + prices[i]


买卖股票的最佳时机II

贪心算法

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

动态规划

版本一:使用二维数组

class Solution {
    public int maxProfit(int[] prices) {
        // 创建的dp[]数组
        int[][] dp = new int[prices.length][2];
        // 初始化dp数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        // 推导dp数组
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]); // 这里与121的区别
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[prices.length - 1][1];
    }
}

版本二:使用滚动二维数组

class Solution {
    public int maxProfit(int[] prices) {
        // 创建的dp[]数组
        int[][] dp = new int[2][2];
        // 初始化dp数组
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        // 推导dp数组
        for (int i = 1; i < prices.length; i++) {
            dp[i % 2][0] = Math.max(dp[(i-1) % 2][0],dp[(i-1) % 2][1]-prices[i]);
            dp[i % 2][1] = Math.max(dp[(i-1) % 2][1],dp[(i-1) % 2][0]+prices[i]);
        }
        return dp[(prices.length - 1) % 2][1];
    }
}

版本三:使用一维数组

class Solution {
    public int maxProfit(int[] prices) {
        // 创建的dp[]数组
        int[] dp = new int[2];
        // 初始化dp数组
        dp[0] = Integer.MIN_VALUE; // 代表持有当前股票手中的现金
        dp[1] = 0;                 // 代表卖出卖出股票手中的现金
        // 推导dp数组
        for (int i = 0; i < prices.length; i++) {
            // 前一天是持有的情况
            dp[0] = Math.max(dp[0],dp[1] - prices[i]);
            dp[1] = Math.max(dp[1],dp[0] + prices[i]);
        }
        return dp[1];
    }
}
相关文章
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
25 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
4月前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
28 1
|
4月前
|
算法
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
65 0
|
4月前
|
Python
【Leetcode刷题Python】1467. 两个盒子中球的颜色数相同的概率
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
44 0
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
52 4
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2
|
4月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
65 7