谈谈使用过的几款咖啡机

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1069|回复: 5
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
FightForTomo 发表于 2017-11-1 05:20:22 | 显示全部楼层 |阅读模式
  此人我要顶:
 
53% (7) 【我投】
  此人我要踩:
 
47% (8) 【我投】

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

您需要 登录 才可以下载或查看,没有帐号?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 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
胖迪,k次交易那个可以优化.
k / 2 >= prices.length ? Stock 2 : 继续往下走;

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

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
GardenAAA 发表于 2017-11-1 05:27:31 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
k次交易这个代码真心不错
回复 支持 反对

使用道具 举报

我的人缘0
wdxh1 发表于 2017-11-1 05:43:20 | 显示全部楼层
  此人我要顶:
 
37% (3) 【我投】
  此人我要踩:
 
63% (5) 【我投】
我也最喜欢打炮了
回复 支持 反对

使用道具 举报

我的人缘0
wukehan1234 发表于 2017-11-1 06:00:03 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
总结的很好,非常感谢!
回复 支持 反对

使用道具 举报

我的人缘0
wasabimlgb 发表于 2017-11-2 23:23:12 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
哈哈哈哈胖迪好可爱
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-23 05:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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