我最近在技术面试中被问到了这个问题.这是我的解决方案.http://pastebin.com/JMVHcfRq我犯了错误还是有更好的解决方案？
通过您选择的语言中矩形数字网格中相邻的非重复单元格(包括对角线)查找最长非递减序列的长度.解决方案应该处理任意宽度和高度的网格.
例如,在以下网格中,可以跟踪的一条合法路径(尽管不是最长)是0-> 3-> 7-> 9,其长度为4.
8 2 4
0 7 1
3 7 9
路径只能连接相邻的位置(你无法连接8 - > 9).通过描述路径0-> 2-> 4-> 7-> 7-> 9或1-> 2-> 4-> 7-> 7-> 8,该实例的最长可能序列的长度为6.
用您选择的语言编写一个方法,该方法采用矩形的数字网格作为输入,并返回最长的序列作为输出的长度.
您可以使用有向图来建模您的问题:
如果两个单元C i,j,C k,m相邻且C i,j <C k,m ,则每个单元在图中是顶点,并且存在来自C i,j →C k,m的边.
现在你的问题是在这个图中找到最长的路径,但是这个图是Directed非循环图,因为问题说矩阵中没有重复的数字,"<"关系是反对称的.所以你的问题减少到找到有向无环图中最长的路径,这很容易通过首先进行拓扑排序然后找到最长的路径.例如看到这个.
更新: 乍一看我认为不可能有平等邻居但现在我看到是可能的,在上面的图形结构中我们应该替换<with <=然后确定图形不是非循环但仍然问题等于找到最长路径图形.
P.S1:如果我有这个最长路径问题的任何多项式答案,我会把它带到这里,但可能是通过这种问题分类更容易搜索它.
P.S2:正如评论中提到的mbeckish,最长的路径问题是一般图中的NP-Hard,但我认为在这种特殊情况下可以用P求解,但我现在没有精确的算法.
P.S3:我对它进行了一些研究,我看到,网格图中的哈密顿路径是NP-Complete,所以看起来你的问题也是NP-Complete(我现在没有减少但是它们非常接近每个其他).