狗家电面

ysboss123

虎蝇孑发表于 2019-9-27 11:37
我觉得那个代码应该停的下来的 base check的时候出边界或者等于0就停了，但是我感觉时间复杂度有点高是 ...

嗯复杂度应该是这个。太高了，可以讨论下怎么优化。。。

ysboss123

jjames 发表于 2019-9-27 11:31
谢谢你提供的代码，感觉还是有些问题，没有visited status，感觉dfs会无线进行下去。
加上visited statu ...

可以停下的，每走一步都把这步改位0，backtrack的时候再赋值回原值。就是复杂度太高了

reliveinfire

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

onewaymyway

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

细雨微张

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

细雨微张

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

int helper(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int row, int col, int& res) {
int m = matrix.size(), n = matrix[0].size();
if (row < 0 || row >= m || col < 0 || col >= n || matrix[row][col] == 0 || visited[row][col]) return 0;
visited[row][col] = true;
int left = helper(matrix, visited, row, col - 1, res);
int right = helper(matrix, visited, row, col + 1, res);
int up = helper(matrix, visited, row - 1, col, res);
int down = helper(matrix, visited, row + 1, col, res);
vector<int> tmp = {left, right, up, down};
sort(tmp.begin(), tmp.end());
res = max(res, matrix[row][col] + tmp[3] + tmp[2]); // get the largest two directions
return matrix[row][col] + tmp[3];
}
int maxPath(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> connectedRegion(m, vector<int>(n, 0));
vector<vector<bool>> visited(m, vector<bool>(n, false));
int res = 0; // does not need to consider negative value
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] != 0 && !visited[i][j]) {
helper(matrix, visited, i, j, res);
}
}
}
return res;
}
int main(){
vector<vector<int>> test1 = { {5,4,1,3}, {1,0,1,0}, {3,0,0,4}, {0,1,2,0} };
assert(maxPath(test1) == 17);
vector<vector<int>> test2 = { {5,4,1,0}, {1,0,1,2}, {3,0,0,4}, {0,1,2,0} };
assert(maxPath(test2) == 21);
return 0;
}

复制代码

虎蝇孑

细雨微张发表于 2019-9-27 23:17
复杂度应该是远远高于O(m^2n^2)的。O(m2n2)的意思是以矩阵中的任意一个元素作为出发点，然后遍历所有的矩 ...

啊好像是谢谢解释

laura9

dfs找岛，每个岛构造一个三叉树来求max path sum

Hanna097

怎么感觉有些电面很简单有些很难呢emm

savage811

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