一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 934|回复: 16
收起左侧

求大神们给Stock带有fee的解题思路

[复制链接] |试试Instant~ |关注本帖
LosivE 发表于 2015-10-16 00:02:19 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Facebook - Other - 其他 |Otherfresh grad应届毕业生

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

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

x
目前看面经,会遇到buy and sell stock那道LC原题,但是每次follow up都会有加入交易费用的要求,请问各位大神们有没有一个比较好的思路?谢谢!.鐣欏璁哄潧-涓浜-涓夊垎鍦
cgpzmxcc 发表于 2015-10-16 00:46:20 | 显示全部楼层
写了一个,不确定是否能cover所有情况,请大家帮忙看看
  1. class Solution {
  2.   
  3.   public int getProfit(int[] prices, int fee) {
  4.     if (prices == null || prices.length == 0) return 0;
  5.     int afterBuy = -prices[0];
  6.     int afterSell = 0;. 鍥磋鎴戜滑@1point 3 acres
  7.     for (int i = 1; i < prices.length; i++) {. 鍥磋鎴戜滑@1point 3 acres
  8.       int oldBuy = afterBuy;
  9.       int oldSell = afterSell;
  10.       afterBuy = Math.max(oldBuy, oldSell - prices[i]);-google 1point3acres
  11.       afterSell = Math.max(oldSell, oldBuy + prices[i] - fee);
  12.     }
  13.     return afterSell;
  14.   }
  15.   . 1point 3acres 璁哄潧
  16.   public static void main(String[] args) {
  17.     Solution s = new Solution();. From 1point 3acres bbs
  18.     System.out.println(s.getProfit(new int[]{1, 5, 4, 8, 3}, 3)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19.   }
  20. }
复制代码
回复 支持 1 反对 0

使用道具 举报

majiamajia 发表于 2015-10-16 01:10:26 | 显示全部楼层
buy stock i 还是 II啊?
回复 支持 反对

使用道具 举报

 楼主| LosivE 发表于 2015-10-16 02:21:03 | 显示全部楼层
majiamajia 发表于 2015-10-16 01:10
buy stock i 还是 II啊?
.1point3acres缃
应该是II,不限制交易次数,但是每次卖出就会有一个定额的费用。
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-16 02:24:42 | 显示全部楼层
还是可以根据IV,给出有gap,有fee的万能解法吧?转移方程改一改就是了
回复 支持 反对

使用道具 举报

 楼主| LosivE 发表于 2015-10-16 03:10:03 | 显示全部楼层
坐看云起 发表于 2015-10-16 02:24
还是可以根据IV,给出有gap,有fee的万能解法吧?转移方程改一改就是了

IV里不是定下了最多交易次数么,那这里就直接把它设成总共的天数么?
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-16 03:30:32 | 显示全部楼层
LosivE 发表于 2015-10-16 03:10
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷IV里不是定下了最多交易次数么,那这里就直接把它设成总共的天数么?

对的,IV可以引伸出很多万能解法:天数上限,再次购买间隔,还有交易费用
回复 支持 反对

使用道具 举报

mileschen2008 发表于 2015-10-16 12:49:27 | 显示全部楼层
坐看云起 发表于 2015-10-16 03:30
对的,IV可以引伸出很多万能解法:天数上限,再次购买间隔,还有交易费用

能不能说说思路?感觉不好弄啊,这种general的情况
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-17 01:06:14 | 显示全部楼层
mileschen2008 发表于 2015-10-16 12:49
能不能说说思路?感觉不好弄啊,这种general的情况

转移方程:
    unhold[j] = Math.max(unhold[j-1], hold - prices[j] - fee); //买卖i次,第j天卖出. 1point3acres.com/bbs
    res = Math.max(res, unhold[j]);  //最高收益
    hold = Math.max(hold, (j - gap - 1 >= 0 ? unhold[i-1][j-gap-1] : 0) - prices[j]);  //第j天持有股票

    //fee是交易费用,gap是交易间隔
    //IV就是把fee和gap设置为0的情况
回复 支持 反对

使用道具 举报

getway32 发表于 2015-10-17 08:28:43 | 显示全部楼层
坐看云起 发表于 2015-10-17 01:06. 鍥磋鎴戜滑@1point 3 acres
转移方程:
    unhold[j] = Math.max(unhold[j-1], hold - prices[j] - fee); //买卖i次,第j天卖出-google 1point3acres
  ...

这个方法来算有fee的情况没有问题,但是算gap天数的时候会出错。
因为unhold是指最多交易i次,不是exactly i次,所以直接在unhold[i-gap]比会出现问题
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-10-17 12:42:41 | 显示全部楼层
getway32 发表于 2015-10-17 08:28
这个方法来算有fee的情况没有问题,但是算gap天数的时候会出错。
因为unhold是指最多交易i次,不是exact ...

hold = Math.max(hold, (j - gap - 1 >= 0 ? unhold[i-1][j-gap-1] : 0) - prices[j]); . from: 1point3acres.com/bbs
这一行的意思可以理解为,第J天,最多经过i-1次完整交易后,持有股票,获利最大值
unhold[j]表示的是,第j天,最多进行i次交易的获利情况,不是必须完成i次交易
回复 支持 反对

使用道具 举报

getway32 发表于 2015-10-18 09:42:23 | 显示全部楼层
坐看云起 发表于 2015-10-17 12:42
hold = Math.max(hold, (j - gap - 1 >= 0 ? unhold[j-gap-1] : 0) - prices[j]);
这一行的意思可以理 ...
. visit 1point3acres.com for more.
我在ide里面试过了,,加gap的时候有的情况貌似不行,但是加fee是没问题的。不知为何
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-10-20 04:31:58 | 显示全部楼层
  1. int maxProfix(vector<int> &prices, int transactionFee) {
  2. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.     int minP = prices[0], maxP = 0;
  4.     int result = 0;
  5.     for(int i = 1; i < prices.size(); ++i) {
  6.         if(prices[i] > maxP) {
  7.             maxP = prices[i];
  8.         } else if(prices[i] < maxP) {
  9.             if(maxP - prices[i] > transactionFee) {
  10.                 if(maxP - minP > transactionFee) {
  11.                     result += maxP - minP - transactionFee;
  12.                     minP = prices[i];
  13.                     maxP = prices[i];
  14.                 }
  15.             } else {
  16.                 if(prices[i] < minP) {
  17.                     minP = prices[i];
  18.                     maxP = prices[i];
  19.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.             }
  21.         }. 1point3acres.com/bbs
  22.     }
  23.     if(maxP - minP > transactionFee) result += maxP - minP - transactionFee;

  24.     return result;
  25. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


  26. int main(char **argv, int argc)
  27. {. Waral 鍗氬鏈夋洿澶氭枃绔,

  28.     vector<int> nums1 = {1, 4, 3, 5, 7, 10, 6, 5, 4, 8, 9, 12, 11, 10, 9, 5};. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.     vector<int> nums2 = {1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 3, 4, 6, 7};
  30.     int result = maxProfix(nums1, 3);
  31.     cout << result << endl;

  32.     return 0;
  33. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| LosivE 发表于 2015-10-20 11:41:05 | 显示全部楼层

谢谢你的代码,能不能稍微解释下为何这样就一定是最大的?
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-10-21 01:28:22 | 显示全部楼层
LosivE 发表于 2015-10-20 11:41
谢谢你的代码,能不能稍微解释下为何这样就一定是最大的?

我没有刻意往DP上面想general的答案。这代码也就适用于不限交易次数的情况下。.鐣欏璁哄潧-涓浜-涓夊垎鍦

逻辑的核心就在于,
1.如果是递增,就一直更新max价格,最后一次交易max-min就得出结论
2.如果遇到递减的情况,也就是遇到比之前max小的情况,要继续判断。
   2.1 如果当天价格比max - 手续费还要小,那之前的部分就有可能进行一次交易了,之前的max - min - 手续费如果大于0,说明你赚了,可以交易。小于0的话则不交易,但是需要放弃掉前面的部分,更新min与max。
   2.2 如果当天价格比max - 手续费要大,那说明,前面的部分如果交易掉,也不会赚,所以就不要交易,继续往下面走。

最好举举例子,假设手续费是3:
1, 4, 5, 6, 8 ,递增,所以min不变,一直更新max最后 8 - 1 - 3 = 4就是profit

1 5 1 8 第三个1递减而且比5 - 3还要小,说明之前的部分可以结算,之前的结算价格是5-1-3=1, 后面的部分是8-1-3=4,profit是5
-google 1point3acres
1 5 4 8 第三个4也是递减,但是因为4比5-2=2,要大,所以先不急着结算,遇到8再一次性结算,profit = 8-1-3=4-google 1point3acres

1 5 4 3 2 最后因为没有更新max,所以直接用之前的max min进行一次交易 profit = 5 - 1 - 3 = 1

1 5 2 8 , 第三个2刚好等于5-3=2, 所以前面的部分结算不结算都一样。5 - 1 - 3 + 8 - 2 - 3 == 8 - 1 - 3. from: 1point3acres.com/bbs
   
回复 支持 反对

使用道具 举报

getway32 发表于 2015-10-27 10:14:20 | 显示全部楼层
akluffy 发表于 2015-10-21 01:28
我没有刻意往DP上面想general的答案。这代码也就适用于不限交易次数的情况下。

逻辑的核心就在于,

如果输入是 1 5 4 2 8呢。
回复 支持 反对

使用道具 举报

akluffy 发表于 2015-10-27 11:20:48 | 显示全部楼层
getway32 发表于 2015-10-27 10:14
如果输入是 1 5 4 2 8呢。

1 5 4 2 8 ,

直接 8 - 1 - 3 = 4,或者5 - 1 - 3=1加上 ,8-2-3 = 3,也是4.
所以两种都可以是因为5-2是3,等于交易费,所以交易两次跟一次实际上一样
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 20:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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