一亩三分地论坛

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

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

[算法题] Facebook 新题

[复制链接] |试试Instant~ |关注本帖
ccgogo123 发表于 2015-7-3 11:15:17 | 显示全部楼层 |阅读模式

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

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

x
best time to sell stock II,允许sell无限多次,但是每次sell都要给3$的代价,问说如何获得最大的profit。希望大家一起讨论讨论
stellari 发表于 2015-7-4 15:51:51 | 显示全部楼层
本帖最后由 stellari 于 2015-7-4 16:32 编辑

我给一个思路吧(虽然还不能严格证明正确性)。希望抛砖引玉:

首先,我们肯定不会在非“谷值”的地方买入,也不会在非“峰值”的地方卖出。所以,为了简化问题,我们先提取出这个序列中所有的“谷值”和“峰值”。分别存放于队列A和B中。

接下来,这个问题和Stock II的唯一区别就在于每次交易要收取佣金,所以使得有时候多次连续交易来得不如合并成一次划算。比如[1->20, 18->30]两次交易=>19-3 + 12-3 = 25,就不如[1->30]一次交易=>30-1-3=26来得划算。

假设第i次交易的始终价格分别为(Ai, Bi),而第i+1次交易为(Ai+1, Bi+1);那么,
当两交易的profit都>=3时,
分开交易的收益是
Bi+1-Ai+1 + Bi-Ai - 6而合起来交易的收益是
Bi+1-Ai -3
所以,如果两次交易应该合并,则必有:
Bi+1-Ai -3 >= Bi+1-Ai+1 + Bi-Ai - 6

Bi - Ai+1 <= 3 ....... (a)

如果仅有第二个交易的profit小于3,那么上述条件(a)是不充分的,比如[1 -> 100],[98 -> 99]这种情况本来不应该合并。所以,此时还应检查是否有
Bi+1 >= Bi ...... (b)

如果仅有第一个交易的profit小于3,那么(a), (b)也是不充分的,比如[2 -> 3], [1 -> 100]这种情况不应合并。所以,此时应检查是否有
Ai+1 >= Ai ...... (c)

如果两个交易的profit都<=3,那么此时无论两个交易的始末值如何,总是可以合并。因为,如果合并后的profit依然<3,甚至变为负值,那么我们可以在最后的postprocessing步骤忽略掉这次交易;如果合并后的profit>3,那么我们本来就应该合并这两次交易。所以合并总是正确的选择。


综上所说,我们能够合并两次交易的充分条件是(a) & (b) & (c).

所以,我们依次取出A和B中每一对元素(Ai, Bi),检查它们和上一对元素(Ai-1, Bi-1)是否满足这个关系。如果是的话,则合并二者为(Ai-1, Bi),不是的话则二者均保留。然后继续检查下一对元素。

在合并时,每个范围最多会被合并一次。比如(A3, B3)如果已经被合并到(A4, B4)中去,那么以后就不会再单独检查(A3, B3)了。相当于每个范围最多被删除一次。所以最后总时间应该仍然是O(N)。

最后,统计没有被合并的范围的个数。如果其中出现profit<3的交易,则认为其profit为0(即不进行此次交易)。

代码如下:
  1. int getMaxProfitV(vector<int>& prices)
  2. {
  3.     int N = prices.size();
  4.     queue<int> A, B;
  5.     // 找到所有峰值和谷值
  6.     for (int i = 0; i < N; ++i) {
  7.         int left = (i == 0)? INT_MAX: prices[i-1];
  8.         int right = (i == N-1)? INT_MIN: prices[i+1];

  9.         if (left <= prices[i] && prices[i] > right) {
  10.             B.push(prices[i]);
  11.         }
  12.         else if (left > prices[i] && prices[i] <= right) {
  13.             A.push(prices[i]);
  14.         }
  15.     }

  16.     stack<pair<int, int> > res;
  17.     res.push(pair<int, int>(A.front(), B.front()));
  18.     A.pop(); B.pop();
  19.    // 维护一个stack。每次新处理一次交易,就试图将此次交易与栈顶的交易合并,直到不能合并为止。
  20.     while (!A.empty()) {
  21.         int lo = A.front(), hi = B.front();
  22.         A.pop(); B.pop();

  23.         // 虽然是二重循环,但是push操作只进行了N次,所以pop操作也最多只能进行O(N)次。最后总时间依然是O(N)。
  24.         // (a), (b), (c) 三条件必须都满足
  25.         while (!res.empty() &&
  26.                 res.top().first <= lo &&
  27.                 res.top().second - lo <= 3 &&
  28.                 res.top().second <= hi
  29.                ) {
  30.             lo = res.top().first;
  31.             res.pop();
  32.         }
  33.         res.push(pair<int, int>(lo, hi));
  34.     }
  35.     int sum = 0;
  36.     // 最后统计所有的范围,<3的则看做0.
  37.     while(!res.empty()) {
  38.         pair<int, int> cur = res.top(); res.pop();
  39.         cout << cur.first << ", " << cur.second << endl;
  40.         if (cur.second - cur.first > 3) {
  41.             sum += cur.second - cur.first - 3;
  42.         }
  43.     }
  44.     return sum;
  45. }
