google onsite 12/18 面经

hulahu 发表于 2015-12-22 09:24
楼主， fibonacci 和 fibonacci 怎么做啊

Greedy 就可以了。每次选最大的数。然后把原数减去你选的数，再重复。

GatorAM 发表于 2015-12-31 07:23
楼主能详细说一下么？是不是假如有3个线程， 第一个线程产生所有括号序列并前三个是“（）（”，第二个线 ...

把string切成2半。一个线程数第一半多了几个（，另一个线程数第二半少了几个（，如果一样的话就是true。
你也可以多分几个线程，切成n份。

斐波那契数列那题，可以很简单的用递归来做

1. vector<int> findSeries(int target, set<int> fibonacci){
   
2.         if(fibonacci.find(target) != fibonacci.end()){
   
3.                 return {target};
   
4.         }
   
5.         auto it = lower_bound(fibonacci.begin(), fibonacci.end(), target);
   
6.         vector<int> res = findSeries(target - *it, fibonacci);
   
7.         res.push_back(*it);
   
8.         return res;
   
9. }

复制代码

算法的正确性 只要你理解任何数都可以用斐波那契数列和来表示 就能明白了


补充内容 (2018-12-31 09:10):
这里 auto it = lower_bound(fibonacci.begin(), fibonacci.end(), target);
这行应该改成找到数列里最大的小于target的数 不能用lower_bound 但核心思想就是这样