0542.01 Matrix

542. 01 Matrix #

题目 #

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:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.

题目大意 #

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。

解题思路 #

  • 给出一个二维数组,数组里面只有 0 和 1 。要求计算每个 1 距离最近的 0 的距离。
  • 这一题有 3 种解法,第一种解法最容易想到,BFS。先预处理一下棋盘,将每个 0 都处理为 -1 。将 1 都处理为 0 。将每个 -1 (即原棋盘的 0)都入队,每次出队都将四周的 4 个位置都入队。这就想一颗石头扔进了湖里,一圈一圈的波纹荡开,每一圈都是一层。由于棋盘被我们初始化了,所有为 -1 的都是原来为 0 的,所以波纹扫过来不需要处理这些 -1 的点。棋盘上为 0 的点都是原来为 1 的点,这些点在波纹扫过来的时候就需要赋值更新 level。当下次波纹再次扫到原来为 1 的点的时候,由于它已经被第一次到的波纹更新了值,所以这次不用再更新了。(第一次波纹到的时候一定是最短的)
  • 第二种解法是 DFS。先预处理,把周围没有 0 的 1 都重置为最大值。当周围有 0 的 1,距离 0 的位置都是 1,这些点是不需要动的,需要更新的点恰恰应该是那些周围没有 0 的点。当递归的步数 val 比点的值小(这也就是为什么会先把 1 更新成最大值的原因)的时候,不断更新它。
  • 第三种解法是 DP。由于有 4 个方向,每次处理 2 个方向,可以降低时间复杂度。第一次循环从上到下,从左到右遍历,先处理上边和左边,第二次循环从下到上,从右到左遍历,再处理右边和下边。

代码 #


package leetcode

import (
	"math"
)

// 解法一 BFS
func updateMatrixBFS(matrix [][]int) [][]int {
	res := make([][]int, len(matrix))
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return res
	}
	queue := make([][]int, 0)
	for i := range matrix {
		res[i] = make([]int, len(matrix[0]))
		for j := range res[i] {
			if matrix[i][j] == 0 {
				res[i][j] = -1
				queue = append(queue, []int{i, j})
			}
		}
	}
	level := 1
	for len(queue) > 0 {
		size := len(queue)
		for size > 0 {
			size--
			node := queue[0]
			queue = queue[1:]
			i, j := node[0], node[1]
			for _, direction := range [][]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}} {
				x := i + direction[0]
				y := j + direction[1]
				if x < 0 || x >= len(matrix) || y < 0 || y >= len(matrix[0]) || res[x][y] < 0 || res[x][y] > 0 {
					continue
				}
				res[x][y] = level
				queue = append(queue, []int{x, y})
			}
		}
		level++
	}
	for i, row := range res {
		for j, cell := range row {
			if cell == -1 {
				res[i][j] = 0
			}
		}
	}
	return res
}

// 解法二 DFS
func updateMatrixDFS(matrix [][]int) [][]int {
	result := [][]int{}
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return result
	}
	maxRow, maxCol := len(matrix), len(matrix[0])
	for r := 0; r < maxRow; r++ {
		for c := 0; c < maxCol; c++ {
			if matrix[r][c] == 1 && hasZero(matrix, r, c) == false {
				// 将四周没有 0 的 1 特殊处理为最大值
				matrix[r][c] = math.MaxInt64
			}
		}
	}
	for r := 0; r < maxRow; r++ {
		for c := 0; c < maxCol; c++ {
			if matrix[r][c] == 1 {
				dfsMatrix(matrix, r, c, -1)
			}
		}
	}
	return (matrix)
}

// 判断四周是否有 0
func hasZero(matrix [][]int, row, col int) bool {
	if row > 0 && matrix[row-1][col] == 0 {
		return true
	}
	if col > 0 && matrix[row][col-1] == 0 {
		return true
	}
	if row < len(matrix)-1 && matrix[row+1][col] == 0 {
		return true
	}
	if col < len(matrix[0])-1 && matrix[row][col+1] == 0 {
		return true
	}
	return false
}

func dfsMatrix(matrix [][]int, row, col, val int) {
	// 不超过棋盘氛围,且 val 要比 matrix[row][col] 小
	if row < 0 || row >= len(matrix) || col < 0 || col >= len(matrix[0]) || (matrix[row][col] <= val) {
		return
	}
	if val > 0 {
		matrix[row][col] = val
	}
	dfsMatrix(matrix, row-1, col, matrix[row][col]+1)
	dfsMatrix(matrix, row, col-1, matrix[row][col]+1)
	dfsMatrix(matrix, row+1, col, matrix[row][col]+1)
	dfsMatrix(matrix, row, col+1, matrix[row][col]+1)
}

// 解法三 DP
func updateMatrixDP(matrix [][]int) [][]int {
	for i, row := range matrix {
		for j, val := range row {
			if val == 0 {
				continue
			}
			left, top := math.MaxInt16, math.MaxInt16
			if i > 0 {
				top = matrix[i-1][j] + 1
			}
			if j > 0 {
				left = matrix[i][j-1] + 1
			}
			matrix[i][j] = min(top, left)
		}
	}
	for i := len(matrix) - 1; i >= 0; i-- {
		for j := len(matrix[0]) - 1; j >= 0; j-- {
			if matrix[i][j] == 0 {
				continue
			}
			right, bottom := math.MaxInt16, math.MaxInt16
			if i < len(matrix)-1 {
				bottom = matrix[i+1][j] + 1
			}
			if j < len(matrix[0])-1 {
				right = matrix[i][j+1] + 1
			}
			matrix[i][j] = min(matrix[i][j], min(bottom, right))
		}
	}
	return matrix
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者