nice,有进步了,这是一道hard题目,而我自己写的,过了135/138个测试用例,没过的是因为超时了,说明不够优化
给定一个 m x n
整数矩阵 matrix
,找出其中 最长递增路径 的长度。
对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。
示例 1:
输入: matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
我一开始写的代码超时了,需要记录重复走过的地方,但是当我记录的时候用了布尔数组发现一点作用都没起到:
class Solution {
int n, m, ans = 0;
boolean[][] state;
public int longestIncreasingPath(int[][] matrix) {
m = matrix.length;
n = matrix[0].length;
state = new boolean[m + 10][n + 10];
for(int i = 0;i < m;i ++) {
for(int j = 0;j < n;j ++) {
dfs(matrix, i, j, 0);
}
}
return ans;
}
public void dfs(int[][] matrix, int x, int y, int nums) {
if(!notArea(x, y)) return;
nums ++;
ans = Math.max(ans, nums);
if(notArea(x + 1, y) && matrix[x + 1][y] > matrix[x][y]) dfs(matrix, x + 1, y, nums);
if(notArea(x - 1, y) && matrix[x - 1][y] > matrix[x][y]) dfs(matrix, x - 1, y, nums);
if(notArea(x, y + 1) && matrix[x][y + 1] > matrix[x][y]) dfs(matrix, x, y + 1, nums);
if(notArea(x, y - 1) && matrix[x][y - 1] > matrix[x][y]) dfs(matrix, x, y - 1, nums);
}
public boolean notArea(int x, int y) {
if(x < 0 || y < 0 || x >= m || y >= n) return false;
return true;
}
}
然后问了下chatgpt如何优化我的代码,它提出了采用记忆化搜索的方式,记录已经访问过的位置的最长递增路径长度,记忆数组memo
class Solution {
int m, n;
int[][] memo; // 记忆数组
public int longestIncreasingPath(int[][] matrix) {
m = matrix.length;
n = matrix[0].length;
memo = new int[m][n];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
ans = Math.max(ans, dfs(matrix, i, j, Integer.MIN_VALUE)); // 对每个点进行深度优先搜索
}
}
return ans;
}
public int dfs(int[][] matrix, int x, int y, int prev) {
if (x < 0 || y < 0 || x >= m || y >= n || matrix[x][y] <= prev) {
return 0; // 超出边界或者不满足递增条件,返回长度为0
}
if (memo[x][y] != 0) {
return memo[x][y]; // 如果已经计算过该位置,直接返回其结果
}
int cur = matrix[x][y]; // 当前位置的值
int pathLen = 0; // 记录当前路径的长度
// 搜索当前位置的上下左右节点
pathLen = Math.max(pathLen, dfs(matrix, x + 1, y, cur));
pathLen = Math.max(pathLen, dfs(matrix, x - 1, y, cur));
pathLen = Math.max(pathLen, dfs(matrix, x, y + 1, cur));
pathLen = Math.max(pathLen, dfs(matrix, x, y - 1, cur));
memo[x][y] = pathLen + 1; // 记录当前位置的最长递增路径长度
return pathLen + 1;
}
}
在深度优先搜索时,如果遇到已经计算过的位置,则直接返回其结果,避免了重复计算。这种方式可以避免超时情况,提高了效率。