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日

相关推荐

  • leetcode1115-交替打印FooBar

    原题 我们提供一个类: class FooBar { public void foo() {     for (int i = 0; i < n; i++) {       …

    算法 2020年2月2日
    0180
  • leetcode219-存在重复元素II

    原题 给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。 示例1…

    算法 2019年12月24日
    0190
  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]…

    算法 2020年5月15日
    0470
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170
  • leetcode999-车的可用捕获量

    原题 999. 车的可用捕获量 - 力扣(LeetCode) 解法 思想 这道题题目有点难理解,其实就是上下左右搜索,质量有点低了。 代码 class Solution { cha…

    算法 2020年3月26日
    070
  • 程序员面试金典17.16-按摩师

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

    算法 2020年3月24日
    01000
  • leetcode55-跳跃游戏

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入: [2,3,1…

    算法 2020年2月9日
    090
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0200
  • leetcode191-位1的个数

    原题 编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。 示例 1: 输入: 000000000000000000000000…

    算法 2020年4月15日
    0120
  • leetcode75-颜色分类

    原题 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分…

    算法 2020年4月19日
    0230

发表回复

登录后才能评论