复制代码
代码看起来有点丑是真的。我猜这题应该也可以通过类似于其他stock题那样用DP来做,不过我还没想到具体解法。

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

stellari 发表于 2016-3-21 10:31:43 | 显示全部楼层
returning 发表于 2016-3-21 01:52
我隐约感觉这道题你想复杂了,题目并不是lc上的stock II,题目是说你可以在某天sell多次。lc上的题每天是 ...

确实这道题可能说得略模糊,我的解法也只是个人理解。我的理由是,

1. lz先说了“best time to sell stock II”这句话,我认为他想表达的是:“一切假设都和Stock II一样,唯一的不同是。。。”,其中包括“不得同时持有多股”这一点。

2. 如果你的理解是正确的,那么题目中必须加入两个关键表述:“能够同时持有多股”和“每次卖出能卖一股/多股”。我认为lz表述时不会漏掉这么多关键信息,所以我倾向于认为这两个假设一开始就不存在。另外lz原话是“可以sell无限次”,并非“可以在同一天内sell无限次”。

3. 按你的理解,此题难度会低得多。可能甚至低于Stock I。这种情况下,我认为lz一开始就不会出来问这道题;况且这种难度的题对于Facebook的申请者来说区分度较低,不太适合。


其实,无论咱们现在怎么理解这道题并不重要,关键问题是如果真的面试时问出了按我的理解方式的题,是否能快速答出来呢?
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-7-8 13:39:46 | 显示全部楼层
milanelllo13 发表于 2015-7-8 12:43
这道题,我问过我一个同学。  他给的思路是:  这个题就是找很多对相邻的极小值和极大值点。  然后某一对极 ...

咱们判断算法正确性可不能靠感觉啊。考虑下面这个例子:
[1 9 8 100]

四个点中有两个极大,两个极小点,共两次交易,每次的profit都大于佣金。所以如果按这个算法,总利润是

9-1 - 3 + 100-8 - 3 = 8 + 92 - 6= 94

但是事实上这个例子的最大profit是一次交易:

100 - 1 -3 = 99 - 3 = 96

所以这题的难点是在于考虑合并多次交易的情况(见上上楼)。
回复 支持 1 反对 0

使用道具 举报

