c********w
发帖数: 2438 | 1 Find the length of the longest non-decreasing sequence through adjacent, non
-repeating cells (including diagonals) in a rectangular grid of numbers in a
language of your choice. The solution should handle grids of arbitrary
width and height.
For example, in the following grid, one legal path (though not the longest)
that could be traced is 0->3->7->9 and its length would be 4.
8 2 4
0 7 1
3 7 9
The path can only connect adjacent locations (you could not connect 8 -> 9).
The longest possible sequence for this example would be of length 6 by
tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.
Write a method, in a language of your choice, that takes a rectangular grid
of numbers as input, and returns the length of the longest such sequence as
output.
原题在此：
http://stackoverflow.com/questions/15553218/technical-interview |
z****e
发帖数: 54598 | |
c********w
发帖数: 2438 | 3 我不知道啊
所以才问
暴力咋解
那不是超夸张么
用topological sort可以么
【在 z****e 的大作中提到】
: 这题可以野蛮暴力解
: 有复杂度要求么有？
|
s*****r
发帖数: 108 | |
a********9
发帖数: 129 | 5 请问buttom up怎么做，以及有duplicated数的情况下咋处理啊。。。
【在 s*****r 的大作中提到】
: 就是个入门 DP
|
a********m
发帖数: 15480 | 6 还是挺麻烦的。
【在 s*****r 的大作中提到】
: 就是个入门 DP
|
z****e
发帖数: 54598 | 7 dp我还没找到状态转移方程，不知道怎么个dp法
图论可解，跟leetcode上那道变态的字典题一样做
首先建图，建立所有的路径
然后从某一点开始走
广度优先的遍历
走到不能走为止，这样就是这个点出发开始走可以走的最长路径
记录下来，换下一个点
这样遍历过去，取最长点 |
a********9
发帖数: 129 | 8 我看stackoverflow说建图后用拓扑求最长路径，但要避免cycle，不知道怎么个避免法
。。
按照你那种应该是暴力法，我感觉直接在matrix上来就行，不用特意建图
DP的话应该是dp(n) = max{if neighbor
，但buttom up 不知道怎么来。。而且如果有duplicate的数，不知道怎么处理。。
求哪位大神讲解一下。。
【在 z****e 的大作中提到】
: dp我还没找到状态转移方程，不知道怎么个dp法
: 图论可解，跟leetcode上那道变态的字典题一样做
: 首先建图，建立所有的路径
: 然后从某一点开始走
: 广度优先的遍历
: 走到不能走为止，这样就是这个点出发开始走可以走的最长路径
: 记录下来，换下一个点
: 这样遍历过去，取最长点
|
z****e
发帖数: 54598 | 9 stackoverflow上那个人说了之后就再没下文了
怀疑是错的，bottom up是只有两个方向可以移动的情况下的dp
但是这题是八个方向一起上，自由移动，所以我很好奇，bottom up怎么搞
然后如果有duplicated的情况的话，要自己编hashcode
二爷的解答里面有一个就是自己编hashcode然后去干掉重复的情况
这几题都跟图有关，我一直感觉图相关问题是最难最麻烦的
【在 a********9 的大作中提到】
: 请问buttom up怎么做，以及有duplicated数的情况下咋处理啊。。。
|
t**8
发帖数: 4527 | 10 directed graph
init connect a->b if b >= a)
for each point, if there is inflow , skip it;
if it only has outflow, depth first search
non
a
)
).
【在 c********w 的大作中提到】
: Find the length of the longest non-decreasing sequence through adjacent, non
: -repeating cells (including diagonals) in a rectangular grid of numbers in a
: language of your choice. The solution should handle grids of arbitrary
: width and height.
: For example, in the following grid, one legal path (though not the longest)
: that could be traced is 0->3->7->9 and its length would be 4.
: 8 2 4
: 0 7 1
: 3 7 9
: The path can only connect adjacent locations (you could not connect 8 -> 9).
|
i****y
发帖数: 84 | 11 就top down DP吧，每经过一点就加1。也能避免所有重复运算，就是递归占了些空间吧
。 |
s******a
发帖数: 184 | 12 为什么duplicate的情况会是个问题呢？
【在 z****e 的大作中提到】
: 这题可以野蛮暴力解
: 有复杂度要求么有？
|
l*n
发帖数: 529 | 13 可以考虑从最大的数9开始，然后看次小的数8，然后看7。因为有两个7，所以先考虑跟
9挨着的7。照此继续。 |
