Citadel的变态OA 欢迎大家讨论

刚写完凉了，楼主一定和我一样没仔细读题。第二题是一天只能买1share OR 卖any share，应该是不能同时进行的

pkk5488 发表于 2018-9-8 23:41
刚写完凉了，楼主一定和我一样没仔细读题。第二题是一天只能买1share OR 卖any share，应该是不能同时进行 ...

C家据说sde new grad一年招个位数，除了return 的intern，所以move on就好

Anakin09 发表于 2018-9-9 00:07
C家据说sde new grad一年招个位数，除了return 的intern，所以move on就好

噗 好的 就算是练练手了

第二题我也是和楼主一样的想法
第三题好像不是太难 主要是遍历的方式已经限制了 哪个child小就先放它就好了  还是我想的太简单了？

第二题我感觉就是找最大值。。

第三题憋了半天也没憋出来。。爆炸了

https://pastebin.com/16bDzZP7

有人可以解释E1 E2问题的要求吗？

我也只做出来第一题，心态爆炸了。。。不过我后来想了下第二题，楼主你看看这个行不行？暂时只能想出这个时间复杂度的解法了。如果你想交流，可以发我email: davechan813@gmail.com. 谢谢啦！

1. #include <iostream>
   
2. 
   
3. int helper(const vector<int>& prices, int l, int maxIndex) {
   
4.     int res = 0;
   
5.     for (int i = l; i < maxIndex; i++) res += max(0, prices[maxIndex] - prices[i]);
   
6.     return res;
   
7. }
   
8. 
   
9. int maxProfit(const vector<int>& prices, int l, int r) {
   
10.     if (l >= r) return 0;
    
11.    
    
12.     int maxPrice = INT_MIN, maxIndex = -1;
    
13.     for (int i = l; i <= r; i++)
    
14.         if (prices[i] > prices[i-1] && prices[i] > maxPrice) {
    
15.             maxPrice = prices[i];
    
16.             maxIndex = i;
    
17.         }
    
18.         
    
19.     if (maxIndex == l) return 0;
    
20.     return helper(prices, l, maxIndex) + maxProfit(prices, maxIndex+1, r);
    
21. }
    
22. 
    
23. int maxProfit(const vector<int>& prices) {
    
24.     return maxProfit(prices, 0, prices.size()-1);
    
25. }
    
26. 
    
27. int main() {
    
28.     // vector<int> prices = {6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4}; // 16
    
29.     // vector<int> prices = {7, 8, 10, 3, 2, 1, 0, 1, 2, 3, 4}; // 21
    
30.     // vector<int> prices = {5, 3, 2}; // 0
    
31.     // vector<int> prices = {1, 2, 100}; // 197
    
32.     vector<int> prices = {1, 3, 1, 2}; // 3
    
33.     cout<<maxProfit(prices)<<endl;
    
34. }

复制代码