Google面经

say543 发表于 2015-8-30 09:07
请问LZ onsite 第三题怎么解? 没想到好的方法...

见最新补充，希望有所帮助

吞字。。。不明觉厉。。。hold[ i ] = max(hold[i-1], unhold[i-2] - price[ i ]) 和 unhold[ i ] = max(uphold[i-1], hold[i-1] + price[ i ])

adamru 发表于 2015-8-26 02:45
我是这么做的：
（1）直接存下输入二维数组就行 set就是O(1), query O(N)
（2）二维数组S存的是（0， 0 ...

lz 啊， 请教下，答案可以实现都是O(logN).

哪里有这个答案呢？ 多谢lz，祝lz好运

adamru 发表于 2015-9-1 10:19
吞字。。。不明觉厉。。。hold[ i ] = max(hold, unhold - price[ i ]) 和 unhold[ i ] = max(uphold, hold ...

感谢LZ 好牛 完全懂了~~

alucardzhou 发表于 2015-8-26 03:14
请问楼主能贴出网上那个答案的链接么？十分感谢

你可以搜一下树状数组，这题就是用树状数组可以达到，更新和取和都是log(n)的复杂度

楼主，电面第三问, set query 都很多，你是怎么答的？ 数状数组根本答不上啊。

股票没看懂， 楼主能不能发个代码啊。

hj867955629 发表于 2015-8-25 10:45
也可以这么想，每个字母可能被缩写了，也可能没被缩写，所以最后是2^n个。

那不就转换成求subset了

写了个第四题 word abbrivation 的代码

1. void abbrivationsHelper(string &s, int pos, vector<string> &ret, string tmp) {
   
2.         // base case
   
3.         if (pos >= s.length()) {
   
4.                 ret.push_back(tmp);
   
5.         }
   
6. 
   
7.         string tmp2;
   
8.         for (int i = pos; i < s.size(); i ++) {
   
9.                 if (i == pos) {
   
10.                         tmp2 = tmp;
    
11.                         tmp2 += s[i];
    
12.                         abbrivationsHelper(s, i + 1, ret, tmp2);
    
13.                 }
    
14.                 tmp2 = tmp;
    
15.                 tmp2 += to_string(i - pos + 1);
    
16.                 abbrivationsHelper(s, i + 1, ret, tmp2);
    
17.         }
    
18. }
    
19. 
    
20. vector<string> abbrivations(string &s) {
    
21.         vector<string> ret;
    
22.         abbrivationsHelper(s, 0, ret, "");
    
23.         return ret;
    
24. }
    
25. 
    
26. void printStrings(vector<string> ret) {
    
27.         for (int i = 0; i < ret.size(); i ++) {
    
28.                 cout << ret[i] << endl;
    
29.         }
    
30. }
    
31. 
    
32. void test() {
    
33.         vector<string> ret;
    
34.         string s = "abc";
    
35.         ret = abbrivations(s);
    
36.         printStrings(ret);
    
37.         s = "abbcc";
    
38.         ret = abbrivations(s);
    
39.         printStrings(ret);
    
40. }

复制代码

买股票的那题的代码

1. //卖完后间隔一天才能买
   
2. int stockDP(vector<int> prices) {
   
3.         if (prices.size() < 0) {
   
4.                 return 0;
   
5.         }
   
6. 
   
7.         vector<int> t(2, 0); // 0 means hold, 1 means unhold
   
8.         vector<vector<int>> dp(prices.size(), t);
   
9. 
   
10.         // dp[i][0] = max(dp[i-1][0], dp[i-2][1] - prices[i])
    
11.         // dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
    
12.         dp[0][0] = -prices[0];
    
13.         dp[0][1] = 0;
    
14.         for (int i = 1; i < prices.size(); i ++) {
    
15.                 // Case 1: hold
    
16.                 if (i == 1) {
    
17.                         dp[i][0] = max(dp[i-1][0], -prices[i]);
    
18.                 } else {
    
19.                         dp[i][0] = max(dp[i-1][0], dp[i-2][1] - prices[i]);
    
20.                 }
    
21.                 // Case 2: unhold
    
22.                 dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
    
23.         }
    
24.         return dp[prices.size()-1][1];
    
25. }
    
26. 
    
27. void test() {
    
28.         vector<int> prices;
    
29.         prices.push_back(1);
    
30.         prices.push_back(2);
    
31.         cout << stockDP(prices) << endl; // 1
    
32.         prices.push_back(3);
    
33.         prices.push_back(4);
    
34.         cout << stockDP(prices) << endl; // 3
    
35. 
    
36.         vector<int> prices2;
    
37.         prices2.push_back(1);
    
38.         prices2.push_back(3);
    
39.         prices2.push_back(1);
    
40.         prices2.push_back(4);
    
41.         cout << stockDP(prices2) << endl; // 3
    
42. 
    
43.         vector<int> prices3;
    
44.         prices3.push_back(4);
    
45.         prices3.push_back(3);
    
46.         prices3.push_back(2);
    
47.         prices3.push_back(1);
    
48.         cout << stockDP(prices3) << endl; // 0
    
49. }

复制代码