leetcode542. 01 Matrix
leetcode542. 01 Matrix
眯眯眼的猫头鹰
发布于 2020-05-11 17:32:17
发布于 2020-05-11 17:32:17
题目要求
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:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.
现有一个0和1构成的二维数组，要求计算每一位距离0最近的距离。加入当前值为0，则距离0最近的距离就是0。
思路一：BFS
广度优先算法的核心思路在于，从每一个最近的距离开始，不断延展开去，直到所有的下标都找到了最近的值。 以第二个例子为基础，思路如下：
原始数组：
[[0,0,0],
[0,1,0],
[1,1,1]]
1. 先将所有非0的点的距离更新为最大
[[0,0,0],
[0,max,0],
[max,max,max]]
2. 以所有原始距离为0的点向外搜索一格，将当前距离大于0的最近距离更新为1
[[0,0,0],
[0,1,0],
[1,max,1]]
3. 再将所有最近距离为1的向外拓展一圈
[[0,0,0],
[0,1,0],
[1,2,1]]至此所有的最近距离都已经得出。
广搜通常都需要通过队列来实现。代码如下：
public int[][] updateMatrix(int[][] matrix) {
int row = matrix.length;
int column = matrix[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0 ; i<row ; i++) {
for (int j = 0 ; j<column; j++) {
if (matrix[i][j] == 0) {
queue.offer(new int[]{i,j});
} else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
int[][] directions = new int[][]{
{0,-1},
{-1,0},
{0,1},
{1,0}
};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] direction : directions) {
int neighbourRow = cell[0] + direction[0];
int neighbourColumn = cell[1] + direction[1];
if (neighbourRow < 0 || neighbourRow >= row || neighbourColumn < 0 || neighbourColumn >= column
|| matrix[neighbourRow][neighbourColumn] <= matrix[cell[0]][cell[1]] + 1) {
continue;
}
queue.offer(new int[]{neighbourRow, neighbourColumn});
matrix[neighbourRow][neighbourColumn] = matrix[cell[0]][cell[1]] + 1;
}
}
return matrix;
}思路二：DFS
深度优先则是从最左上角节点开始，从左往右从上往下依次，对上下左右四个方向都进行最近距离的计算。这里需要额外用一个数组来记录结果值，从而防止出现重复判断的情况。比如：
[[0,0],
[1,1],
[1,1]]如果不判断当前节点是否访问过，则会在全是1的子数组中无限遍历，始终得不出最短距离。代码如下：
public int[][] updateMatrix(int[][] matrix) {
int row = matrix.length;
int column = matrix[0].length;
int[][] result = new int[row][column];
for (int i = 0 ; i<row ; i++) {
for (int j = 0 ; j<column; j++) {
result[i][j] = updateMatrix(matrix, i, j, result);
}
}
return result;
}
public int updateMatrix(int[][] matrix, int i, int j, int[][] result) {
if (matrix[i][j] == 0) {
return 0;
}
if (i > 0 && matrix[i-1][j] == 0){
return 1;
}
if (j > 0 && matrix[i][j-1] == 0) {
return 1;
}
if (i < matrix.length-1 && matrix[i+1][j] == 0) {
return 1;
}
if (j < matrix[0].length - 1 && matrix[i][j+1] == 0) {
return 1;
}
int min = Integer.MAX_VALUE - 1;
if (i > 0 && result[i-1][j] != 0) {
min = Math.min(min, result[i-1][j]);
}
if (j > 0 && result[i][j-1] != 0) {
min = Math.min(min, result[i-1][j]);
}
if (i < matrix.length - 1) {
min = Math.min(min, updateMatrix(matrix, i+1, j, result));
}
if (j < matrix[0].length - 1) {
min = Math.min(min, updateMatrix(matrix, i, j+1, result));
}
return min + 1;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录