Leetcode542:矩阵(广度遍历解法)

简介: Leetcode542:矩阵(广度遍历解法)

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

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

答题

/**

 * @param {number[][]} mat

 * @return {number[][]}
   */
   var updateMatrix = function(mat) {
   let map = new Array(mat.length);    // 用于输出的数组
   let quque = [];                     // 队列
    /* 给map赋初值*/
   for(let i = 0; i < mat.length; i++){
       map[i] = new Array(mat[0].length).fill(Infinity);
       for(let j = 0; j < mat[0].length; j++){
           if(mat[i][j] == 0){
               quque.push([i,j]);
               map[i][j] = 0;
           }
       }
   }
   /*遍历0周边的数,如果大于0+1,则赋值,将此推进队列,继续遍历*/
    while(quque.length > 0){
        let size = quque.length;
        for(let k = 0; k < size; k++){
            let [i,j] = quque.shift();
           

            if(i - 1 >= 0 && map[i - 1][j] > map[i][j] + 1){
                map[i - 1][j] = map[i][j] + 1;
                quque.push([i - 1,j])
            }
            if(i + 1 < map.length && map[i + 1][j] > map[i][j] + 1){
                map[i + 1][j] = map[i][j] + 1;
                quque.push([i + 1,j])
            }
            if(j - 1 >= 0 && map[i][j - 1] > map[i][j] + 1){
                map[i][j - 1] = map[i][j] + 1;
                quque.push([i,j - 1])
            }
            if(j + 1 < map[0].length && map[i][j + 1] > map[i][j] + 1){
                map[i][j + 1] = map[i][j] + 1;
                quque.push([i,j + 1])
            }
        }

    }
    return map;
   };

不像其他的,这里是需要一开始就把所有的0位置放到quque中去当做一个集合,与岛屿大小问题大同小异

相关文章
|
2月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
2月前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历
|
2月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
41 6
|
2月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
44 1
|
2月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
41 1
|
2月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
18 3
|
2月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
27 4
|
2月前
|
Python
【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
LeetCode上105号问题"从前序与中序遍历序列构造二叉树"的Python实现,通过递归方法根据前序和中序遍历序列重建二叉树。
18 3
|
2月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
20 0
【Leetcode刷题Python】73. 矩阵置零
|
2月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
66 0