01 Matrix-LeetCode#542

542.01 Matrix

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.
Example 1: 
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2: 
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

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.

思路:从matrix[0][0]开始判断,新建一个整型矩阵res[i][j]

  • 如果matrix[i][j] == 0,res[i][j] = 0
  • 如果matrix[i][j] == 1, res[i][j]去比较左边(res[i][j – 1])与上边(res[i – 1][j]),取最小值。

还需要从matrix[matrix.length – 1][matrix[0].length – 1]开始,比较右边(res[i][j + 1])与下边(res[i + 1][j])取最小值,再与自身比较取最小值,就是距离最近0的距离。
代码如下:

public class ZeroOneMatrix {
    public int[][] updateMatrix(int[][] matrix) {
        int[][] res = new int[matrix.length][matrix[0].length];
        int x = matrix[0].length;
        int y = matrix.length;
        int max = matrix.length * matrix[0].length;
        for (int i = 0; i < y; i++) {
            for (int j = 0; j < x; j++) {
                if (matrix[i][j] == 0) {
                    res[i][j] = 0;
                } else {
                    int topCell = i > 0 ? res[i - 1][j] : max;
                    int leftCell = j > 0 ? res[i][j - 1] : max;
                    res[i][j] = Math.min(topCell, leftCell) + 1;
                }
            }
        }
        for (int i = y - 1; i >= 0; i--) {
            for (int j = x - 1; j >= 0; j--) {
                if (res[i][j] != 0) {
                    int downCell = i < y - 1 ? res[i + 1][j] : max;
                    int rightCell = j < x - 1 ? res[i][j + 1] : max;
                    res[i][j] = Math.min(Math.min(downCell, rightCell) + 1, res[i][j]);
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        ZeroOneMatrix zeroOneMatrix = new ZeroOneMatrix();
        int[][] matrix = {{0}, {0}, {0}, {0}, {0}};
        zeroOneMatrix.updateMatrix(matrix);
    }
}
文章已创建 112

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部