临安网站建设公司,获取免费域名,昆明市城建设档案馆网站,wordpress建站要多久力扣labuladong一刷day10股票买卖问题共6题
一、121. 买卖股票的最佳时机
题目链接#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 思路#xff1a;只能买入1次#xff0c;定义dp[i][0]数组表示第i天持有股票时手中的最大金额 数#xff0c;…力扣labuladong一刷day10股票买卖问题共6题
一、121. 买卖股票的最佳时机
题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 思路只能买入1次定义dp[i][0]数组表示第i天持有股票时手中的最大金额 数定义dp[i][1]表示第1天手中不持有股票时手中金额最大值。 这里的持有表示为一种状态可以是之前就持有的也可以是今天才持有的。
class Solution {public int maxProfit(int[] prices) {int[][] dp new int[prices.length][2];dp[0][0] -prices[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], dp[i-1][0]prices[i]);}return dp[prices.length-1][1];}
}class Solution {public int maxProfit(int[] prices) {int len prices.length;int[] dp new int[2];dp[0] -prices[0];for (int i 1; i prices.length; i) {dp[0] Math.max(dp[0], -prices[i]);dp[1] Math.max(dp[1], dp[0]prices[i]);}return dp[1];}
}二、122. 买卖股票的最佳时机 II
题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ 思路上一题类似只不过是可以进行无数次交易本题还可以优化及dp[2]。
class Solution {public int maxProfit(int[] prices) {int len prices.length;int[][] dp new int[len][2];dp[0][0] -prices[0];for (int i 1; i len; i) {dp[i][0] Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);dp[i][1] Math.max(dp[i-1][1], dp[i-1][0]prices[i]);}return dp[len-1][1];}
}class Solution {public int maxProfit(int[] prices) {int len prices.length;int[] dp new int[2];dp[0] -prices[0];for (int i 1; 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];}
}三、123. 买卖股票的最佳时机 III
题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/ 思路和上一题的区别是最多只能进行两次交易dp[0]和dp[1]表示第一次交易的持有和不持有状态dp[2]和dp[3]表示第二次交易的持有和不持有状态。
class Solution {public int maxProfit(int[] prices) {int len prices.length;int[] dp new int[4];dp[0] -prices[0];dp[2] -prices[0];for (int i 1; i len; i) {dp[0] Math.max(dp[0], -prices[i]);dp[1] Math.max(dp[1], dp[0]prices[i]);dp[2] Math.max(dp[2], dp[1]-prices[i]);dp[3] Math.max(dp[3], dp[2]prices[i]);}return dp[3];}
}四、188. 买卖股票的最佳时机 IV
题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/ 思路本题与上一题不同之处在与拓展了一下设置最多可以购买k次前面是购买两次我们还可以展开写成dp[0]、dp[1]、dp[2]、dp[3]两天就写了4行要是k天我们无法穷举都写出来需要借助for循环来进行缩写。其他的没有什么唯一要注意的就是交易次数。 dp[i][j1] Math.max(dp[i-1][j1], dp[i-1][j]-prices[i]); 这个是计算持有如果之前就已经完成了该次交易买入交易数就是本身如果之前没进行是今天才进行该次的买入那依赖的便是上一次交易的卖出交易数自然减一。 卖出同样同理。
class Solution {public int maxProfit(int k, int[] prices) {int len prices.length, m 2*k1;int[][] dp new int[len][m];for (int i 1; i m; i2) {dp[0][i] -prices[0];}for (int i 1; i len; i) {for (int j 0; j m-2; j2) {dp[i][j1] Math.max(dp[i-1][j1], dp[i-1][j]-prices[i]);dp[i][j2] Math.max(dp[i-1][j2], dp[i-1][j1]prices[i]);}}return dp[len-1][m-1];}
}五、309. 买卖股票的最佳时机含冷冻期
题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 思路含有冷静期的初始化时要注意冷静期为1天那么第二天要计算持有要么是第一天就持有了要么是第二天才持有第二天才持有第一天就是冷静期所以是0-prices[i]。那么如果是冷静期为k天也可以按照这个思路来处理。 剩下的如果要计算持有都是依赖于2天前的因为中间有一天冷静期。
class Solution {public int maxProfit(int[] prices) {int len prices.length;int[][] dp new int[len][2];for (int i 0; i len; i) {if (i 0) {dp[i][0] -prices[0];continue;}if (i 1) {dp[i][0] Math.max(dp[i-1][0], -prices[i]);dp[i][1] Math.max(dp[i-1][1], dp[i-1][0]prices[i]);continue;}dp[i][0] Math.max(dp[i-1][0], dp[i-2][1]-prices[i]);dp[i][1] Math.max(dp[i-1][1], dp[i-1][0]prices[i]);}return dp[len-1][1];}
}六、714. 买卖股票的最佳时机含手续费
题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/ 思路含有续费的就是在卖出时减掉手续费即可。
class Solution {public int maxProfit(int[] prices, int fee) {int len prices.length;int[] dp new int[2];dp[0] -prices[0];for (int i 1; i len; i) {dp[0] Math.max(dp[0], dp[1]-prices[i]);dp[1] Math.max(dp[1], dp[0]prices[i]-fee);}return dp[1];}
}
