Uber ATG Core Platform hiring
Uber ATG (self driving car)
core platforms multiple (lots!) openings

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业诚聘
机器学习/数据统计/教育等职位
码农求职神器Triplebyte:
不用海投
内推多家公司面试
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
锦晖律师事务所
12月16日
H1B讲座通知
查看: 1458|回复: 5
收起左侧

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

[复制链接] |试试Instant~
我的人缘0
FightForTomo 发表于 2017-11-1 05:20:22 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  52% (772)
 
 
47% (697)  踩

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

您需要 登录 才可以下载或查看,没有帐号?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);
复制代码

评分

参与人数 3大米 +22 收起 理由
Haibara_CC + 2 给你点个赞!
ARUI35 + 10 给你点个赞!
GardenAAA + 10 给你点个赞!

查看全部评分


上一篇:关于Subsets中deep copy的问题
下一篇:刷题记录+思路分析贴
我的人缘0
119018682 发表于 2017-11-1 10:25:50 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  92% (12)
 
 
7% (1)  踩
胖迪,k次交易那个可以优化.
k / 2 >= prices.length ? Stock 2 : 继续往下走;

可以把复杂度从O(kn)降到O(n)
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
GardenAAA 发表于 2017-11-1 05:27:31 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (493)
 
 
6% (37)  踩
k次交易这个代码真心不错
回复

使用道具 举报

我的人缘0
wdxh1 发表于 2017-11-1 05:43:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (279)
 
 
8% (27)  踩
我也最喜欢打炮了
回复

使用道具 举报

我的人缘0
wukehan1234 发表于 2017-11-1 06:00:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (12)
 
 
14% (2)  踩
总结的很好,非常感谢!
回复

使用道具 举报

我的人缘0
wasabimlgb 发表于 2017-11-2 23:23:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (139)
 
 
13% (21)  踩
哈哈哈哈胖迪好可爱
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地留学网

GMT+8, 2018-12-13 02:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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