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

daguanyuan 发表于 2017-6-30 06:16
返例：2， 2， 2， 2， 2， 3， 7， worker：2
不知到这么久了有合适的解了么？

看leetcode 410. 应该是一样的

关注一下，也在准备昂赛

扫描线算法 怎么算这个矩形重合？
那位大牛能简单说下？
我还看见有题是算多个圆重合，答案是先看包含圆的矩形是否重合（用扫描线），然后确认里面圆形是否重合

scredwood 发表于 2017-7-1 03:47
看leetcode 410. 应该是一样的

好像不一样。LC上要求是连续的，这里要求是不连续的。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Q2, Prob 2: I don't think it is typical DP. It seems to just update max sum while sliding the window. Using more space in exchange of time.

1. int max3KSum(vector<int>& a, int k) {
   
2.         int n = a.size();
   
3.         vector<int> L2RMaxKSum(n - k + 1), R2LMaxKSum(n - k + 1), sum(n- k + 1);
   
4. 
   
5.         L2RMaxKSum[0] = sum[0] = accumulate(a.begin(), a.begin() + k, 0);
   
6.         for (int i = 1; i <= n - k; ++i)
   
7.                 L2RMaxKSum[i] = max(L2RMaxKSum[i - 1], sum[i] += (a[i + k - 1] - a[i - 1]));
   
8. 
   
9.         R2LMaxKSum[n - k] = sum[n - k];
   
10.         for (int i = n-k-1; i >= 0; --i)
    
11.                 R2LMaxKSum[i] = max(R2LMaxKSum[i + 1], sum[i]);
    
12. 
    
13.         int res = 0;
    
14.         for (int i = k; i + 2 * k < n; ++i)
    
15.                 res = max(res, sum[i] + L2RMaxKSum[i - k] + R2LMaxKSum[i + k]);
    
16.         return res;
    
17. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一题就是基于背包的贪心吧，相当于有worker个背包，每次尽可能装满，去掉那些用过的元素，然后在装下一个包，所以复杂度基本是O((worker-1)*(sum(tasks)/worker*len(tasks)))