leetcode 542. 01 矩阵

这篇具有很好参考价值的文章主要介绍了leetcode 542. 01 矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

示例 1:
leetcode 542. 01 矩阵,广度/深度遍历,LeetCode,剑指offer,leetcode,矩阵,算法

输入:mat = [[0,0,0],[0,1,0],[0,0,0]]
输出:[[0,0,0],[0,1,0],[0,0,0]]

示例 2:
leetcode 542. 01 矩阵,广度/深度遍历,LeetCode,剑指offer,leetcode,矩阵,算法

输入:mat = [[0,0,0],[0,1,0],[1,1,1]]
输出:[[0,0,0],[0,1,0],[1,2,1]]

提示:
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0
题目链接:leetcode 542

思路:
可以采用广度遍历的方式来做,先把所有为 0 的元素进队列,然后依次计算出其临近的元素的距离,依次直到把矩阵中所有的元素的距离都计算完。

class Solution:
    def __init__(self):
        self.INT_MAX = 100000

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        res = [[self.INT_MAX for j in range(cols)] for i in range(rows)]
        visited = [[0 for j in range(cols)] for i in range(rows)]
        ss = []
        for i in range(rows):
            for j in range(cols):
                if mat[i][j] == 0:
                    res[i][j] = 0
                    visited[i][j] = 1
                    ss.append((i, j))
        while len(ss) > 0:
            r, c = ss.pop(0)
            if r>0 and visited[r-1][c] == 0:
                ss.append((r-1, c))
                visited[r-1][c] = 1
                res[r-1][c] = min(res[r-1][c], res[r][c]+1)
            if r+1<rows and visited[r+1][c] == 0:
                ss.append((r+1, c))
                visited[r+1][c] = 1
                res[r+1][c] = min(res[r+1][c], res[r][c]+1)
            if c>0 and visited[r][c-1] == 0:
                ss.append((r, c-1))
                visited[r][c-1] = 1
                res[r][c-1] = min(res[r][c-1], res[r][c]+1)
            if c+1<cols and visited[r][c+1] == 0:
                ss.append((r, c+1))
                visited[r][c+1] = 1
                res[r][c+1] = min(res[r][c+1], res[r][c]+1)
        return res

方法二,采用动态规划来做
leetcode 542. 01 矩阵,广度/深度遍历,LeetCode,剑指offer,leetcode,矩阵,算法文章来源地址https://www.toymoban.com/news/detail-595594.html

class Solution:
    def __init__(self):
        self.INT_MAX = 100000

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        res = [[self.INT_MAX for j in range(cols)] for i in range(rows)]
        visited = [[0 for j in range(cols)] for i in range(rows)]
        ss = []
        for i in range(rows):
            for j in range(cols):
                if mat[i][j] == 0:
                    res[i][j] = 0
        ### from 左上
        for i in range(rows):
            for j in range(cols):
                if i-1>=0:
                    res[i][j] = min(res[i-1][j]+1, res[i][j])
                if j-1>=0:
                    res[i][j] = min(res[i][j-1]+1, res[i][j])
        ### from 右上
        for i in range(rows):
            for j in range(cols-1, -1, -1):
                if i-1>=0:
                    res[i][j] = min(res[i-1][j]+1, res[i][j])
                if j+1<cols:
                    res[i][j] = min(res[i][j+1]+1, res[i][j])
        
        ## from 左下
        for i in range(rows-1, -1, -1):
            for j in range(cols):
                if i+1<rows:
                    res[i][j] = min(res[i+1][j]+1, res[i][j])
                if j-1>=0:
                    res[i][j] = min(res[i][j-1]+1, res[i][j]) 
        
        ## from 右下
        for i in range(rows-1, -1, -1):
            for j in range(cols-1, -1, -1):
                if i+1<rows:
                    res[i][j] = min(res[i+1][j]+1, res[i][j])
                if j+1<cols:
                    res[i][j] = min(res[i][j+1]+1, res[i][j])
        return res

