Facebook 新题

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. 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.         }

复制代码

请问这题有最后讨论出看法一致的结果吗? 能否帮我看看下面的代码对不对？
Let local[i] be the max profit of making a sell on day i, global[i] be max profit after day i.
update local[i] 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[i] 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.     }

复制代码

mark一下

martin5678 发表于 2016-4-1 06:31
个人想法：

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

这样不能保证值为最大把。 比如 1，5，4，10 。 fee为2。按你的解法答案为6. （4-2 ＋ 6-2）。但最大应该为7（10-1-2）才对吧。 不知道是不是我理解有误。

public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[] buy = new int[n + 1], sell = new int[n + 1];
        buy[0] = Integer.MIN_VALUE;
        for (int i = 1; i <= n; ++i) {
            buy[i] = Math.max(buy[i - 1], sell[i - 1] - prices[i - 1] - fee);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i - 1] - fee);
        }
        return sell[n];
    }

https://discuss.leetcode.com/topic/72011/fb-phone-interview-best-time-to-buy-and-sell-stock-follow-up-with-transaction-fee/11

mitchellhe 发表于 2017-9-19 02:28
public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[] buy = n ...

没有必要O(n) space. sell[n] 永远是最大的...