20190712-01矩阵的解题思考
发布于2019-08-07 10:59 阅读(846) 评论(0) 点赞(1) 收藏(0)
01矩阵
难度分类
中等
题目描述
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
题目转载于Leetcode。
算法
- 记录Q =矩阵所有的值为0的节点
- 将值为0的节点看作已处理过的节点，记录visited = set(Q)
- 当Q不为空的时候依次从Q的左边取节点对取到的节点做以下判断：
a) 节点的上下左右领结点是否合法存在（即是否越界）
b) 如果上下左右节点存在，判断其是否已被更新
c) 如果即存在又没有被更新，则更新其节点值为当前取到的节点值+1，即任何0节点上下左右的领结点到0的距离为1，更新后将更新后的节点加入Q和Visted里面。加入Q里面是为了一层一层的更新远端节点的距离，加入Visited是为了以防后续被更新
代码
def updateMatrix(matrix): matrix_length = len(matrix) if matrix_length < 1: return matrix row_length = len(matrix[0]) queue = [] visited = set() for i in range(matrix_length): for j in range(row_length): if matrix[i][j] == 0: queue.append((i, j))#找到所有的0结点 visited.add((i, j))#将0节点看作已经被更新的节点visited while queue: i, j = queue.pop(0) for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]: # 下上右左4个节点，0的上下左右到0的距离都为1 if 0 <= x < matrix_length and 0 <= y < row_length and (x, y) not in visited: # x,y范围区间在矩阵边界值以内,且未被更新 matrix[x][y] = matrix[i][j] + 1 visited.add((x, y)) queue.append((x, y)) return matrix
所属网站分类: 技术文章 > 博客
作者：追梦骚年
链接：https://www.pythonheidong.com/blog/article/10107/ad95c3f92809816c0921/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力