Java实现 LeetCode 542 01 矩阵(暴力大法,正反便利)
2023-09-14 08:58:04 时间
542. 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
注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
class Solution {
private int row;
private int col;
private int[][] vector = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
/**
* DP(两次遍历,可 AC)
*/
public int[][] updateMatrix(int[][] matrix) {
row = matrix.length;
col = matrix[0].length;
// 第一次遍历,正向遍历,根据相邻左元素和上元素得出当前元素的对应结果
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 1) {
matrix[i][j] = row + col;
}
if (i > 0) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i - 1][j] + 1);
}
if (j > 0) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i][j - 1] + 1);
}
}
}
// 第二次遍历,反向遍历,根据相邻右元素和下元素及当前元素的结果得出最终结果
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (i < row - 1) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i + 1][j] + 1);
}
if (j < col - 1) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i][j + 1] + 1);
}
}
}
return matrix;
}
}
相关文章
- Java实现 LeetCode 831 隐藏个人信息(暴力)
- Java实现 LeetCode 804 唯一摩尔斯密码词 (暴力)
- Java实现 LeetCode 778 水位上升的泳池中游泳(二分+DFS)
- Java实现 LeetCode 671 二叉树中第二小的节点(遍历树)
- Java实现 LeetCode 637 二叉树的层平均值(遍历树)
- Java实现 LeetCode 1111 有效括号的嵌套深度(阅读理解题,位运算)
- Java实现 LeetCode 506 相对名次
- Java实现 LeetCode 481 神奇字符串
- Java实现 LeetCode 451 根据字符出现频率排序
- Java实现 LeetCode 446 等差数列划分 II - 子序列
- Java实现 LeetCode 443 压缩字符串
- Java实现 LeetCode 443 压缩字符串
- Java实现 LeetCode 409 最长回文串
- Java实现 LeetCode 401 二进制手表
- Java实现 LeetCode 385 迷你语法分析器
- Java实现 LeetCode 365 水壶问题
- Java实现 LeetCode 315 计算右侧小于当前元素的个数
- Java实现 LeetCode 278 第一个错误的版本
- Java实现 LeetCode 257 二叉树的所有路径
- Java实现 LeetCode 237 删除链表中的节点
- Java实现 LeetCode 234 回文链表
- Java实现 LeetCode 136 只出现一次的数字
- Java实现 LeetCode 132 分割回文串 II(二)
- Java实现 LeetCode 128 最长连续序列
- Java实现 LeetCode 82 删除排序链表中的重复元素 II(二)
- Java实现 LeetCode 80 删除排序数组中的重复项 II(二)
- Java实现 LeetCode 137 只出现一次的数字