By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、01矩阵

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

两个相邻元素间的距离为 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.1、解题思路

四面八方走一趟

1.2、算法

public int[][] updateMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = matrix[i][j] == 0 ? 0 : 10000;
        }
    }
	
    //左上角和左下角的的是又 其他方向遍历的时候截关
    // 从左上角开始
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i - 1 >= 0) {
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
            }
            if (j - 1 >= 0) {
                dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
            }
        }
    }
    // 从右下角开始
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (i + 1 < m) {
                dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
            }
            if (j + 1 < n) {
                dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
            }
        }
    }
    return dp;
}

1.3、测试

@Test
public void test() {
    int[][] matrix = {
        {0, 0, 0},
        {0, 1, 0},
        {1, 1, 1}
    };
    updateMatrix(matrix);
}

​

ContactAuthor