leetcode221-最大正方形

原题

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

示例:

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

解法

思想

动态规划:

dp(x,y)是以matrix[x][y]为右下角的点的最大正方形的边长,则如果matrix[x][y]=='1',那么dp(x,y)=min(dp(x-1,y-1),dp(x-1,y),dp(x,y-1))。否则dp(x,y)=0

代码

class Solution {

    public int maximalSquare(char[][] matrix) {
        int height = matrix.length;
        if(height == 0) return 0;
        int width = matrix[0].length;
        int[][] edge = new int[height][width];
        int maxEdge = 0;
        for(int i = 0 ; i < height;i++){
            for(int j = 0;j < width;j++){
                if(matrix[i][j] == '0'){
                    edge[i][j] = 0;
                    continue;
                }
                int leftUp = (i == 0 || j == 0) ? 0 : edge[i-1][j-1];
                int left = j == 0 ? 0 : edge[i][j-1];
                int up = i == 0 ? 0 : edge[i-1][j];
                edge[i][j] = Math.min(Math.min(leftUp,left),up) +1;
                if(edge[i][j]>maxEdge) maxEdge = edge[i][j];
            }
        }
        return maxEdge*maxEdge;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode221-%e6%9c%80%e5%a4%a7%e6%ad%a3%e6%96%b9%e5%bd%a2/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月8日
下一篇 2020年5月8日

相关推荐

  • leetcode26-删除排序数组中的重复项

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空…

    算法 2019年11月23日
    0190
  • 蓝桥杯试题-翻硬币

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写…

    算法 2020年3月1日
    0140
  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说,你的设计应该包含以下的功能 put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更…

    算法 2019年12月18日
    0110
  • leetcode1103-分糖果II

    原题 排排坐,分糖果。 我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类…

    算法 2020年3月5日
    0130
  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3 输出:[ "((()))", "(()())", "…

    算法 2020年4月9日
    0130
  • leetcode124-二叉树中的最大路径和

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

    算法 2020年4月26日
    0170
  • 蓝桥杯试题-哈夫曼树

    原题 Description Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列…

    算法 2020年3月1日
    0240
  • leetcode453-最小移动次数使数组元素相等

    原题 给定一个长度为 n 的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。 示例: 输入: [1,2,3] 输出: 3 解释: 只…

    算法 2020年6月7日
    0120
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode912-排序数组

    原题 给定一个整数数组 nums,将该数组升序排列。 示例 1: 输入: [5,2,3,1] 输出: [1,2,3,5] 示例 2: 输入: [5,1,1,2,0,0] 输出: […

    算法 2020年3月31日
    0340

发表回复

登录后才能评论