221 最大正方形

news/2024/3/29 3:41:12/文章来源:https://blog.csdn.net/skullFang/article/details/129193092

#221 最大正方形

题目描述

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

示例 1:

img

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

题目解释

如果想让右下角为正方形的右下角,必须红、绿、蓝、三个框框内所有元素都为1。

image-20230224020609684

进一步思考

右下角为正方形的右下角的边长,是三个框框中最小的那个+1。因为三个框框分别对应了。正方形其余是几条边。因为木桶效应,新的正方形边长当然是最短的边+1了。image-20230224020821504

定义dp[i][j]dp[i][j]dp[i][j]是以i,ji,ji,j为正方形右下角的最大正方形边长。图中红色框框的边长dp[i−1][j−1]dp[i-1][j-1]dp[i1][j1],绿色的边长dp[i][j−1]dp[i][j-1]dp[i][j1],蓝色的边长dp[i−1][j]dp[i-1][j]dp[i1][j]。那么推导公式。
mat[i][j]=0−>dp[i][j]=0mat[i][j]=1−>min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])+1mat[i][j]=0->dp[i][j]=0\\ mat[i][j]=1->min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1 mat[i][j]=0>dp[i][j]=0mat[i][j]=1>min(dp[i1][j1],dp[i1][j],dp[i][j1])+1
初始化

根据推导公式和定义初始化,应该初始化第0行和第0列。初始化值应该与矩阵中的值对应。

代码

class Solution:def maximalSquare(self, matrix: List[List[str]]) -> int:"""定义dp[i][j]以i,j为右下角的最大正方形面积边长"""m=len(matrix)n=len(matrix[0])dp=[[0 for _ in range(n)] for _ in range(m)]for i in range(m):if matrix[i][0]=='1':dp[i][0]=1for j in range(n):if matrix[0][j]=='1':dp[0][j]=1for i in range(1,m):for j in range(1,n):if matrix[i][j]=='1':dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1else:dp[i][j]=0max_len=0for i in range(m):for j in range(n):max_len=max(max_len,dp[i][j])return max_len**2

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_73470.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【LeetCode】2357. 使数组中所有元素都等于零

2357. 使数组中所有元素都等于零 题目描述 给你一个非负整数数组 nums 。在一步操作中,你必须: 选出一个正整数 x ,x 需要小于或等于 nums 中 最小 的 非零 元素。nums 中的每个正整数都减去 x。 返回使 nums 中所有元素都等于 0 需要的 …

经典设计模式MVC理解

MVC是模型(Model)、视图(View)、控制器(Controller)的简写,将业务逻辑、数据、显示分离的方法来组织代码。今天简单回顾一下。 mvc释义理解 M代表模型(Model),表示业务规则封装。在MVC的三个部件中,模型拥有最多的处理任务。被模型返回的数据…

图表类可视化开发采坑记录之旅3

如图所示的扇形图样式改造&#xff1a; 开发框架&#xff1a; 基于vue2&#xff0c;echarts5.0.0 基于组件&#xff1a; html代码&#xff1a; <div class"showCanvas"><div id"midError"></div> </div> css代码&#xff1a; …

【华为OD机试模拟题】用 C++ 实现 - 去除多余空格(2023.Q1)

最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…

运动蓝牙耳机什么牌子好,运动蓝牙耳机品牌推荐

现在市面上运动耳机的品牌越来越多&#xff0c;还不知道选择哪一些运动耳机品牌&#xff0c;可以看看下面的一些耳机分享&#xff0c;运动耳机需要注意耳机的参数配置以及佩戴舒适度&#xff0c;根据自己最根本的使用需求来选择运动耳机。 1、南卡Runner Pro4骨传导蓝牙运动耳…

C/C++开发,无可避免的内存管理(篇一)-内存那些事

一、内存管理机制 任何编程语言在访问和操作内存时都会涉及大量的计算工作。但相对其他语言&#xff0c;c/c开发者必须自行采取措施确保所访问的内存是有效的&#xff0c;并且与实际物理存储相对应&#xff0c;以确保正在执行的任务不会访问不应该访问的内存位置。C/C语言及编译…

mongoDB的安装与使用

MongoDB安装MongoDB官方网站&#xff1a;https://www.mongodb.com/try/download/community-kubernetes-operator2软件安装权限不足&#xff1a;https://www.javaclub.cn/database/56541.htmlstep1:打开安装包直接点击Nextstep2&#xff1a;继续点击Nextstep3&#xff1a;点击自…

DMotion - 基于DOTS的动画框架和状态机

【博物纳新】专栏是UWA旨在为开发者推荐新颖、易用、有趣的开源项目&#xff0c;帮助大家在项目研发之余发现世界上的热门项目、前沿技术或者令人惊叹的视觉效果&#xff0c;并探索将其应用到自己项目的可行性。很多时候&#xff0c;我们并不知道自己想要什么&#xff0c;直到某…

day51【代码随想录】动态规划之回文子串、最长回文子序列

