求大神讨论Facebook 面经经典难题

say543 发表于 2017-3-30 14:31
看不太懂 你怎么用一维限制只找三个.....

一维数组实现二维DP嘛，本来二维表就是一行一行挨个写下来的

这个二维表的行是假设有nn个subarray, nn就是  行index+1

DP(nn, i) = Max(DP(nn-1, i-k)+sum(i-k, i), DP(nn, i-1))
这个是状态转移方程， DP是有subarray的个数下，从0到i的最大值。sum(i-k, i)是元素从i-k到i的累加和
状态转移方程的体现在第13行

这个代码是测试过的，应该没大问题，我发之前应该写注释的

补充内容 (2017-3-30 15:43):
DP是有subarray的个数下
=>DP是有nn个subarray的个数下

大神，可以用greedy吗？task从高到低排个序，然后用一个min heap, 每次把work load最小的worker弹出来，把当前最大的task分配给他。

补充内容 (2017-4-24 16:02):
我是说第一题

第一题，有两个worker的情况实际上是在求最接近总量／2的subset，在workload有限的情况下是背包。worker>2硬说是dp也可以，复杂度就变成 workload^#workers了。还是dfs吧。
第二题dp，O(n)
第三题扫描线没毛病

sfsttz 发表于 2017-4-24 18:01
第一题，有两个worker的情况实际上是在求最接近总量／2的subset，在workload有限的情况下是背包。worker>2 ...

我后来做了研究，基本确定了第一题属于NP HARD  叫多背包问题，就像你说的那样。
面试官问的时候就是在碰瓷，解释清楚然后问要不就用简单的heuristic可以不

翻滚吧豆子 发表于 2017-4-25 00:05
我后来做了研究，基本确定了第一题属于NP HARD  叫多背包问题，就像你说的那样。
面试官问的时候就是在 ...

楼主大神，能展开说一下，或者给个link？

xiaobai123 发表于 2017-4-25 02:37
楼主大神，能展开说一下，或者给个link？

http://www.or.deis.unibo.it/kp/Chapter6.pdf
这里

翻滚吧豆子 发表于 2017-3-30 07:48
是的，这道题和股票IV很像

有个小bug，当length=n*k的时候，并没有update lastmax。
我稍改了一下，不过是C++

1. int findNWindow(vector<int>& nums, int K, int n){
   
2.         int m = nums.size();
   
3.     vector<int> lastMaxK(m,0);
   
4.     vector<int> maxK(m,0);
   
5. 
   
6.     for(int i=0; i<n; i++){
   
7.             int curSum=0;
   
8.             for(int j=i*K; j<m; j++){
   
9.                     curSum += nums[j];
   
10. 
    
11.                     if (j<(i+1)*K-1) continue;
    
12.                     if (j>=(i+1)*K) curSum -= nums[j-K];
    
13. 
    
14.                     if (j==K-1) maxK[j] = curSum;
    
15.                     else maxK[j] = max(lastMaxK[j-K] + curSum, maxK[j-1]);
    
16.             }
    
17.             swap(maxK, lastMaxK);
    
18.     }
    
19.     return lastMaxK[m-1];
    
20. }

复制代码

翻滚吧豆子 发表于 2017-4-25 00:05
我后来做了研究，基本确定了第一题属于NP HARD  叫多背包问题，就像你说的那样。
面试官问的时候就是在 ...

第一题怎么能算np hard的问题呢？你都能用二分搜索 （多项式时间）搜索有效解了。
乍看是个NP， 实际是个P吧。

补充内容 (2017-5-28 01:12):
这道题是个P问题，binary Search上下限，验证解的正确性， 都是多项式复杂时间。 这个题和多背包问题相比，约束条件少很多，物品的体积都是1， 背包的空间（工人工作数量无限）。

xiaobai123 发表于 2017-4-24 16:01
大神，可以用greedy吗？task从高到低排个序，然后用一个min heap, 每次把work load最小的worker弹出来，把 ...

返例：2， 2， 2， 2， 2， 3， 7， worker：2
不知到这么久了有合适的解了么？

关注一下