csco not bad - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

csco not bad

csco not bad# Stock

l*e2010-05-12 07:05

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没思路

w*l2010-05-12 07:05

2 楼

e*s2010-05-12 07:05

3 楼

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没思路

m*o2010-05-12 07:05

4 楼

然后就跌了。。

【在 w****l 的大作中提到】

: .

l*e2010-05-12 07:05

5 楼

看字面应该可以

【在 e*******s 的大作中提到】

: path可以交叉重叠不

e*s2010-05-12 07:05

6 楼

那cycle怎么办

【在 l***e 的大作中提到】

: 看字面应该可以

l*e2010-05-12 07:05

7 楼

cycle不行交叉或许可以网上看的题只能从文字理解

【在 e*******s 的大作中提到】

: 那cycle怎么办

e*s2010-05-12 07:05

8 楼

把这个图做下edge vertice convert
node value为以前edge对应的diff
然后把不为1的node都去掉
在在上面做DFS应该可以了吧

【在 l***e 的大作中提到】

: cycle不行交叉或许可以网上看的题只能从文字理解

r*32010-05-12 07:05

9 楼

不能交叉吧... 只能取右边的或者下边的number

R*Z2010-05-12 07:05

10 楼

用DP的话，从右下角往左上角倒推应该可以吧

【在 l***e 的大作中提到】

y*r2010-05-12 07:05

11 楼

对的。
因为只能向右向下，这就是个有向无环图。找出所有起始节点做DFS就可以。

【在 e*******s 的大作中提到】

: 把这个图做下edge vertice convert
: node value为以前edge对应的diff
: 然后把不为1的node都去掉
: 在在上面做DFS应该可以了吧

M*a2010-05-12 07:05

12 楼

这个显然DP，时间空间复杂度都是O(n^2)
DFS太慢。

l*n2010-05-12 07:05

13 楼

翻出来个老题，最近听人说狗家店面面到了。贴个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*e2010-05-12 07:05

14 楼

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;