一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 818|回复: 5
收起左侧

[算法题] 买卖股票的这几道题很有意思

[复制链接] |试试Instant~ |关注本帖
FightForTomo 发表于 2017-11-1 05:20:22 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
本帖最后由 FightForTomo 于 2017-11-1 05:29 编辑

我理解的buy 和 sell是 状态函数,表示到当天为止,执行,买或者卖操作,累计的最大收益是多少。是我最喜欢的dp系列。

1. 1次交易
  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int buy = Integer.MIN_VALUE, sell = 0;
  4.         for (int i : prices) {
  5.             buy = Math.max(buy, - i);
  6.             sell = Math.max(sell, buy + i);
  7.         }
  8.         return sell;
  9.     }
  10. }
复制代码
2. 无限次交易
  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int sell = 0;
  4.         for (int i = 1; i < prices.length; i++) {
  5.             sell += Math.max(0, prices[i]-prices[i-1]);
  6.         }
  7.         return sell;
  8.     }
  9. }
复制代码
3. 2次交易
  1. public class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices == null || prices.length < 2) return 0;
  4.         int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
  5.         int sell1 = 0, sell2 = 0;
  6.         for(int i : prices){
  7.             buy1 = Math.max(buy1, -i);
  8.             sell1 = Math.max(sell1, buy1 + i);
  9.             buy2 = Math.max(buy2, sell1 - i);
  10.             sell2= Math.max(sell2, buy2 + i);
  11.         }
  12.         return sell2;
  13.     }
  14. }
复制代码
4. k次交易
  1. class Solution {
  2.     public int maxProfit(int k, int[] prices) {
  3.         int len = prices.length;
  4.         if (len < 2 || k == 0) return 0;
  5.         int[] buys = new int[k + 1];
  6.         int[] sells = new int[k + 1];
  7.         Arrays.fill(buys, Integer.MIN_VALUE);
  8.         for (int i : prices) {
  9.             for (int j = 1; j <=k; j++) {
  10.                 buys[j] = Math.max(buys[j], sells[j - 1] - i);
  11.                 sells[j] = Math.max(sells[j], buys[j] + i);
  12.             }
  13.         }
  14.         return sells[k];
  15.     }
  16. }
复制代码
5. 冷却时间
  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int len = prices.length;
  4.         int[] buys = new int[len];
  5.         int[] sells = new int[len];
  6.         buys[0] = -prices[0];
  7.         buys[1] = prices[0] > prices[1] ? - prices[1] : - prices[0];
  8.         sells[1] = prices[0] > prices[1] ? 0 : prices[1] - prices[0];
  9.         
  10.         for (int i = 2; i < len; i++) {
  11.             buys[i] = Math.max(buys[i - 1], sells[i - 2] - prices[i]);
  12.             sells[i] = Math.max(sells[i - 1] , buys[i - 1] + prices[i]);
  13.         }
  14.         return sells[len - 1];
  15.     }
  16. }
复制代码
6. 交易费
  1. class Solution {
  2.     public int maxProfit(int[] prices, int fee) {
  3.         int sell = 0, buy = Integer.MIN_VALUE;
  4.         for (int i : prices) {
  5.             buy = Math.max(buy, sell - i);
  6.             sell = Math.max(sell, buy + i - fee);
复制代码

评分

2

查看全部评分

119018682 发表于 2017-11-1 10:25:50 | 显示全部楼层
胖迪,k次交易那个可以优化.
k / 2 >= prices.length ? Stock 2 : 继续往下走;

可以把复杂度从O(kn)降到O(n)
回复 支持 1 反对 0

使用道具 举报

GardenAAA 发表于 2017-11-1 05:27:31 | 显示全部楼层
k次交易这个代码真心不错
回复 支持 反对

使用道具 举报

wdxh1 发表于 2017-11-1 05:43:20 | 显示全部楼层
我也最喜欢打炮了
回复 支持 反对

使用道具 举报

wukehan1234 发表于 2017-11-1 06:00:03 | 显示全部楼层
总结的很好,非常感谢!
回复 支持 反对

使用道具 举报

wasabimlgb 发表于 2017-11-2 23:23:12 | 显示全部楼层
哈哈哈哈胖迪好可爱
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-19 00:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表