|
因为最近笔试做了一道股票问题，之前其实做过，但是笔试的时候还是想了很久。所以决定来总结一下这类股票问题。
level 1
剑指offer 63.股票的最大利润
特点：只买卖一次，求最大利润。
思路：
遍历数组的每一位，找到下标为 i 的元素之前最小的元素。比较是当前卖出更高，还是不卖更高。
var maxProfit = function(prices) {
if(prices.length < 2) return 0;
let min = prices[0];
const dp = new Array(prices.length).fill(0);
for(let i = 1; i < prices.length; i++) {
min = Math.min(min, prices[i]);
dp[i] = Math.max(dp[i-1],prices[i]-min);
}
return dp[prices.length-1];
};
Level 2
122. 买卖股票的最佳时机 II
特点：可以多次购买
思路1:
采用贪心算法，只有当前元素的值小于 下标为 i + 1 的元素的值就加 利润。
var maxProfit = function(prices) {
let maxProfit = 0;
for(let i=0;i<prices.length-1;i++){
if(prices[i]<prices[i+1])
{
maxProfit += (prices[i+1]-prices[i]);
}
}
return maxProfit;
};
思路2：
利用动态规划
dp[i][0]：第i天持有股票所得最多现金。dp[i][1]：第i天不持有股票所得最多现金
遍历数组
dp[i][0] 表示第i天所持，那么只有两种可能：
- 第一种是昨天没有，今天才买入,dp[i-1][1] - prices[i]
- 第二种是昨天就买了，今天还持有。现在的利润就是dp[i-1][0]；
dp[i][1]表示第i天不持有，那么也有两种可能：
- 第一种是昨天也不持有。dp[i-1][1]
- 第二种是昨天持有，今天卖了 dp[i-1][0] + prices[i]
var maxProfit = function(prices) {
const len = prices.length;
if(len < 2) return 0;
const dp = new Array(len).fill(0).map(() => new Array(2).fill(0));
dp[0][0] = -prices[0];
for(let i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i-1][1] - prices[i],dp[i-1][0]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i]);
}
return dp[len-1][1];
};
Level 3
309. 最佳买卖股票时机含冷冻期
特点：可以多次买卖，但是卖出股票后，无法在第二天买入股票。有一天的冷冻期。
var maxProfit = function(prices) {
const len = prices.length;
if(len < 2) return 0;
const dp = new Array(len+1).fill(0).map(() => new Array(2).fill(0));
dp[0][0] = -prices[0];
dp[1][0] = -prices[0];
dp[1][1] = 0;
for(let i = 2; i <= len; i++) {
dp[i][0] = Math.max(dp[i-1][0],dp[i-2][1] - prices[i-1]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i-1]);
}
return dp[len][1];
};
也可以这样写：
因为有一个冷冻期，所以要考虑 i-2 天的状态。所以只有从i = 2开始循环。之前的状态需要单独初始化。
var maxProfit = function(prices) {
const len = prices.length;
if(len < 2) return 0;
const dp = new Array(len+1).fill(0).map(() => new Array(2).fill(0));
dp[0][0] = -prices[0];
dp[1][0] = Math.max(dp[0][0],-prices[1]);
dp[1][1] = Math.max(dp[0][0] + prices[1], dp[0][1]);
for(let i = 2; i < len; i++) {
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];
};
Level 4
714. 买卖股票的最佳时机含手续费
这个其实只是在当天卖出的时候需要减一个手续费。
var maxProfit = function(prices, fee) {
let dp = new Array(prices.length).fill(0).map( item => new Array(2).fill(0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(let i = 1; i < prices.length; 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]-fee);
}
return dp[prices.length-1][1];
};
|