狗家匹村昂塞特

恭喜楼主拿到offter。我写了下第四轮， 还望大家指正

1. int maxSum(vector<int>& nums, int k, int index, int sum){  //using backtracking/ brute force
   
2.         if(index >= nums.size())
   
3.                 return sum;
   
4.         int res = INT_MIN;
   
5.         for(int i=index; i<nums.size(); i++){
   
6.                 if(nums[i] > 0)
   
7.                         res = max(res, maxSum(nums, k, i+k+1, sum+nums[i]));
   
8.                 else
   
9.                         res = max(res, maxSum(nums, k, i+1, sum));
   
10.         }
    
11.         return res;
    
12. }
    
13. 
    
14. int maxSum(vector<int> nums, int k){   // using DP
    
15.         for(int i=0; i<nums.size(); i++){
    
16.                 if(nums[i] <= 0)
    
17.                         nums[i] = i==0 ? 0 : nums[i-1];
    
18.                 else if(i-k-1<0 )
    
19.                         nums[i] = i==0 ? nums[i] : max(nums[i-1], nums[i]);
    
20.                 else // i-k1 >=0 && nums[i] > 0
    
21.                         nums[i] = max(nums[i-1], nums[i]+nums[i-k-1]);
    
22.         }
    
23.         return nums.back();
    
24. }

复制代码

Griffith♂Guts 发表于 2016-11-19 09:20
我也在等svp好慌啊。

你啥时候面的 也是匹兹堡office?

liqingfd 发表于 2016-11-19 11:36
你啥时候面的 也是匹兹堡office?

2周前，在mtv

ashun 发表于 2016-11-18 22:35
就每猜一次，根据结果，把剩下的词过滤一下，不可能的结果直接从dictionary里面去掉

我这个错了。请忽略


楼主好，是不是首先全部来相同字母，26遍，筛选出那几个字母。然后先去dict(这里用trie), 剪枝。然后按照5个字母的permutation去trie里找？

还要请问下一点，就是那个有向图的题目具体什么意思，能麻烦您在说一下吗

楼主第三轮是不是采用topological sort的做法?

zhan1612 发表于 2016-11-19 11:28
恭喜楼主拿到offter。我写了下第四轮， 还望大家指正

dfs可以用memorization优化一下，不加优化的时间复杂度应该是O(n!)

请教lz第三题有向无环图的输入是什么形式的呢？我感觉就遍历一边所有的边，统计入度为0的点就是根了吧，lz是怎么做的？

请问lz第一题的binary search是根据start时间找到小于target日期的第一个interval吗