剑指offer 矩阵中的路径

思想:标准的回溯法
实现:

  • 使用hash表标记元素是否已经被访问
  • 使用全局变量以及在函数内定义函数尽量减少代码量
class Solution_hash:
    def hasPath(self, matrix, rows, cols, path):
        if not matrix or cols < 1 or rows < 1 or not path:
            return False

        self.hash = {}

        def DFS(i, j, index):
            if check(i, j, index):
                self.hash[(i, j)] = 1  # 标记当前节点已经被访问
                if index == len(path) - 1: return True
                flag = DFS(i + 1, j, index + 1) or DFS(i, j + 1, index + 1) or \
                       DFS(i - 1, j, index + 1) or DFS(i, j - 1, index + 1)
                self.hash.pop((i, j))  # 当前节点的后续节点都没有找到合适的路径 释放点当前节点 允许再次访问
                return flag
            return False

        def check(i, j, index):  # 对于当前节点的合法性进行判断
            return 0 <= i < rows and 0 <= j < cols and (i, j) not in self.hash and matrix[i * cols + j] == path[index]

        for i in range(rows):
            for j in range(cols):
                if DFS(i, j, 0): return True
        return False
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 17:13
想去,但是听说加班强度实在难崩,所以拒绝了,现在有点心梗对面hr感觉也是实习生,打电话的时候怪紧张的,但是感觉人很好嘞
水中水之下水道的鼠鼠:哥们这不先去体验一下,不行再跑呗,大不了混个实习经历(有更好的转正offer就当我没说)
点赞 评论 收藏
分享
asdasdasda...:19岁,不容易啊可能升个本会好点,现在学历歧视太严重了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务