C++ LeetCode542矩阵示例详解

目录
  • LeetCode  542.01 矩阵
  • 方法一：广度优先搜索
  • AC代码
    • C++

LeetCode  542.01 矩阵

力扣题目链接：leetcode.cn/problems/01…

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

两个相邻元素间的距离为 1 。

示例 1：

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

示例 2：

输入：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

方法一：广度优先搜索

首先遍历原始矩阵，找到所有的0，将其位置入队。

接着在队列不为空时，不断出队一个位置，并判断这个位置的上下左右是否被遍历过。

如果还没有被遍历过，那么就将新的位置入队。并将地图中新的位置的值修改为“出队位置的值 + 1”

原理：

所有的原始的0最终结果都是0。广度优先搜索就是在所有的“0”的位置中，走一步。这一步所到的位置就是“1”步能到达的位置。同理，“1”经过一步到达的位置就是“2”。最先到达的就是步数最少的。

  • 时间复杂度O(nm)
  • 空间复杂度O(nm)

AC代码

C++

typedef pair<int, int> pii;
const int direcitons[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        queue<pii> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!mat[i][j]) {
                    visited[i][j] = true;
                    q.push({i, j});
                }
            }
        }
        while (q.size()) {
            pii thisNode = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int tx = thisNode.first + direcitons[d][0];
                int ty = thisNode.second + direcitons[d][1];
                if (tx >= 0 && tx < n && ty >= 0 && ty < m) {
                    if (!visited[tx][ty]) {
                        visited[tx][ty] = true;
                        mat[tx][ty] = mat[thisNode.first][thisNode.second] + 1;
                        q.push({tx, ty});
                    }
                }
            }
        }
        return mat;
    }
};

