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日

相关推荐

  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    0100
  • leetcode260-只出现一次的数字III

    原题 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。 示例: 输入: [1,2,1,3,2,5] 输出: [3,5…

    算法 2020年4月28日
    0150
  • leetcode1-两数之和

    原题 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能…

    算法 2019年12月20日
    0110
  • leetcode648-单词替换

    原题 在英语中,我们有一个叫做 词根(root)的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 oth…

    算法 2020年4月20日
    0150
  • 剑指offer62-圆圈中最后剩下的数字

    原题(来源Leetcode) 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如,0、1、2、3、4这5…

    算法 2020年3月30日
    0650
  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250
  • leetcode1071-字符串的最大公因子

    原题 对于字符串 S 和 T,只有在 S = T + ... + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。 返回最长字符串 X,要求满足 X 能除尽 …

    算法 2020年3月12日
    0250
  • leetcode2-两数相加

    原题 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回…

    算法 2019年12月17日
    080
  • leetcode92-反转链表

    原题 https://leetcode.cn/problems/reverse-linked-list-ii/description 题解 头插法 /** * Definition…

    算法 2024年3月28日
    0100
  • leetcode559-N叉树的最大深度

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

    2020年1月20日
    090

发表回复

登录后才能评论