tangchensr 发表于 2015-7-4 09:40:09 | 显示全部楼层
本帖最后由 tangchensr 于 2015-7-4 09:46 编辑

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {

        if(prices.empty() || prices.size() == 1)
        {
            return 0;
        }

        int maxProfit = 0;
        int localProfit = 0;
        for(int i = 1; i < prices.size(); i++)
        {
            if(prices[i - 1] < prices)
            {
                localProfit += prices - prices[i - 1];
            }
            else
            {
                if(localProfit >= 3)
                {
                    maxProfit += localProfit - 3;
                }
                localProfit = 0;
            }
        }
        return maxProfit;
    }
};
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-4 10:38:19 | 显示全部楼层
tangchensr 发表于 2015-7-4 09:40
class Solution
{
public:

这个程序应该不行。

首先,代码中有点问题:如果prices如果一直是上升的,那么maxProfit就永远不会得到更新,所以最后一定会返回0。所以在循环结束以后应该再更新一次maxProfit;

其次,即使这样做了,这个算法也是不对的。因为,最大的profit未必是每个序列单独的profit之和。比如[1, 3, 2, 100]这个序列。你的算法中会先找到[1, 3]这个上升序列,其profit<=3,所以扔掉;再看[2, 100]这个序列,得到98,减3得95。而事实上这个序列的最大profit应该是100 - 1 - 3 = 96才对。
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-7-8 12:43:21 | 显示全部楼层
这道题,我问过我一个同学。  他给的思路是:  这个题就是找很多对相邻的极小值和极大值点。  然后某一对极大值减去极小值大于commission fee,就算一次交易。    感觉是对的!
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-7-8 13:57:08 | 显示全部楼层
stellari 发表于 2015-7-8 13:39
咱们判断算法正确性可不能靠感觉啊。考虑下面这个例子:
[1 9 8 100]

谢谢。他有和我说过 要和前一次合并。。我自己给忘记了。。   谢谢哈哈哈
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-6 14:43:37 | 显示全部楼层
stellari 发表于 2015-7-4 15:51
我给一个思路吧(虽然还不能严格证明正确性)。希望抛砖引玉:

首先,我们肯定不会在非“谷值”的地方买 ...

我同意你的看法。
我的想法是遍历数组,找increasing sub list,然后把这个sublist的 (min,max)存到stack里,
在继续找下一个increasing sub list,再与stack顶部的(min,max)合并。

其实这道题像是merge intervals的变种
回复 支持 反对

使用道具 举报

lrn0304 发表于 2015-10-29 05:31:42 | 显示全部楼层
当有收益时候竟可能的让收益最大再卖掉.
回复 支持 反对

使用道具 举报

returning 发表于 2016-3-21 01:52:33 | 显示全部楼层
stellari 发表于 2015-7-4 15:51
我给一个思路吧(虽然还不能严格证明正确性)。希望抛砖引玉:

首先,我们肯定不会在非“谷值”的地方买 ...

我隐约感觉这道题你想复杂了,题目并不是lc上的stock II,题目是说你可以在某天sell多次。lc上的题每天是没法buy or sell多次的。比如如下数组[1, 3, 15,20],最佳收益是20-1 + 20-3 + 20-15, 也就是说每天都买,但是最后一天卖出。所以,如果加上限制条件,那就只需要考虑当前和最大的差值是否少于3,如果少于3,买了也白买。我觉得这样就够了。
回复 支持 反对

使用道具 举报

martin5678 发表于 2016-4-1 06:31:31 | 显示全部楼层
个人想法:

找出所有的增加区间,如果收入大于代价就加入

如果有错误烦请指正
  1. public static int stock(int[] prices, int fee) {
  2.                 int buyVal = prices[0];
  3.                 int sellVal = prices[0];
  4.                 int profit = 0;
  5.                 for (int i = 1; i < prices.length; i++) {
  6.                         if (prices[i] >= prices[i - 1]) {
  7.                                 sellVal = prices[i];
  8.                         } else {
  9.                                 if (sellVal - buyVal > fee) {
  10.                                         profit += sellVal - buyVal - fee;
  11.                                 }
  12.                                 buyVal = prices[i];
  13.                                 sellVal = prices[i];
  14.                         }
  15.                 }
  16.                 if (sellVal - buyVal > fee) {
  17.                         profit += sellVal - buyVal - fee;
  18.                 }
  19.                 return profit;
  20.         }
复制代码
回复 支持 反对

使用道具 举报

JohnDoe 发表于 2016-4-17 15:45:20 | 显示全部楼层
请问这题有最后讨论出看法一致的结果吗? 能否帮我看看下面的代码对不对?
Let local be the max profit of making a sell on day i, global be max profit after day i.
update local first:
1. do not buy on day i-1 (latest valley is before i-1). we simply extend the previous sell at day i-1 to day i
2. make a buy on day i-1 (latest valley is at i-1). Make the transaction and append to global[i-1].
Take the max of the two.
Update global then, take of max of sell on i or not.
  1. public int buyAndSellWithFee(int[] prices, int fee){
  2.         if(prices.length<2) return 0;
  3.         int local=0-fee, global=0;
  4.         for(int i = 1; i<prices.length; i++){
  5.             local=prices[i]-prices[i-1]+Math.max(local,global-fee);
  6.             if(local>global) System.out.println("sell at "+i);
  7.             global=Math.max(global,local);
  8.         }
  9.         return global;
  10.     }
复制代码
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-9-30 13:38:15 | 显示全部楼层
martin5678 发表于 2016-4-1 06:31
个人想法:

找出所有的增加区间,如果收入大于代价就加入

这样不能保证值为最大把。 比如 1,5,4,10 。 fee为2。按你的解法答案为6. (4-2 + 6-2)。但最大应该为7(10-1-2)才对吧。 不知道是不是我理解有误。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 00:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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