狗家电面

狗家电面，接通电话后简单的自我介绍之后，开始做题。

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

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

参考LC124写了一个O(m*n)的解，用楼主给的两个例子似乎都是对的

1. int helper(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int row, int col, int& res) {
   
2.   int m = matrix.size(), n = matrix[0].size();
   
3.   if (row < 0 || row >= m || col < 0 || col >= n || matrix[row][col] == 0 || visited[row][col]) return 0;
   
4.   visited[row][col] = true;
   
5.   int left = helper(matrix, visited, row, col - 1, res);
   
6.   int right = helper(matrix, visited, row, col + 1, res);
   
7.   int up = helper(matrix, visited, row - 1, col, res);
   
8.   int down = helper(matrix, visited, row + 1, col, res);
   
9.   vector<int> tmp = {left, right, up, down};
   
10.   sort(tmp.begin(), tmp.end());
    
11.   res = max(res, matrix[row][col] + tmp[3] + tmp[2]); // get the largest two directions
    
12.   return matrix[row][col] + tmp[3];
    
13. }
    
14. 
    
15. int maxPath(vector<vector<int>>& matrix) {
    
16.   int m = matrix.size(), n = matrix[0].size();
    
17.   vector<vector<int>> connectedRegion(m, vector<int>(n, 0));
    
18.   vector<vector<bool>> visited(m, vector<bool>(n, false));
    
19.   int res = 0; // does not need to consider negative value
    
20.   for (int i = 0; i < m; ++i) {
    
21.     for (int j = 0; j < n; ++j) {
    
22.       if (matrix[i][j] != 0 && !visited[i][j]) {
    
23.         helper(matrix, visited, i, j, res);
    
24.       }
    
25.     }
    
26.   }
    
27. 
    
28.   return res;
    
29. }
    
30. 
    
31. int main(){
    
32.   vector<vector<int>> test1 = { {5,4,1,3}, {1,0,1,0}, {3,0,0,4}, {0,1,2,0} };
    
33.   assert(maxPath(test1) == 17);
    
34.   vector<vector<int>> test2 = { {5,4,1,0}, {1,0,1,2}, {3,0,0,4}, {0,1,2,0} };
    
35.   assert(maxPath(test2) == 21);
    
36.   return 0;
    
37. }

复制代码

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

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

关建在于没有环, 没有环 可以视为一个tree, 所以就是max tree path sum即可.

求大米！

码了。挺难的，没思路看起来。

求问楼主，
[1,2,3]
[4,0,5]
[6,7,8] 比如这个的话最大path就是环形走一遍得到1+2+。。。+8么？所以path终止条件就是碰到上下左右的情况如果都是1。出界 2。碰到0 3。已经走过的数，碰到这三种就停止，算是得到了一条路径是么？
已经加米，谢谢楼主。

虎蝇孑 发表于 2019-9-27 07:06
求问楼主，
[1,2,3]
[4,0,5]

题目条件是不会形成环，你给的例子跟条件不符合。

我觉得应该是先找到connected component, 然后在里面找maximum path sum，结束之后依然不会做。

看起来很像求一个hamilton路径，也就是路过可能的所有数，有且仅有一次，不同的地方在于，这题是求值的，而且没有终止点

是不是用DFS就能做？每个值遍历一遍

求hamilton图，似乎只能暴力搜索

马一下。有点难。第一反应也是，相当于被0分割出多个孤岛，每个孤岛元素求和。。但是这样就不能保证路径了。。
感觉dfs + backtrack

把matrix看成undirected graph, 找Maximum path sum? 用DFS走，走過的點就設成visited