文章目录前言一、回文子串&#xff08;力扣647&#xff09;二、最长回文子序列&#xff08;力扣516&#xff09;前言 1、回文子串 2、最长回文子序列 一、回文子串&#xff08;力扣647&#xff09; 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目…

数据库防护做不好,分分钟要被勒索比特币,每个接触数据库的都必须知道

公司有个公网数据库被黑了&#xff0c;对方留言勒索0.006比特币&#xff0c;按目前比特币的价值&#xff0c;大概1009元人民币左右&#xff0c;虽然不多&#xff0c;但发生这个事情着实让人丢脸&#xff0c;说明平时对防护还做不到位&#xff01; 还好公司平时有做数据库防范措…

骨传导耳机靠谱吗,骨传导耳机的原理是什么

很多人刚开始接触骨传导耳机时都会具有一个疑问&#xff0c;骨传导耳机是不是真的靠谱&#xff0c;是不是真的不伤害听力&#xff1f;骨传导耳机传输声音的原理是什么&#xff1f; 下面就给大家讲解一下骨传导耳机传输声音的原理以及骨传导耳机对听力到底有没有伤害。 骨传导…

DeepLabV3+:对预测处理的详解

相信大家对于这一部分才是最感兴趣的&#xff0c;能够实实在在的看到效果。这里我们就只需要两个.py文件&#xff08;deeplab.py、predict_img.py&#xff09;。 创建DeeplabV3类 deeplab.py的作用是为了创建一个DeeplabV3类&#xff0c;提供一个检测图片的方法&#xff0c;而…

如何通过jar包得知maven坐标,以及如何替换依赖的依赖的版本

问题一&#xff1a;我只能得到这个jar包的名字&#xff0c;如果得知这个jar包的maven坐标&#xff08;groupId以及artifactId&#xff09;&#xff1f; 思路1&#xff1a;将jar包的名字&#xff08;去除版本号&#xff09;在mvn仓库中搜索&#xff0c;地址&#xff1a;https:/…

Linux期末考试应急

Linux期末考试应急 虚拟机添加硬盘、分区、格式化、挂载、卸载 fdisk -l#查看系统现有分区fdisk <指定磁盘>#指定磁盘分区sudo mkfs.ext3 <指定分区>#格式化磁盘###挂载磁盘1.新建一个目录sudo mkdir /mnt/test2.将指定分区挂载到对应目录sudo mount /dev/sdb10 /…

PHPExcel 表格设置

4.5.3。通过行和列设置单元格值 通过设置坐标单元格值可以使用工作表的setCellValueByColumnAndRow方法来实现。 //设置单元格B8 $objPHPExcel->getActiveSheet()->setCellValueByColumnAndRow(1, 8, ‘Some value’); 4.5.4。由列和行中检索的小区 检索的小区的值&#…

什么蓝牙耳机打游戏好?打游戏好用的无线蓝牙耳机

午休或是周末约上好友玩两局游戏&#xff0c;是忙里偷闲的快乐时刻&#xff0c;对于普通游戏玩家&#xff0c;其实耳机够用就行&#xff0c;下面就分享几款打游戏好用的蓝牙耳机。 一、南卡小音舱蓝牙耳机 蓝牙版本&#xff1a;5.3 推荐系数&#xff1a;五颗星 南卡小音舱li…

酷开系统AI人工智能技术,为营销抢夺更多目标消费者

随着越来越多的年轻群体回归家庭&#xff0c;互联网电视产业正在时代的浪潮下快速发展&#xff0c;如今已经有数以万计的家庭消费者倾向于在客厅场景中使用大屏电视观看更多丰富的电视节目&#xff0c;而这一趋势&#xff0c;对于急需线上互动营销渠道的企业和品牌方来说&#…

乘上算力发展的东风,联想这次能否变革突起?

“逆水行舟&#xff0c;不进则退”笔者认为这句话也同样适用到现在的联想集团身上&#xff0c;近3年受到疫情的影响全球电子领域普遍不突出&#xff0c;智能手机出货量上涨乏力&#xff0c;个人电脑&#xff08;PC&#xff09;的销量也波动频繁&#xff0c;联想集团在这种不乐观…

追梦之旅【数据结构篇】——详解C语言实现链栈

详解C语言实现链栈~&#x1f60e;前言&#x1f64c;整体实现内容分析&#x1f49e;1.头文件编码实现&#x1f64c;2.功能文件编码实现&#x1f64c;3.测试函数功能代码&#x1f64c;总结撒花&#x1f49e;&#x1f60e;博客昵称&#xff1a;博客小梦 &#x1f60a;最喜欢的座右…

茂名市 2021 年高中信息技术学科素养展评

没事干&#xff0c;发一下去年去比赛的题目。 目录 第一题 30分 第二题 30分 第一题 30分 题目&#xff1a; “姐姐&#xff0c;乘除法运算太难了&#xff0c;有什么办法能熟练掌握吗&#xff1f;”今年 读小学四年级的表弟向李红求救。为了提高表弟的运算能力&#xff0c;…