l***e
发帖数: 303 | 1 You are given a grid of numbers. A snake sequence is made up of adjacent
numbers such that for each number, the number on the right or the number
below it is +1 or -1 its value. For example,
1 3 2 6 8
-9 7 1 -1 2
1 5 0 1 9
In this grid, (3, 2, 1, 0, 1) is a snake sequence.
Given a grid, find the longest snake sequences and their lengths (so there
can be multiple snake sequences with the maximum length).
用dfs的话不太好算最长的sequences 用DP没思路 |
e*******s
发帖数: 1979 | 2 path可以交叉重叠不
【在 l***e 的大作中提到】
: You are given a grid of numbers. A snake sequence is made up of adjacent
: numbers such that for each number, the number on the right or the number
: below it is +1 or -1 its value. For example,
: 1 3 2 6 8
: -9 7 1 -1 2
: 1 5 0 1 9
: In this grid, (3, 2, 1, 0, 1) is a snake sequence.
: Given a grid, find the longest snake sequences and their lengths (so there
: can be multiple snake sequences with the maximum length).
: 用dfs的话不太好算最长的sequences 用DP没思路
|
l***e
发帖数: 303 | 3 看字面 应该可以
【在 e*******s 的大作中提到】
: path可以交叉重叠不
|
e*******s
发帖数: 1979 | 4 那cycle怎么办
【在 l***e 的大作中提到】
: 看字面 应该可以
|
l***e
发帖数: 303 | 5 cycle不行 交叉或许可以 网上看的题 只能从文字理解
【在 e*******s 的大作中提到】
: 那cycle怎么办
|
e*******s
发帖数: 1979 | 6 把这个图做下edge vertice convert
node value为以前edge对应的diff
然后把不为1的node都去掉
在在上面做DFS应该可以了吧
【在 l***e 的大作中提到】
: cycle不行 交叉或许可以 网上看的题 只能从文字理解
|
r*****3
发帖数: 27 | 7 不能交叉吧... 只能取右边的或者下边的number |
R***Z
发帖数: 1167 | 8 用DP的话，从右下角往左上角倒推应该可以吧
【在 l***e 的大作中提到】
: You are given a grid of numbers. A snake sequence is made up of adjacent
: numbers such that for each number, the number on the right or the number
: below it is +1 or -1 its value. For example,
: 1 3 2 6 8
: -9 7 1 -1 2
: 1 5 0 1 9
: In this grid, (3, 2, 1, 0, 1) is a snake sequence.
: Given a grid, find the longest snake sequences and their lengths (so there
: can be multiple snake sequences with the maximum length).
: 用dfs的话不太好算最长的sequences 用DP没思路
|
y***r
发帖数: 1845 | 9 对的。
因为只能向右向下，这就是个有向无环图。找出所有起始节点做DFS就可以。
【在 e*******s 的大作中提到】
: 把这个图做下edge vertice convert
: node value为以前edge对应的diff
: 然后把不为1的node都去掉
: 在在上面做DFS应该可以了吧
|
M*******a
发帖数: 1633 | 10 这个显然DP，时间空间复杂度都是O(n^2)
DFS太慢。 |
|
|
l*****n
发帖数: 246 | 11 翻出来个老题，最近听人说狗家店面面到了。贴个code练习一下：
public int longestSnake(int[][] matrix){
int max = 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
dp[m-1][n-1] = 1;
for(int i = m-2; i>=0; i--){
if(Math.abs(matrix[i][n-1]-matrix[i+1][n-1]==1){
dp[i][n-1] = dp[i+1][n-1]+1;
max = Math.max(max, dp[i][n-1]);
}
}
for(int j=n-2; j>=0; j--){
if(Math.abs(matrix[m-1][j]-matrix[m-1][j+1])==1){
dp[m-1][j] = dp[m-1][j+1]+1;
max = Math.max(dp[m-1][j], max);
}
}
for(int i=m-2; i>=0; i--){
for(int j=n-2; j>=0; j--){
if(Math.abs(matrix[i][j]-matrix[i][j+1])==1){
dp[i][j] = dp[i][j+1] +1;
}
if(Math.ab(matrix[i][j]-matrix[i+1][j])==1){
dp[i][j] = Math.max(dp[i][j], dp[i+1][j]+1);
}
max = Math.max(dp[i][j], max);
}
}
return max;
} |
d*****e
发帖数: 2489 | 12 mark
【在 l*****n 的大作中提到】
: 翻出来个老题，最近听人说狗家店面面到了。贴个code练习一下：
: public int longestSnake(int[][] matrix){
: int max = 0;
: int m = matrix.length;
: int n = matrix[0].length;
: int[][] dp = new int[m][n];
: dp[m-1][n-1] = 1;
: for(int i = m-2; i>=0; i--){
: if(Math.abs(matrix[i][n-1]-matrix[i+1][n-1]==1){
: dp[i][n-1] = dp[i+1][n-1]+1;
|
q*c
发帖数: 9453 | 13 dp
倒着算，从右下角开始。
【在 l***e 的大作中提到】
: You are given a grid of numbers. A snake sequence is made up of adjacent
: numbers such that for each number, the number on the right or the number
: below it is +1 or -1 its value. For example,
: 1 3 2 6 8
: -9 7 1 -1 2
: 1 5 0 1 9
: In this grid, (3, 2, 1, 0, 1) is a snake sequence.
: Given a grid, find the longest snake sequences and their lengths (so there
: can be multiple snake sequences with the maximum length).
: 用dfs的话不太好算最长的sequences 用DP没思路
|
l******9
发帖数: 26 | 14 觉得要用DFS
dp不行
10
01
【在 q*c 的大作中提到】
: dp
: 倒着算，从右下角开始。
|
V******J
发帖数: 9 | 15 正算倒算都可以。正算:dp[i][j]表示已(i,j)结束的最长sequence. |
p*****9
发帖数: 273 | |
