由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求解一道面试题 snake sequence
相关主题
(CS) 水滴的2D问题是怎么解决的?这题有沒有P解?
贴点面试题问两道amazon的面试题
G家面试题: Longest Increasing Sequence 2D matrix问几道面试题
看到个面试题,不会做……问个google面试题
请问leetcode 上那道Longest Consecutive Sequence题L 家面试题, 请大牛讲讲思路
给大家出个题目:从2d array中找sequence,返回坐标系列一道google 题,谁给翻译一下意思,多谢。
问一道面试题目问道G题(4)
别处看到的g家一个画grid的面试题请教一道 G 家 DNA edit distance的题
相关话题的讨论汇总
话题: dp话题: matrix话题: int话题: snake话题: max
进入JobHunting版参与讨论
1 (共1页)
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太慢。
相关主题
给大家出个题目:从2d array中找sequence,返回坐标系列这题有沒有P解?
问一道面试题目问两道amazon的面试题
别处看到的g家一个画grid的面试题问几道面试题
进入JobHunting版参与讨论
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
16
mark
1 (共1页)
进入JobHunting版参与讨论
相关主题
请教一道 G 家 DNA edit distance的题请问leetcode 上那道Longest Consecutive Sequence题
问一道数据结构题给大家出个题目:从2d array中找sequence,返回坐标系列
攒人品,google电话面经问一道面试题目
问一个graph题别处看到的g家一个画grid的面试题
(CS) 水滴的2D问题是怎么解决的?这题有沒有P解?
贴点面试题问两道amazon的面试题
G家面试题: Longest Increasing Sequence 2D matrix问几道面试题
看到个面试题,不会做……问个google面试题
相关话题的讨论汇总
话题: dp话题: matrix话题: int话题: snake话题: max