专栏首页爱写BugLeetcode 542:01 矩阵 01 Matrix

Leetcode 542:01 矩阵 01 Matrix

题目:

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。

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

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 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

注意:

  1. 给定矩阵的元素个数不超过 10000。
  2. 给定矩阵中至少有一个元素是 0。
  3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

Note:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.

解题思路:

关键字:最近、距离。那肯定是广度优先搜索。类似之前的文章 岛屿数量:https://mp.weixin.qq.com/s/BrlMzXTtZWdB7hRfCKNMoQ

将这个问题转化成图,那就是求每个节点 1 到节点 0 最短的路径是多少。从某个节点开始,上下左右向外扩展,每次扩展一圈距离累加1,如:

输入:
1 1 1
0 1 0
0 0 0

转化成图(Graph),每种颜色代表一个层级:

这就变成了求某个节点到某个节点的深度了。

所以这道题有两种思路:

  • 以节点1为根节点,求该节点到节点0之间的深度
  • 以节点0为根节点,遇到最近的节点1路径计为1,再次以记录为1的节点为根节点继续向内遍历,遇到原节点1再次累加1并得到路径2,以此类推。。。

两种方法各有优劣,

以0节点为根节点解题,要么开辟一个新的二维数组以记录路径,要么先遍历一遍将所有的节点1的值改为不可能和路径大小重复的值。

以1节点为根节点,那么就要做一些多余的重复遍历。

以0为根节点:

逻辑顺序:

以输入下列二维数组为例:

1 1 1
0 1 1
0 0 1

先把原节点值为1 的节点改为M (路径值不可能达到的值,该题中大于10000即可)

先侵染0节点附近的M节点,0节点加1之后得到1节点

再侵染1节点附近的M节点,1节点加1之后得到2节点

……

Java:

class Solution {

    public int[][] updateMatrix(int[][] matrix) {
        int row = matrix.length, column = matrix[0].length;
        int[][] neighbors = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//邻居节点的索引偏移量
        Queue<int[]> queue = new LinkedList<>();//队列
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (matrix[i][j] == 0) queue.offer(new int[]{i, j});
                else matrix[i][j] = Integer.MAX_VALUE;//节点值为1的节点改为一个路径不可能达到的值
            }
        }
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            for (int i = 0; i < 4; i++) {
                //得到邻居节点索引
                int x = tmp[0] + neighbors[i][0];
                int y = tmp[1] + neighbors[i][1];
                if (x >= 0 && x < row && y >= 0 && y < column && matrix[tmp[0]][tmp[1]] < matrix[x][y]) {
                    matrix[x][y] = matrix[tmp[0]][tmp[1]] + 1;//该节点的值得到邻居节点的路径值+1
                    queue.offer(new int[]{x, y});
                }
            }
        }
        return matrix;
    }
}

Python3:

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        row, column = len(matrix), len(matrix[0])
        nerghbors = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        queue = collections.deque()
        for i in range(row):
            for j in range(column):
                if matrix[i][j] == 0:
                    queue.append((i, j))
                else:
                    matrix[i][j] = 10001

        while queue:
            x, y = queue.popleft()
            for i, j in nerghbors:
                xx = i + x
                yy = j + y
                if 0 <= xx < row and 0 <= yy < column and matrix[x][y] < matrix[xx][yy]:
                    matrix[xx][yy] = matrix[x][y] + 1
                    queue.append((xx, yy))

        return matrix

以1为根节点:

Java:

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int row = matrix.length, column = matrix[0].length;
        for (int i = 0; i < row; i++)
            for (int j = 0; j < column; j++)
                if (matrix[i][j] == 1) matrix[i][j] = bfs(matrix, i, j, row, column);
        return matrix;
    }

    private int bfs(int[][] matrix, int i, int j, int row, int column) {
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        Set<int[]> set = new HashSet<>();
        queue.add(i * column + j);//记录索引的另一种方法
        while (!queue.isEmpty()) {
            int size = queue.size();
            count += 1;
            for (int k = 0; k < size; k++) {
                int tmp = queue.poll();
                int x = tmp / column, y = tmp % column;//得到索引坐标
                //处理上下左右四个邻居节点,遇到0节点直接返回count路径值
                if (x + 1 < row && !set.contains((x + 1) * column + y)) {
                    if (matrix[x + 1][y] != 0) queue.add((x + 1) * column + y);
                    else return count;
                }
                if (x - 1 >= 0 && !set.contains((x - 1) * column + y)) {
                    if (matrix[x - 1][y] != 0) queue.add((x - 1) * column + y);
                    else return count;
                }
                if (y + 1 < column && !set.contains(x * column + y + 1)) {
                    if (matrix[x][y + 1] != 0) queue.add(x * column + y + 1);
                    else return count;
                }
                if (y - 1 >= 0 && !set.contains(x * column + y - 1)) {
                    if (matrix[x][y - 1] != 0) queue.add(x * column + y - 1);
                    else return count;
                }
            }
        }
        return count;
    }
}

Python3:

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        row, column = len(matrix), len(matrix[0])
        for i in range(row):
            for j in range(column):
                if matrix[i][j] == 1:
                    matrix[i][j] = self.bfs(i, j, matrix, row, column)

        return matrix

    def bfs(self, i: int, j: int, matrix: List[List[int]], row: int, column: int) -> int:
        queue = collections.deque()
        count = 0
        nodeset = set()
        queue.append((i, j))
        while queue:
            size = len(queue)
            count += 1
            for i in range(size):
                x, y = queue.popleft()
                if x + 1 < row and (x + 1, y) not in nodeset:
                    if matrix[x + 1][y] != 0:
                        queue.append((x + 1, y))
                    else:
                        return count
                if x - 1 >= 0 and (x - 1, y) not in nodeset:
                    if matrix[x - 1][y] != 0:
                        queue.append((x - 1, y))
                    else:
                        return count
                if y + 1 < column and (x, y + 1) not in nodeset:
                    if matrix[x][y + 1] != 0:
                        queue.append((x, y + 1))
                    else:
                        return count
                if y - 1 >= 0 and (x, y - 1) not in nodeset:
                    if matrix[x][y - 1] != 0:
                        queue.append((x, y - 1))
                    else:
                        return count
        return count

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 498:对角线遍历Diagonal Traverse(python3、java)

    给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

    爱写bug
  • Leetcode 54:Spiral Matrix 螺旋矩阵

    Given a matrix of m x n elements (m rows, n columns), return all elements of the...

    爱写bug
  • leetcode ​# 54:Spiral Matrix 螺旋矩阵

    Given a matrix of m x n elements (m rows, n columns), return all elements of the...

    爱写bug
  • Leetcode 221. Maximal Square

    Given a 2D binary matrix filled with 0's and 1's, find the largest square conta...

    triplebee
  • Leetcode 48 Rotate Image

    You are given an n x n 2D matrix representing an image. Rotate the image by 90...

    triplebee
  • Leetcode-48-Rotate-Image

    这个乍一看觉得不难,但是写的时候又不知道怎么回事,其实旋转,对于我们写程序来说,其实就是不停的调换位置,但是怎么调换是个问题。

    小二三不乌
  • 【每日算法Day 93】不用额外空间,你会旋转一个矩阵吗?

    给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。

    godweiyang
  • 【一天一大 lee】旋转图像 (难度:中等) - Day20201219

    你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

    前端小书童
  • Q221 Maximal Square

    Given a 2D binary matrix filled with 0's and 1's, find the largest square contai...

    echobingo
  • Array - 48. Rotate Image

    You are given an n x n 2D matrix representing an image.

    用户5705150

扫码关注云+社区

领取腾讯云代金券