乐趣区

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

jiezi

一、题目粗心

标签: 动静布局

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 夏至未到，温度曾经到了；波及到数组问题行列老是搞混
退出移动版