草庐IT

leetcode 221. Maximal Square 最大正方形(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签: 动态规划

https://leetcode.cn/problems/maximal-square

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

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 '0' 或 '1'

二、解题思路

使用动态规划来解决，使用dp[i][j]表示以(i,j)为右下角，且只饮食1的正方形的边长最大值。如果我们能计算出所有dp[i][j]的值，那么其中的最大值即为矩阵中只饮食1的下方形的边长最大值，其平方即为最大下方形的面积。
如何计算dp中每个元素的值：
若该位置的值为0，则dp[i][j]=0，因为当前位置不可能在由1组成的正方形中
若该位置的值为1，则dp[i][j]的值由其上方、左方和左上方的三个相邻位置的dp值决定，具体就是当前位置的元素值等于三个相邻的元素中的最小值加1，其状态方程如下：
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1

三、解题方法

3.1 Java实现

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

四、总结小记

  • 2022/6/20 倒计时14天
leetcodeMaximalmatrixstrongblockquote算法与数据结构

有关leetcode 221. Maximal Square 最大正方形(中等)的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  3. ruby - 获取数组中值的最大连续出现次数 - 2

    下面有没有更优雅的方法来实现这个:输入:array=[1,1,1,0,0,1,1,1,1,0]输出:4我的算法:streak=0max_streak=0arr.eachdo|n|ifn==1streak+=1elsemax_streak=streakifstreak>max_streakstreak=0endendputsmax_streak 最佳答案 类似于w0lf'sanswer,但通过从chunk返回nil来跳过元素:array.chunk{|x|x==1||nil}.map{|_,x|x.size}.max

  4. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  5. ruby - capybara 增加最大允许页面加载时间 - 2

    我有一个页面，有时加载时间超过一分钟。假设这是预期的行为并且不会改变。在这些情况下，我得到Net::ReadTimeout。请注意，这是在通过单击上一页上的按钮导航到页面之后，而不是ajax请求。因此Capybara.using_wait_time没有帮助。我尝试了一些激进的方法(其中一些我知道行不通)，例如:设置page.driver.browser.manage.timeouts的implicit_wait、script_timeout和page_load。遍历整个对象空间并设置所有Selenium::WebDriver::Remote::Http::Default的timeout

  6. Ruby - 找到哈希最大值的键 - 2

    我有一个散列，我想返回散列最大值的键(或键/值对)。所以，如果只有一个真正的最大值，它将返回那个键；但是，如果有多个具有相同值的键/值对，它将返回所有这些键。我如何在Ruby中完成此操作？my_hash.max_by{|k,v|v}#onlyreturnsonekey/valuepair 最佳答案 如果你想要所有对，我会做类似的事情max=my_hash.values.maxHash[my_hash.select{|k,v|v==max}] 关于Ruby-找到哈希最大值的键，我们在Sta

  7. Ruby:获取具有最大值的哈希对 - 2

    这是一个哈希值，用于跟踪我拥有的每种水果的数量fruits={"apples"=>10,"pears"=>15,"bananas"=>15,"grapes"=>12}我想知道哪种水果我吃得最多。如果有决胜局，则将它们全部归还。 最佳答案 #easymax_quantity=fruits.values.maxmax_fruits=fruits.select{|k,v|v==max_quantity}.keys#fastmax_quantity=-1.0/0.0max_fruits=[]fruits.eachdo|k,v|ifv>max

  8. ruby-on-rails - 如何在 ruby​​ 中找到跨记录的最大属性？ - 2

    我有几个具有多个属性(A、B、C、D)的记录。我希望能够找到哪条记录对于给定属性(例如D)具有更高的值。我该怎么做？ 最佳答案 你可能会给出max_by一看。objects=[somearrayofobjects]object_with_highest_value=objects.max_by{|obj|obj.desired_value} 关于ruby-on-rails-如何在ruby​​中找到跨记录的最大属性？，我们在StackOverflow上找到一个类似的问题：

  9. ruby - 如何获取两个数组之间的最大值数组 - 2

    我正在寻找一种优雅的方法来获取包含两个数组之间最大值的数组。意思是如果有两个数组:a=[1,5,9]b=[3,2,11]结果应该是:=>[3,5,11]假设两个数组的大小相同。我使用的代码感觉不像是用Ruby的方式来完成这个任务:c=Array.new(a.size)foriin0...a.sizec[i]=[a[i],b[i]].maxend 最佳答案 这应该有效:[a,b].transpose.map(&:max)#=>[3,5,11]transpose返回[[1,3],[5,2],[9,11]]和map(&:max)找到每个子

  10. ruby - 我天真的最大团发现算法比 Bron-Kerbosch 的运行得更快。怎么了？ - 2

    简而言之，我的原始代码(用Ruby编写)如下所示:#$seenisahashtomemoizepreviouslyseensets#$sparseisahashofusernamestoalistofneighboringusernames#$setisthelistofoutputclusters$seen={}defsubgraph(set,adj)hash=(set+adj).sortreturnif$seen[hash]$sets.pushset.sort.join(",")ifadj.empty?andset.size>2adj.each{|node|subgraph(set

随机推荐