云博
Leetcode 542. 01矩阵 动态规划+BFS解

阅读量:(97) 您现在所在的位置: 首页 百宝箱 Leetcode Leetcode 542. 01矩阵 动态规划+BFS解 作者:慎独、
简介:Leetcode 542. 01矩阵 动态规划+BFS解 。动态规划:要考虑4个方向,所以需要2次动态规划。以及初始值该如何选择以避免出错,还有不为0的条件的判断。BFS:要维护一个集合去重,避免产生死循环。

题目 :Leetcode 542. 01矩阵 一刷 (中等)


解题思路:

两种思路:

① 动态规划

② BFS

我一开始想到的是动态规划,这道题就好比机器人寻路那道题,下一步所得到的值,依赖于上一步的所有值的一个比较判断。

因为这道题要求上下给定的元素会在上下左右这四个方向进行判断。而机器人寻路只能向下向右走。

因此我们运用动态规划的思路就可以解题了。

法一


具体步骤:

① 定义元素状态:我们要求某个元素距离某1个0(题目中会出现多个0),距离要求最短。而题目中的矩阵是二维的,因此我们 就可以定义一个二维数组dp。

② 建立状态转移方程:我们这里要考虑边界的情况,上下左右四周,因此我们需要对方程分段一下。

首先考虑向右向下的情况:此时每一步的距离都会由其左和上的位置的距离比较。

但这里为了使得边界的比较容易理解一些:将状态转移分为两个比较。

if col >= 1:
    dp[row][col] = min(dp[row][col],dp[row][col-1]+1)
if row >= 1:
    dp[row][col] = min(dp[row][col],dp[row-1][col]+1)

注:

当列大于等于第二列的时候,才会考虑比较其左边。当行大于等于第二列的时候,才会考虑其上边,因为这里并没有加上边界条件, 添加边界条件最后还得删掉边界条件太麻烦了。因此就拆分成两个判断。

如果光是考虑左上的话,就有可能到这各个角落处的距离出现问题。因此还需要考虑右下。

那么此时就有可能有人问一个问题,是否还需要考虑左下和右上呢?其实我们可以仔细分析一下, 其实只要考虑左上和右下就行了,这里举个简单直观的小例子。

1 0 1 0 1

我们观察中间这个值,只需要左上和右下两次动态规划就可以满足其上下左右4中情况了。

因此右下同理。

因此状态转移公式:

① 左上:

if col >= 1:
    dp[row][col] = min(dp[row][col],dp[row][col-1]+1)
if row >= 1:
    dp[row][col] = min(dp[row][col],dp[row-1][col]+1)

② 右下:

if col < n-1:
    dp[row][col] = min(dp[row][col],dp[row][col+1]+1)
if row < m-1:
    dp[row][col] = min(dp[row][col],dp[row+1][col]+1)

③ 初始化状态为了求解最小距离,我们可以将dp数组全部赋值为float(inf)(无穷,或者大于10000的任何数),同时找出matrix中为0的位置i,j,将dp中相应的 位置置0。如果不设置为大于10000的任何数,就有可能产生误差(会导致该位置的值不会依赖左上或右下两个方向的值来取得最小值)

④ 选取结果 结果要求返回数组,因此本题的结果可以用dp替代。

代码:

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        # 动态规划,分2部分建立状态转移方程
        # 创建二位dp数组
        m = len(matrix)
        n = len(matrix[0])
        dp = [[float(inf) for _ in range(n)] for _ in range(m)]
        for row in range(m):
            for col in range(n):
                if matrix[row][col] == 0:
                    dp[row][col] = 0
        # 向右向下
        for row in range(m):
            for col in range(n):
                if col >= 1:
                    dp[row][col] = min(dp[row][col],dp[row][col-1]+1)
                if row >= 1:
                    dp[row][col] = min(dp[row][col],dp[row-1][col]+1)
        # 向左向上
        for row in range(m-1,-1,-1):
            for col in range(n-1,-1,-1):
                if col < n-1:
                    dp[row][col] = min(dp[row][col],dp[row][col+1]+1)
                if row < m-1:
                    dp[row][col] = min(dp[row][col],dp[row+1][col]+1)

        return dp

或者直接在原矩阵上进行判断修改,这样就无须多开辟一个二维空间:

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                max_i,max_j = 10001,10001
                if matrix[i][j] != 0:
                    if i>=1:
                        max_i = matrix[i-1][j]
                    if j>=1:
                        max_j = matrix[i][j-1]
                    matrix[i][j] = min(max_i,max_j)+1
        for i in range(m-1,-1,-1):
            for j in range(n-1,-1,-1):
                max_i,max_j = 10001,10001
                # 对不为0的值进行修改
                if matrix[i][j] != 0:
                    if i <= m-2:
                        max_i = matrix[i+1][j]
                    if j <= n-2:
                        max_j = matrix[i][j+1]
                    # 因为最终要比较3个值,分别为当前位置,当前位置的下方,当前位置的右方。
                    matrix[i][j] = min(matrix[i][j], min(max_i,max_j)+1)
        return matrix

法二

DFS深度优先遍历,首先选出所有不为0的值,将这些0的位置坐标放入队列中。同时维护一个集合,用于装载 所有已经运算过一次的位置。防止多次运算重复,造成死循环。

本题中DFS的过程就是由内向外不断扩展的过程。

代码

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        from collections import deque
        m = len(matrix)
        n = len(matrix[0])
        list_zero = [(i,j) for j in range(n) for i in range(m) if matrix[i][j] == 0]
        q = deque(list_zero)
        set_ = set(list_zero)

        while(q):
            row,col = q.popleft()
            for i,j in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                if 0 <= i <= m-1 and 0 <= j <= n-1 and (i,j) not in set_ and matrix[i][j] != 0:
                    matrix[i][j] = matrix[row][col] + 1
                    set_.add((i,j))
                    q.append((i,j))
        return matrix

点赞一波

1
    评论集
  • 慎独、    2020-07-03 08:06
    法二中的DFS深度优先改为BFS广度优先,笔误
    0 0
    回复

  • 下方评论哦~

    欢迎您游客

 小云标签


 网站统计:


笔记数: 总点赞量:

总访问量:   分类数目:

服务器:阿里云服务器

 网站动态: