LeetCode 542. 01 矩阵

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 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。
• 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/01-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

本题比较直接想到的是BFS和DFS，另外还有dp不容易想到;
图解：

思路1-BFS

• 把所有的0位置当作同源起始搜索位置往内层bfs;

算法复杂度:（N为数组的元素总数）

• 时间复杂度： $ {\color{Magenta}{\Omicron\left(N\right)}} $
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(N\right)}} $

思路2-DFS

• 把最外层的1当作DFS的同源起始位置，可以减少递归栈的深度，因为BFS时外层的0只会做一次判断，但是DFS时，外层的0会互相进入递归，而这样的递归是无意义的；

算法复杂度:（N为数组的元素总数）

• 时间复杂度： $ {\color{Magenta}{\Omicron\left(N\right)}} $
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(N\right)}} $

思路3-dp动态规划，从左上角到右下角往复扫描一次

• 第一次扫描遇到非0位置先给最大路径，然后再左上收敛；
• 第二次扫描从右下再收敛一遍；

算法复杂度:（N为数组的元素总数）

• 时间复杂度： $ {\color{Magenta}{\Omicron\left(N\right)}} $
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

算法源码示例

原文链接:https://www.cnblogs.com/izhoujie/p/12708457.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有