以上就是C++ LeetCode542矩阵示例详解的详细内容，更多关于C++ LeetCode542矩阵的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++ LeetCode1827题解最少操作使数组递增

    目录 LeetCode1827.最少操作使数组递增 方法一:遍历 AC代码 C++ LeetCode1827.最少操作使数组递增 力扣题目链接:leetcode.cn/problems/mi… 给你一个整数数组 nums (下标从 0 开始).每一次操作中,你可以选择数组中一个元素,并将它增加 1 . 比方说,如果 nums = [1,2,3] ,你可以选择增加 nums[1] 得到 nums = [1,3,3] . 请你返回使 nums 严格递增 的 最少 操作次数. 我们称数组 nums 是

  • C++ LeetCode1805字符串不同整数数目

    目录 LeetCode 1805.字符串中不同整数的数目 方法一:遍历拆分 AC代码 C++ LeetCode 1805.字符串中不同整数的数目 力扣题目链接:leetcode.cn/problems/nu… 给你一个字符串 word ,该字符串由数字和小写英文字母组成. 请你用空格替换每个不是数字的字符.例如,"a123bc34d8ef34" 将会变成 " 123  34 8  34" .注意,剩下的这些整数为(相邻彼此至少有一个空格隔开):"123&q

  • C++ LeetCode1781题解所有子字符串美丽值之和

    目录 LeetCode 1781.所有子字符串美丽值之和 方法一:前缀和 AC代码 C++ 方法二:边遍历边计算 AC代码 C++ LeetCode 1781.所有子字符串美丽值之和 力扣题目链接:leetcode.cn/problems/su… 一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差. 比方说,"abaacc" 的美丽值为 3 - 1 = 2 . 给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和. 示例 1: 输入:s = &quo

  • C++ LeetCode1812判断国际象棋棋盘格子颜色

    目录 1812.判断国际象棋棋盘中一个格子的颜色 方法一:取模 AC代码 C++ 方法二:基于方法一的小改进 AC代码 C++ 1812.判断国际象棋棋盘中一个格子的颜色 力扣题目链接:leetcode.cn/problems/de… 给你一个坐标 coordinates ,它是一个字符串,表示国际象棋棋盘中一个格子的坐标.下图是国际象棋棋盘示意图. 如果所给格子的颜色是白色,请你返回 true,如果是黑色,请返回 false . 给定坐标一定代表国际象棋棋盘上一个存在的格子.坐标第一个字符是字

  • C++ LeetCode543题解二叉树直径

    目录 LeetCode 543.二叉树的直径 方法一:深度优先搜索求二叉树的深度 AC代码 C++ LeetCode 543.二叉树的直径 力扣题目链接:leetcode.cn/problems/di… 给定一棵二叉树,你需要计算它的直径长度.一棵二叉树的直径长度是任意两个结点路径长度中的最大值.这条路径可能穿过也可能不穿过根结点. 示例 :给定二叉树 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]. 注意:两结点之间的路径长度是以它们之间边的数目表示. 方法一:深度优

  • C++ LeetCode300最长递增子序列

    目录 LeetCode 300.最长递增子序列 方法一:动态规划 AC代码 C++ LeetCode 300.最长递增子序列 力扣题目链接:leetcode.cn/problems/lo… 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度. 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序.例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列. 示例 1: 输入:nums = [10,9,2,5,3,7,101,18]输出:4

  • C++ LeetCode1780判断数字是否可以表示成三的幂的和

    目录 LeetCode 1780.判断一个数字是否可以表示成三的幂的和 方法一:二进制枚举 题目分析 解题思路 复杂度分析 AC代码 C++ 方法二:进制转换 AC代码 C++ LeetCode 1780.判断一个数字是否可以表示成三的幂的和 力扣题目链接:leetcode.cn/problems/ch… 给你一个整数 n ,如果你可以将 n 表示成若干个不同的三的幂之和,请你返回 true ,否则请返回 false . 对于一个整数 y ,如果存在整数 x 满足 y == 3x ,我们称这个整

  • C++ LeetCode1775通过最少操作次数使数组和相等

    目录 LeetCode1775.通过最少操作次数使数组的和相等 方法一:贪心 + 计数 AC代码 C++ LeetCode1775.通过最少操作次数使数组的和相等 力扣题目链接:leetcode.cn/problems/eq… 给你两个长度可能不等的整数数组 nums1 和 nums2 .两个数组中的所有值都在 1 到 6 之间(包含 1 和 6). 每次操作中,你可以选择 任意 数组中的任意一个整数,将它变成 1 到 6 之间 任意 的值(包含 1 和 6). 请你返回使 nums1 中所有数

  • C++ LeetCode542矩阵示例详解

    目录 LeetCode  542.01 矩阵 方法一:广度优先搜索 AC代码 C++ LeetCode  542.01 矩阵 力扣题目链接:leetcode.cn/problems/01… 给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离. 两个相邻元素间的距离为 1 . 示例 1: 输入:mat = [[0,0,0],[0,1,0],[0,0,0]]输出:[[0,0,0],[0,1,0],[0,0,0]] 示例

  • C语言编程题杨氏矩阵算法快速上手示例详解

    目录 题目概要 一.解题思路 二.具体代码 题目概要 有一个数字矩阵,矩阵的每行从左到右都是递增的,矩阵从上到下都是递增的,请编写程序在这样的矩阵中查找某个数字是否存在? 一.解题思路 对于查找一个数组中元素是否存在,很多同学第一想法就是从头到尾遍历一遍.这样的想法优点是代码简单且无脑容易上手,但是这样的缺点也很明显,比如是m *n的数组,你从头到尾遍历,最坏情况要找m *n次.题目给的相关条件比如从左向右递增,从上向下递增你也完全没有使用,这样的暴力求解显然不是我们想看到的 我们来介绍一种方法

  • 基于Python Numpy的数组array和矩阵matrix详解

    NumPy的主要对象是同种元素的多维数组.这是一个所有的元素都是一种类型.通过一个正整数元组索引的元素表格(通常是元素是数字). 在NumPy中维度(dimensions)叫做轴(axes),轴的个数叫做秩(rank,但是和线性代数中的秩不是一样的,在用python求线代中的秩中,我们用numpy包中的linalg.matrix_rank方法计算矩阵的秩,例子如下). 结果是: 线性代数中秩的定义:设在矩阵A中有一个不等于0的r阶子式D,且所有r+1阶子式(如果存在的话)全等于0,那末D称为矩阵

  • Python数学建模StatsModels统计回归之线性回归示例详解

    Python数学建模StatsModels统计回归之线性回归示例详解

    目录 1.背景知识 1.1 插值.拟合.回归和预测 1.2 线性回归 2.Statsmodels 进行线性回归 2.1 导入工具包 2.2 导入样本数据 2.3 建模与拟合 2.4 拟合和统计结果的输出 3.一元线性回归 3.1 一元线性回归 Python 程序: 3.2 一元线性回归 程序运行结果: 4.多元线性回归 4.1 多元线性回归 Python 程序: 4.2 多元线性回归 程序运行结果: 5.附录:回归结果详细说明 1.背景知识 1.1 插值.拟合.回归和预测 插值.拟合.回归和预测

  • java图搜索算法之图的对象化描述示例详解

    java图搜索算法之图的对象化描述示例详解

    目录 一.前言 二.什么是图 三.怎么存储一个图的结构 1.邻接矩阵 2.邻接表 3.图对象化表示 四.图的作用 你好,我是小黄,一名独角兽企业的Java开发工程师. 校招收获数十个offer,年薪均20W~40W. 感谢茫茫人海中我们能够相遇, 俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习, 希望优秀的你可以和我一起学习,一起努力,实现属于自己的梦想. 一.前言 对于图来说,我一直以来都似懂非懂 懂的是图的含义,不懂的是图具体的实现 对于当前各大厂面试的图题,不外乎以下几

  • 人工智能学习Pytorch教程Tensor基本操作示例详解

    人工智能学习Pytorch教程Tensor基本操作示例详解

    目录 一.tensor的创建 1.使用tensor 2.使用Tensor 3.随机初始化 4.其他数据生成 ①torch.full ②torch.arange ③linspace和logspace ④ones, zeros, eye ⑤torch.randperm 二.tensor的索引与切片 1.索引与切片使用方法 ①index_select ②... ③mask 三.tensor维度的变换 1.维度变换 ①torch.view ②squeeze/unsqueeze ③expand,repea

  • 人工智能学习Pytorch张量数据类型示例详解

    人工智能学习Pytorch张量数据类型示例详解

    目录 1.python 和 pytorch的数据类型区别 2.张量 ①一维张量 ②二维张量 ③3维张量 ④4维张量 1.python 和 pytorch的数据类型区别 在PyTorch中无法展示字符串,因此表达字符串,需要将其转换成编码的类型,比如one_hot,word2vec等. 2.张量 在python中,会有标量,向量,矩阵等的区分.但在PyTorch中,这些统称为张量tensor,只是维度不同而已. 标量就是0维张量,只有一个数字,没有维度. 向量就是1维张量,是有顺序的数字,但没有"

  • python opencv图像处理基本操作示例详解

    python opencv图像处理基本操作示例详解

    目录 1.图像基本操作 ①读取图像 ②显示图像 ③视频读取 ④图像截取 ⑤颜色通道提取及还原 ⑥边界填充 ⑦数值计算 ⑧图像融合 2.阈值与平滑处理 ①设定阈值并对图像处理 ②图像平滑-均值滤波 ③图像平滑-方框滤波 ④图像平滑-高斯滤波 ⑤图像平滑-中值滤波 3.图像的形态学处理 ①腐蚀操作 ②膨胀操作 ③开运算和闭运算 4.图像梯度处理 ①梯度运算 ②礼帽与黑帽 ③图像的梯度处理 5.边缘检测 ①Canny边缘检测 1.图像基本操作 ①读取图像 ②显示图像 该函数中,name是显示窗口的名字

  • python计算机视觉opencv卡号识别示例详解

    python计算机视觉opencv卡号识别示例详解

    目录 一.模板预处理 1.将模板设置为二值图 2.检测模板的轮廓 3.对模板轮廓排序,并将数字和轮廓一一对应,以字典存储 4.备注 二.图片预处理 1.初始化卷积核 2.图片预处理第一部分 3.图像预处理第二部分 三.轮廓处理 1.大轮廓过滤 2.小轮廓分割 模板图片如下: 需识别的图片如下: 一.模板预处理 1.将模板设置为二值图 2.检测模板的轮廓 3.对模板轮廓排序,并将数字和轮廓一一对应,以字典存储 排序的函数如下: 排序并存储: 4.备注 ①每一个数字对应的是二值图截出来的那个数字图的

  • python编程开发时间序列calendar模块示例详解

    python编程开发时间序列calendar模块示例详解

    目录 calendar模块 设置每周第一天-setfirstweekday 1.默认情况:礼拜一是第一天 2.设置任意一天 是否闰年-isleap 年份间的闰年数-leapdays(y1, y2) 星期几-weekday(year, month, day) monthrange(year, month) 月的日历矩阵-monthcalendar(year, month) 月的日历-prmonth(year, month, w, l) 年的日历-calendar.calendar(year) 格式

随机推荐