给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
【Leetcode542(矩阵(广度遍历解法))】答题
/** * @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中去当做一个集合,与岛屿大小问题大同小异
推荐阅读
- 17个实用的JavaScript数组和对象的方法
- js循环
- vue input 验证输入内容为小数点后两位
- 面试|前端面试——深拷贝与浅拷贝的区别
- 一些零碎代码|几十行代码,打造一款JavaScript便签系统
- 前端面试题|深拷贝和浅拷贝
- Javascript|前端js面试会问到的浅拷贝和深拷贝(以浅拷贝为例)
- Javascript|JavaScript权威指南7(四) 第十一章 JavaScript 标准库
- AliOS|新一代嵌入式UI框架 HaaS UI 使用JS在嵌入式开发炫酷前端