原题在这里:矩阵中的路径
我个人一般喜欢在 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 友,或者算法大佬帮忙解答一下吗?就是想证明一下自己没有想错。
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]`中的内容吧? |
2
darkTianTian OP @doujiang 我这里其实没有改原参数`matrix`,在主循环中都使用了`list(matrix)`,当然,这样空间复杂度会稍高。
|
3
doujiang 2019-03-11 23:39:27 +08:00
@darkTianTian 令 M = list(matrix),查找的字符串为`abcd`,那么匹配到 ab 之后,搜索 b 的方位是右左上下,假设右不匹配 c 返回 False,此时 b 的右边会被修改为'-',但是返回上一层查找 b 的左时,右边应该恢复原状。
|
4
darkTianTian OP @doujiang 谢谢,我一直以为这么写是对的,其实根本没有恢复。
|
5
doujiang 2019-03-24 13:18:46 +08:00
@darkTianTian 同学给我看过牛客网的一些题目,感觉它数据很弱,leetcode 更靠谱一些
|
6
darkTianTian OP @doujiang 嗯,确实差很多,我在 LeetCode 上找到这题了。
|