到了这里,关于leetcode 542. 01 矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每天一道leetcode:剑指 Offer 34. 二叉树中和为某一值的路径(中等&图论&深度优先遍历&递归)

    给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 树中节点总数在范围 [0, 5000] 内 -1000 = Node.val = 1000 -1000 = targetSum = 1000 使用递归深度优先遍历,使用前序遍历,在遍历途

    2024年02月12日
    浏览(49)
  • 剑指 Offer 12. 矩阵中的路径 / LeetCode 79. 单词搜索(深度优先搜索)

    链接:剑指 Offer 12. 矩阵中的路径;LeetCode 79. 单词搜索 难度:中等 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相

    2024年02月02日
    浏览(42)
  • C++实现图—邻接矩阵,邻接表,深度遍历,广度遍历

    目录 1.图的基本概念 2.图的存储结构 2.1邻接矩阵 2.2 邻接表 3.图的遍历 3.1广度优先遍历 3.2图的深度遍历  总结: 图是由顶点集合以及顶点之间的关系组成的一种数据结构:G = (V,E),其中顶点集合V={x|x属于某个对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Pa

    2024年02月06日
    浏览(56)
  • 图用邻接矩阵实现,深度优先遍历和广度优先遍历

    邻接矩阵的结构体 邻接矩阵图的建立         图的建立有多种实现方式,我这里是从键盘输入顶点数,边条数,并从键盘输入边的关系 图是带有权值的,并且把环的权值赋值为0,两个顶点没有边权值为32767。 查找顶点v,并且返回v的相关信息         通过循环去找顶点,如

    2024年02月04日
    浏览(47)
  • C++构造无向图,邻接矩阵,深度优先遍历,广度优先遍历

    目录 定义无向图邻接矩阵 构造无向图 打印邻接矩阵 无向图邻接矩阵深度优先遍历(DFS) 无向图邻接矩阵广度优先遍历(BFS) 测试  完整代码 定义无向图邻接矩阵 构造无向图 1、输入总顶点数和总边数 2、依次输入顶点信息存入顶点表 3、 初始化邻接矩阵,使每个权值初始化

    2024年02月06日
    浏览(83)
  • 蛮力算法之深度优先遍历和广度优先遍历——图的深度优先遍历和广度优先遍历,附带案例:迷宫问题及矩阵中传染性传播问题

    这两种搜索方法本质上都是基于蛮力法思路 这两种搜索方法对有向图和无向图都适用 1.1 邻接矩阵 邻接矩阵示意图: 1.2 邻接表 注意:边结点代表的是图中的边,而并非图中的结点;头结点才表示图中的结点;头结点身后所连接的为边结点 邻接表示意图:(一般默认为出边

    2024年02月05日
    浏览(66)
  • 每天一道leetcode:127. 单词接龙(图论&困难&建图&广度优先遍历)

    字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - ... - sk : 每一对相邻的单词只差一个字母。 对于 1 = i = k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。 sk == endWord 给你两个单词 beginWord 和 endWord 和一个字典

    2024年02月12日
    浏览(36)
  • 每天一道leetcode:1466. 重新规划路线(图论&中等&广度优先遍历)

    n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。 路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条

    2024年02月12日
    浏览(50)
  • 每天一道leetcode:433. 最小基因变化(图论&中等&广度优先遍历)

    基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 \\\'A\\\' 、 \\\'C\\\' 、 \\\'G\\\' 和 \\\'T\\\' 之一。 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如, \\\"AACCGGTT\\\" -- \\\"AACCGGTA\\\" 就是一次基因变化。

    2024年02月12日
    浏览(41)
  • 每天一道leetcode:934. 最短的桥(图论&中等&广度优先遍历)

    给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地, 0 表示水域。 岛 是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。 grid 中 恰好存在两座岛 。 你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成 一座岛 。 返回必须翻转的 0 的最小数

    2024年02月12日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包