V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
darkTianTian
V2EX  ›  算法

牛客网中《剑指 offer》矩阵中的路径一题 TestCase 不全。

  •  
  •   darkTianTian · 2019-03-06 00:37:56 +08:00 · 2816 次点击
    这是一个创建于 2068 天前的主题,其中的信息可能已经有所发展或是发生改变。

    原题在这里:矩阵中的路径

    我个人一般喜欢在 LeetCode 上刷题,不过有时候《剑指 Offer 》的题那里没有,会去牛客网上做。 之前就发现这道题在牛客网上测试用例不全,以为会修复,没想到几个月过去了,还是这样。把问题发到讨论区也没人理,也找不到合适的反馈入口。

    这道题是用 Python 写的,排行榜上 Python 的大部分答案,我都认为是错的。

    在一个特殊的 TestCase 下: matrix = 'ABEESFCSADME', rows=3, cols=4, path='SEE' 排行榜中大部分的答案都输出了错误的结果False,正确应该是True

    ABEE SFCS ADME

    错误的答案都是这么写的,在 if 条件后直接 return 了,那么在四个方向判断中,如果先向下走,会导致提前 return False,而不会再向上延伸。

    # -*- coding:utf-8 -*-
    class Solution:
        def hasPath(self, matrix, rows, cols, path):
            # write code here
            for i in range(rows):
                for j in range(cols):
                    if matrix[i*cols+j] == path[0]:
                        if self.find(list(matrix),rows,cols,path[1:],i,j):
                            return True
            return False
        def find(self,matrix,rows,cols,path,i,j):
            if not path:
                return True
            matrix[i*cols+j]='0'
            if j+1<cols and matrix[i*cols+j+1]==path[0]:
                return self.find(matrix,rows,cols,path[1:],i,j+1)
            elif j-1>=0 and matrix[i*cols+j-1]==path[0]:
                return self.find(matrix,rows,cols,path[1:],i,j-1)
            elif i+1<rows and matrix[(i+1)*cols+j]==path[0]:
                return self.find(matrix,rows,cols,path[1:],i+1,j)
            elif i-1>=0 and matrix[(i-1)*cols+j]==path[0]:
                return self.find(matrix,rows,cols,path[1:],i-1,j)
            else:
                return False
    

    我觉得正确的解法应该是这样,应该保留四个方向的结果做或运算。

    def hasPath(matrix, rows, cols, path):
        # write code here
        for i in range(rows):
            for j in range(cols):
                if matrix[i*cols + j] == path[0]:
                    if spread(list(matrix), rows, cols, path[1:], i, j):
                        return True
        return False
    
    def spread(matrix, rows, cols, path, i, j):
        if not path:
            return True
        matrix[i*cols + j] = '-'
        up, down, left, right = False, False, False, False
        if j + 1 < cols and matrix[i * cols + j + 1] == path[0]:
            down = spread(matrix, rows, cols, path[1:], i, j + 1)
        if j - 1 >= 0 and matrix[i * cols + j - 1] == path[0]:
            left = spread(matrix, rows, cols, path[1:], i, j - 1)
        if i + 1 < rows and matrix[(i + 1) * cols + j] == path[0]:
            right = spread(matrix, rows, cols, path[1:], i + 1, j)
        if i - 1 >= 0 and matrix[(i - 1) * cols + j] == path[0]:
            up = spread(matrix, rows, cols, path[1:], i - 1, j)
        return up or down or left or right
    

    上面两个代码均能通过牛客网的全部测试用例。而输出结果却不一致,我还是确信自己的写法是正确的。 有刷过此题的 V 友,或者算法大佬帮忙解答一下吗?就是想证明一下自己没有想错。

    6 条回复    2019-03-24 14:51:13 +08:00
    doujiang
        1
    doujiang  
       2019-03-11 19:51:44 +08:00
    ```
    def spread(matrix, rows, cols, path, i, j):
    if not path:
    return True
    tmp = matrix[i*cols + j]
    matrix[i*cols + j] = '-'
    ****
    matrix[i*cols + j] = tmp
    return up or down or left or right
    ```
    测试样例确实弱,应该回溯;另外,返回结果之前,应该恢复`matrix[i*cols + j]`中的内容吧?
    darkTianTian
        2
    darkTianTian  
    OP
       2019-03-11 22:48:44 +08:00
    @doujiang 我这里其实没有改原参数`matrix`,在主循环中都使用了`list(matrix)`,当然,这样空间复杂度会稍高。
    doujiang
        3
    doujiang  
       2019-03-11 23:39:27 +08:00
    @darkTianTian 令 M = list(matrix),查找的字符串为`abcd`,那么匹配到 ab 之后,搜索 b 的方位是右左上下,假设右不匹配 c 返回 False,此时 b 的右边会被修改为'-',但是返回上一层查找 b 的左时,右边应该恢复原状。
    darkTianTian
        4
    darkTianTian  
    OP
       2019-03-23 16:01:49 +08:00
    @doujiang 谢谢,我一直以为这么写是对的,其实根本没有恢复。
    doujiang
        5
    doujiang  
       2019-03-24 13:18:46 +08:00
    @darkTianTian 同学给我看过牛客网的一些题目,感觉它数据很弱,leetcode 更靠谱一些
    darkTianTian
        6
    darkTianTian  
    OP
       2019-03-24 14:51:13 +08:00
    @doujiang 嗯,确实差很多,我在 LeetCode 上找到这题了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2879 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 14:24 · PVG 22:24 · LAX 07:24 · JFK 10:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.