Quora電面

據說是專愛考難題的quora ，所以我就放棄準備去面了
結果來了也不囉唆簡歷，直接一題dp ，其實不難的，但理解題意＋debug花了不少時間，估計是掛了

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

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

Sorry 積分不小心沒改設太高了，重發一下

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

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

就是小偷问题。。。谢谢分享

1. 
   
2. class Solution {
   
3. public:
   
4.   int rob(vector<int>& nums) {
   
5.     int sum_y = 0, sum_n = 0, tmp = 0;
   
6.     int n = nums.size();
   
7.     if (n == 0)
   
8.       return 0;
   
9.     vector<int> dp(n + 1, 0);
   
10.     vector<int> path(n + 1, 0);
    
11.     dp[0] = 0;
    
12.     dp[1] = nums[0];
    
13.     for (int i = 2; i <= n; i++) {
    
14.         if (dp[i-2] + nums[i-1] > dp[i-1]) {
    
15.             path[i] = i - 1;
    
16.             dp[i] = dp[i-2] + nums[i-1];
    
17.         } else {
    
18.             path[i] = i - 2;
    
19.             dp[i] = dp[i-1];
    
20.         }
    
21.     }
    
22.     for (int i : path)
    
23.       cout << i << ' ';
    
24.     cout << endl;
    
25.     for (int i : dp)
    
26.       cout << i << ' ';
    
27.     cout << endl;
    
28.     vector<int> res;
    
29.     int i = n;
    
30.     while (i > 0) {
    
31.       if (path[i] == i - 1) {  
    
32.         res.push_back(i-1);
    
33.         i = i - 2;
    
34.       }
    
35.       else {
    
36.         i = i - 1;     
    
37.       }
    
38.     }
    
39.     reverse(res.begin(), res.end());
    
40.     for (int i : res)
    
41.       cout << i << ' ';
    
42.     return dp[n];
    
43.   }
    
44. };
    

复制代码