关于leetcode:leetcode-542-01-Matrix-01-矩阵中等

一、题目粗心

标签: 动静布局

https://leetcode.cn/problems/01-matrix

给定一个由 0 和 1 组成的矩阵 mat，请输入一个大小雷同的矩阵，其中每一个格子是 mat 中对应地位元素到最近的 0 的间隔。

两个相邻元素间的间隔为 1。
示例 1：

输出：mat = [[0,0,0],[0,1,0],[0,0,0]]
输入：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输出：mat = [[0,0,0],[0,1,0],[1,1,1]]
输入：[[0,0,0],[0,1,0],[1,2,1]]

提醒：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mati is either 0 or 1.

• mat 中至多有一个 0 

  二、解题思路

  判断应用动静布局思路解决问题，先定义一个数组 dp[][] 来，找到状态转移方程式。本题须要从左上开始搜寻一次，右下开始搜寻一次。

  三、解题办法

  3.1 Java 实现

  public class Solution {public int[][] updateMatrix(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] dp = new int[n][m];
        // mat[i][j] == 1, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i+1][j], dp[i][j+1])
        // mat[i][j] == 0, dp[i][j] = 0
        // 将 dp 中的值置为最大
        for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {dp[i][j] = Integer.MAX_VALUE - 1;
            }
        }
        for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (mat[i][j] == 0) {dp[i][j] = 0;
                } else {if (j > 0) {dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                    }
                    if (i > 0) {dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
                    }
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {for (int j = m - 1; j >= 0; j--) {if (mat[i][j] != 0) {if (j < m - 1) {dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
                    }
                    if (i < n - 1) {dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
                    }
                }
            }
        }
  
        return dp;
    }
  }

  四、总结小记

• 2022/6/19 夏至未到，温度曾经到了；波及到数组问题行列老是搞混