首页 > 代码库 > 【LeetCode】542. 01 Matrix
【LeetCode】542. 01 Matrix
Problem description
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.
题目分析:
1.题目的大意就是找出离目标最近的点的距离。
2.题目直觉是搜索,可用DFS或者BFS,但是看到有10000*10000的数据,假如用简单的DFS BFS,有TLE的可能,题目是一种找最优解的题,可以用DP分析一下,分析如下:
我们知道,二维数组可以拆分为垂直和水平的一维数组。
假设水平一维数组[0,1,1],在位置3的数字肯定是前面非0数字距离的值加1,因此 dis[i] = dis[i-1] + 1。
假设在上述一维数组的3位置,扩展出垂直向上一维数组[1,0,0],同理的,dis[j] = dis[j] + 1。
此时我们就得到了某个点向左和向上的距离0的值,min(top,left)可得出向左和向右的最小距离值。
一样的,我们分析向右和向上,跟上面是同理的,
递推方程分别为:
dis[i] = dis[i+1]+1 和 dis[j]=dis[j+1]+1,
最后,我们得到了(向左,向上,设A) 以及 (向右,向下,设B)的距离最小值,再min(A,b)就好了。
因为最近在学习C#,所以贴一下C#的代码 ^_^
public int[,] UpdateMatrix(int[,] matrix) { int maxV = matrix.GetLength(0) * matrix.GetLength(1); int[,] ans = new int[matrix.GetLength(0), matrix.GetLength(1)];
//判断左上 for (int i = 0; i < matrix.GetLength(0); i++) { for (int j = 0; j < matrix.GetLength(1); j++) { if (matrix[i, j] == 0) { ans[i, j] = 0; } else { int left = j > 0 ? ans[i, j - 1] : maxV; int top = i > 0 ? ans[i - 1, j] : maxV; ans[i, j] = Math.Min(left, top) +1 ; } } } //判断右下 for (int i = matrix.GetLength(0) - 1 ; i >= 0; i--) { for (int j = matrix.GetLength(1) - 1; j>=0 ; j--) { if (matrix[i, j] == 0) { ans[i, j] = 0; } else { int right = j < matrix.GetLength(1) - 1 ? ans[i, j + 1] : maxV; int bottom = i < matrix.GetLength(0) - 1 ? ans[i + 1, j] : maxV; ans[i, j] = Math.Min(Math.Min(right, bottom) + 1,ans[i,j]); } } } return ans; }
【LeetCode】542. 01 Matrix
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。