leetcode542-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

注意:

  1. 给定矩阵的元素个数不超过 10000。
  2. 给定矩阵中至少有一个元素是 0。
  3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解法

思想

  • BFS:
    先将所有0标记出,然后紧挨0未被标记出的就是1,标记所有1,紧挨1未被标记出的就是2……

BFS

  • 动态规划:
    依次遍历每个元素,如果四周有0就是1,如果没有也不是0就根据所有相邻元素对应的值中的最小值+1获得。

代码

BFS:

class Point{
    public int x;
    public int y;
    public Point(int x,int y){
        this.x = x;
        this.y = y;
    }
} 

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int height = matrix.length;
        int width = matrix[0].length;
        int[][] marked = new int[height][width];
        int[][] ans = new int[height][width];
        Queue<Point> queue = new LinkedList<>();
        //将原二维数组中所有0答案设为0
        for(int i = 0;i<height;i++){
            for(int j = 0;j<width;j++){
                if(matrix[i][j] == 0){
                    marked[i][j] = 1;
                    ans[i][j] = 0;
                    queue.offer(new Point(i,j));
                }
            }
        }

        while(!queue.isEmpty()){
            Point point = queue.poll();
            if(point.x!=0 && marked[point.x-1][point.y]!=1){
                ans[point.x-1][point.y] = ans[point.x][point.y]+1;
                marked[point.x-1][point.y] = 1;
                queue.offer(new Point(point.x-1,point.y));
            } 
            if(point.x!=height-1 && marked[point.x+1][point.y]!=1){
                ans[point.x+1][point.y] = ans[point.x][point.y]+1;
                marked[point.x+1][point.y] = 1;
                queue.offer(new Point(point.x+1,point.y));
            } 
            if(point.y!=0 && marked[point.x][point.y-1]!=1){
                ans[point.x][point.y-1] = ans[point.x][point.y]+1;
                marked[point.x][point.y-1] = 1;
                queue.offer(new Point(point.x,point.y-1));
            } 
            if(point.y!=width-1 && marked[point.x][point.y+1]!=1){
                ans[point.x][point.y+1] = ans[point.x][point.y]+1;
                marked[point.x][point.y+1] = 1;
                queue.offer(new Point(point.x,point.y+1));
            }     
        }
        return ans;
    }
}

动态规划:

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length ;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int i = 0;i < m; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = dfs(matrix, dp, i, j);
            }
        }
       return dp;     
    }
    public static int dfs(int[][] matrix,int[][] dp, int i, int j){
        int m = matrix.length ;
        int n = matrix[0].length;
        if(i<0 || i>m-1 || j < 0 || j > n-1) return 9999;
        // 如果自身是0
        if(matrix[i][j] == 0) return 0;
        // 如果四周有0
        if(i > 0 && matrix[i-1][j] == 0) return 1;
        if(j < n-1 && matrix[i][j+1] == 0) return 1;
        if(i < m-1 && matrix[i+1][j] == 0) return 1; 
        if(j>0 && matrix[i][j-1] == 0) return 1;
        // 如果四周没有0根据四周的dp最小值+1获取
        int left,bottom,right,top;
        left=top=9999;

        if(i > 0 && dp[i-1][j] != 0){
            top = dp[i-1][j];
        }
        if(j> 0 && dp[i][j-1] != 0){
            left = dp[i][j-1];
        }
        bottom = dfs(matrix, dp,i+1, j);
        right = dfs(matrix, dp,i,j+1);
        return Math.min(Math.min(left, right), Math.min(top,bottom))+1; 
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode542-01%e7%9f%a9%e9%98%b5/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月12日
下一篇 2019年12月14日

相关推荐

  • leetcode125-验证回文串

    原题 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明: 本题中,我们将空字符串定义为有效的回文串。 示例 1: 输入: "A man, a …

    算法 2020年5月21日
    0100
  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode84-柱状图中最大的矩形

    原题 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽…

    2020年1月24日
    0100
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0100
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0380
  • 程序员面试金典17.16-按摩师

    原题(来源Leetcode) 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,…

    算法 2020年3月24日
    0630
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0110
  • leetcode135-分发糖果

    原题 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到 1 个…

    算法 2020年2月17日
    060
  • leetcode559-N叉树的最大深度

    原题 给定一个 N 叉树,找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如,给定一个 3叉树 : 我们应返回其最大深度,3。 说明: 树的深度不会…

    2020年1月20日
    050
  • leetcode557-反转字符串中的单词III

    原题 给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。 示例1: 输入: “Let’s take LeetCode contest” 输出: …

    算法 2019年11月23日
    0100

发表回复

登录后才能评论