google加面

alanlxl 发表于 2018-3-31 10:14
round2应该可以简单如下解决，思路是：一个点成为一棵树的root，当且仅当它不被删除 and 它的父亲被删除
* ...

line 9 - line 14可以这样？
if(shouldeDelete(parent) && !shouldDelete(curr))
         result.push_back(curr);

lf963 发表于 2018-4-2 05:42
我寫出來了，寫完後發現和之前那位用三維dp的很像，由於題目說了正數不會形成 cycle ，所以才能用記憶法
...

好像没问题 速度也快了很多 给老哥点赞👍 我在学习一下

lf963 发表于 2018-4-2 05:42
我寫出來了，寫完後發現和之前那位用三維dp的很像，由於題目說了正數不會形成 cycle ，所以才能用記憶法
...

请问 这个 int temp = DFS(maze,memorization,nextX,nextY,3 - dir); 是什么意思？

flyPacific111 发表于 2018-4-2 07:26
line 9 - line 14可以这样？
if(shouldeDelete(parent) && !shouldDelete(curr))
         result.push ...

嗯差不多的意思，只是如果cur被删除的话，要记得断开它与左右子的连接

alanlxl 发表于 2018-4-2 14:39
嗯差不多的意思，只是如果cur被删除的话，要记得断开它与左右子的连接

我又看了一下，发现还有个问题。如果curr需要被删除，还需要切断parent和curr的联系吧

flyPacific111 发表于 2018-4-2 22:00
我又看了一下，发现还有个问题。如果curr需要被删除，还需要切断parent和curr的联系吧

其实cur = NULL就行了。。

第一题第二问，由于无环，dfs一遍不会重复，应该是不需要任何extra space（标记数组坐在原数组上）， O（nm）矩阵大小就能做。

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. inline check(vector<vector<int>>& vec, int i, int j){
   
7.     return i >= 0 && j >= 0 && i < vec.size() && j < vec[0].size() && vec[i][j] > 0;
   
8. }
   
9. 
   
10. int dfs(vector<vector<int>>& vec, int i, int j, int ii, int jj, int& maxmine){
    
11.     int val = vec[i][j];
    
12.     int curmax = 0, accummax = 0;
    
13.     int l = 0, r = 0, u = 0, d = 0;
    
14.     if(check(vec,i+1,j) && (i+1 != ii || j != jj))r = dfs(vec,i+1,j,i,j,maxmine);
    
15.     if(check(vec,i-1,j) && (i-1 != ii || j != jj))l = dfs(vec,i-1,j,i,j,maxmine);
    
16.     if(check(vec,i,j+1) && (i != ii || j+1 != jj))d = dfs(vec,i,j+1,i,j,maxmine);
    
17.     if(check(vec,i,j-1) && (i != ii || j-1 != jj))u = dfs(vec,i,j-1,i,j,maxmine);
    
18.     accummax = max(r,max(l,max(d,u)));
    
19.     curmax = max(l+r,max(l+u,max(l+d,max(r+u,max(r+d,u+d)))));
    
20.     maxmine = max(maxmine,curmax+val);
    
21.     vec[i][j] = 0;
    
22.     return val + accummax;
    
23. }
    
24. 
    
25. int maxMine(vector<vector<int>>& vec){
    
26.     int n = vec.size();
    
27.     if(n == 0)return 0;
    
28.     int m = vec[0].size();
    
29.     int maxmine = 0;
    
30.     for(int i=0;i<n;i++){
    
31.         for(int j=0;j<m;j++){
    
32.             if(vec[i][j] > 0){
    
33.                 dfs(vec,i,j,-1,-1,maxmine);
    
34.             }
    
35.         }
    
36.     }
    
37.     return maxmine;
    
38. }
    
39. 
    
40. int main(){
    
41.     vector<vector<int>> vec({{1,0,0,0,2,4,6,0,0,1},
    
42.                             {3,1,4,3,0,0,1,2,0,2},
    
43.                             {5,0,0,2,1,0,0,3,0,3},
    
44.                             {0,0,0,0,5,6,5,4,1,4},
    
45.                             {2,4,6,0,4,0,7,0,2,0},
    
46.                             {0,0,1,2,3,0,8,0,3,0},
    
47.                             {0,0,2,0,0,0,9,0,4,0},
    
48.                             {0,0,3,4,5,0,0,0,0,0},
    
49.                             {0,0,0,0,6,5,3,4,9,0},
    
50.                             {1,2,3,4,5,0,2,0,0,0}});
    
51.     cout << maxMine(vec) << endl;
    
52. }
    

复制代码

c艹的，上面老哥的样例，答案应该是91. 如果有问题欢迎指正~

尴尬，竟然给offer了。可惜太晚了，已经签了。。。

请问第一题iterator怎么写呢 感觉并不好写啊

请问一下楼主，到底是什么决定四轮还是五轮呀？我以为new grad都是4轮？