力扣(LeetCode)221

栏目: 编程工具 · 发布时间: 6年前

内容简介:题目地址:题目描述:

题目地址:

https://leetcode-cn.com/probl...

题目描述:

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

示例:

输入:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

输出: 4

解答:

这一题使用动态规划算法。dpi表示以点(i,j)为右下角点的最大正方形的边长,那么就有若matrixi = '0',dpi = 0,否则dpi = 1+min(dpi-1,min(dpi-1,dpi))

然后查找dpi的最大值max,返回max*max

java ac代码:

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0)return 0;
        
        int[][]dp = new int[matrix.length][matrix[0].length];
        for(int i = 0;i < matrix.length;i++)
            dp[i][0] = matrix[i][0]-'0';
        for(int j = 0;j < matrix[0].length;j++)
            dp[0][j] = matrix[0][j]-'0';
        
        for(int i = 1;i < matrix.length;i++)
            for(int j = 1;j < matrix[0].length;j++)
                if(matrix[i][j] != '0')
                dp[i][j] = 1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
        
        int max = 0;
        for(int i = 0;i < matrix.length;i++)
            for(int j = 0;j < matrix[0].length;j++)
                max = Math.max(dp[i][j],max);
        return max*max;
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Haskell趣学指南

Haskell趣学指南

[斯洛文尼亚] Miran Lipovaca / 李亚舟、宋方睿 / 人民邮电出版社 / 2014-1

《haskell趣学指南》是一本讲解haskell这门函数式编程语言的入门指南,语言通俗易懂,插图生动幽默,示例短小清晰,结构安排合理。书中从haskell的基础知识讲起,涵盖了所有的基本概念和语法,内容涉及基本语法、递归、类型和类型类、函子、applicative 函子、monad、zipper及所有haskell重要特性和强大功能。 《haskell趣学指南》适合对函数式编程及haske......一起来看看 《Haskell趣学指南》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具