Leetcode(每日一题)——1139. 最大的以 1 为边界的正方形
摘要
1139. 最大的以 1 为边界的正方形
一、以1为边界的最大正方形
1.1 动态规划
第530
题需要正方形所有网格中的数字都是1
,只要搞懂动态规划的原理,代码就非常简洁。而这题只要正方形4
条边的网格都是1即可,中间是什么数字不用管。
这题解题思路是这样的
- 第一步先计算每个网格中横向和竖向连续1的个数。
- 第二步遍历二维网格,以每一个格子为正方形的右下角,分别找出上边和左边连续1的个数,取最小值作为正方形的边长,然后判断正方形的左边和上边长度是否都大于等于正方形边长,如果都大于等于正方形边长就更新正方形的最大边长,否则缩小正方形的边长,继续判断……。
代码比较简单,我们定义一个三维数组,其中
- dp[i][j][0]: (i,j)横向连续1的个数
- dp[i][j][1]: (i,j)竖向连续1的个数
第一步: 我们计算的时候,如果当前位置是0就跳过,只有是1的时候才计算,分别统计左边和上边(也就是横向和竖向)连续1的个数。代码比较简单,我们来看下(这里为了减少一些边界条件的判断,把dp的宽和高都增加了1)。
int m = grid.length;
int n = grid[0].length;
//dp[i][j][0]: (i,j)横向连续1的个数
//dp[i][j][1]: (i,j)竖向连续1的个数
int[][][] dp = new int[m + 1][n+1][2];
for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {//如果当前位置是0,就跳过if (grid[i - 1][j - 1] == 0)continue;//如果是1,我们就计算横向和竖向连续1的个数dp[i][j][0] = dp[i][j - 1][0] + 1;dp[i][j][1] = dp[i - 1][j][1] + 1;}
}
第二步:找出正方形的最大边长
我们会以网格中的每一个位置为正方形的右下角,来找出正方形的边长。如下图所示,我们以橙色的位置1为正方形的右下角,分别沿着左边和上边找出他们连续1的个数,最小的作为正方形的边长。因为左边和上边连续1的个数我们在第一步的时候已经计算过,分别是dp[i][j][0]和dp[i][j][1],也就是正方形的边长我们暂时可以认为是
其实大家已经看到了这个边长就是正方形下边和右边的长度,但是正方形的上边和左边我们还没确定,我们继续确定正方形左边和上边的长度。会有两种情况
- 一种如下图所示,就是正方形左边和上边的长度都大于
curSide
,我们可以认为以坐标(i,j)
为右下角的正方形的最大长度就是curSide
。
另一种如下图所示,正方形上边的长度是1
,小于curSide
。
这种情况下是构不成正方形的,所以我们要缩小curSide
的值,然后再继续判断
public int largest1BorderedSquare(int[][] grid) {int m = grid.length;int n = grid[0].length;//dp[i][j][0]: (i,j)横向连续1的个数//dp[i][j][1]: (i,j)竖向连续1的个数int[][][] dp = new int[m + 1][n + 1][2];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {//如果当前位置是0,就跳过if (grid[i - 1][j - 1] == 0)continue;//如果是1,我们就计算横向和竖向连续1的个数dp[i][j][0] = dp[i][j - 1][0] + 1;dp[i][j][1] = dp[i - 1][j][1] + 1;}}int maxSide = 0;//记录正方形的最大长度for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {//沿着当前坐标往上和往左找出最短的距离,暂时看做是正方形的边长(正方形的具体边长//还要看上边和左边的长度,所以这里要判断一下)int curSide = Math.min(dp[i][j][0], dp[i][j][1]);//如果边长小于maxSide,即使找到了也不可能再比maxSide大,所以我们没必要再找,直接跳过,if (curSide <= maxSide)continue;//curSide可以认为是正方形下边和右边的长度,我们还需要根据正方形上边和左边的长度//来确认是否满足正方形的条件for (; curSide > maxSide; curSide--) {//判断正方形的左边和上边的长度是否大于curSide,如果不大于,我们就缩小正方形//的长度curSide,然后继续判断if (dp[i][j - curSide + 1][1] >= curSide && dp[i - curSide + 1][j][0] >= curSide) {maxSide = curSide;//更短的就没必要考虑了,这里直接中断break;}}}}//返回正方形的边长return maxSide * maxSide;
}
复杂度分析
- 时间复杂度:O(m×n×min(m,n)),其中 m 表示矩阵的行数,n 表示矩阵的列数。
- 空间复杂度:O(m×n),其中 m 表示矩阵的行数,n 表示矩阵的列数。需要保存矩阵中每个位置的最长连续1的数目,需要的空间为 O(m×n)。
二、只是包含1的最大正方形
221. 最大正方形
在一个由 '0'
和 '1'
组成的二维矩阵内,找到只包含 '1'
的最大正方形,并返回其面积。
2.1 暴力求解
由于正方形的面积等于边长的平方,因此要找到最大正方形的面积,首先需要找到最大正方形的边长,然后计算最大边长的平方即可。
暴力法是最简单直观的做法,具体做法如下:
- 遍历矩阵中的每个元素,每次遇到 1,则将该元素作为正方形的左上角;
- 确定正方形的左上角后,根据左上角所在的行和列计算可能的最大正方形的边长(正方形的范围不能超出矩阵的行数和列数),在该边长范围内寻找只包含 1 的最大正方形;
- 每次在下方新增一行以及在右方新增一列,判断新增的行和列是否满足所有元素都是 1。
package matrix;/*** @Classname 最大的正方形221* @Description TODO* @Date 2023/2/17 7:50* @Created by xjl*/
public class 最大的正方形221 {public int maximalSquare(char[][] matrix) {int maxSide=0;if (matrix==null||matrix.length==0||matrix[0].length==0){return maxSide;}int rows=matrix.length,colums=matrix[0].length;for (int i=0;i<rows;i++){for (int j=0;j<colums;j++){if (matrix[i][j]=='1'){// 遇到一个 1 作为正方形的左上角maxSide=Math.max(maxSide,1);// 计算可能的最大正方形边长 剩下的矩阵中的最大的正方形int currentMaxSide=Math.min(rows-i,colums-j);for (int k = 1; k < currentMaxSide; k++) {// 判断新增的一行一列是否均为 1boolean flag = true;// 判断是下一行和下一列是否为0 判断所有的对角线的元素 如果有存在的那就判断其他的四条边if (matrix[i + k][j + k] == '0') {break;}for (int m = 0; m < k; m++) {if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {flag = false;break;}}if (flag) {maxSide = Math.max(maxSide, k + 1);} else {break;}}}}}int maxSquare = maxSide * maxSide;return maxSquare;}
}
2.2 动态规划求解
可以使用动态规划降低时间复杂度。我们用 dp(i,j) 表示以 (i,j) 为右下角,且只包含1的正方形的边长最大值。如果我们能计算出所有dp(i,j) 的值,那么其中的最大值即为矩阵中只包含1的正方形的边长最大值,其平方即为最大正方形的面积。
那么如何计算 dpdp 中的每个元素值呢?对于每个位置 (i,j)(i,j),检查在矩阵中该位置的值:
- 如果该位置的值是 0,则 dp(i,j)=0,因为当前位置不可能在由 1 组成的正方形中;
- 如果该位置的值是 1,则 dp(i,j)的值由其上方、左方和左上方的三个相邻位置的dp值决定。具体而言,当前位置的元素值等于三个相邻位置的元素中的最小值加1,状态转移方程如下:
此外,还需要考虑边界条件。如果 i 和 j 中至少有一个为0,则以位置 (i,j)为右下角的最大正方形的边长只能是 1,因此 dp(i,j)=1。
class Solution {public int maximalSquare(char[][] matrix) {int maxSide = 0;if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return maxSide;}int rows = matrix.length, 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(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;}maxSide = Math.max(maxSide, dp[i][j]);}}}int maxSquare = maxSide * maxSide;return maxSquare;}
}
复杂度分析
- 时间复杂度:O(mn),其m 和 n是矩阵的行数和列数。需要遍历原始矩阵中的每个元素计算dp的值。
- 空间复杂度:O(mn),其中 m和n是矩阵的行数和列数。创建了一个和原始矩阵大小相同的矩阵 dp。由于状态转移方程中的 dp(i,j)由其上方、左方和左上方的三个相邻位置的 dp值决定,因此可以使用两个一维数组进行状态转移,空间复杂度优化至O(n)。
博文参考
《leetcode》
相关文章:
Leetcode(每日一题)——1139. 最大的以 1 为边界的正方形
摘要 1139. 最大的以 1 为边界的正方形 一、以1为边界的最大正方形 1.1 动态规划 第530题需要正方形所有网格中的数字都是1,只要搞懂动态规划的原理,代码就非常简洁。而这题只要正方形4条边的网格都是1即可,中间是什么数字不用管。 这题…...
YOLOv5:GitHub两万八Star项目
来源:投稿 作者:王同学 编辑:学姐 Yolov5详解 官方源码仓库:https://github.com/ultralytics/yolov5 相关论文:未发表(改进点都被你们抢先发了) 0 前言 截止到2022年7月,Yolov5项…...
袋鼠云产品功能更新报告04期丨2023年首次,产品升级“狂飙”
新的一年我们加紧了更新迭代的速度,增加了数据湖平台EasyLake和大数据基础平台EasyMR,超40项功能升级优化。我们将继续保持产品升级节奏,满足不同行业用户的更多需求,为用户带来极致的产品使用体验。 以下为袋鼠云产品功能更新报…...
如何在Power Virtual Agents中使用Power Automate
今天我们来介绍一下如何在Power Virtual Agents中使用PowerAutomate。我们以通过在PVA聊天机器人的对话框中输入“发布通知”后会把预设好的通知信息自动发布到Teams中的某个团队中为例。首先进入PVA聊天机器人编辑界面后选择“主题”-“新建主题”。 在“新建主题”中添加“触…...
BXC6332A第二代智能头盔方案助力电动车市场,为安全保驾护航
随着2020年6月1日起,公安部交管局在全国开展“一盔一带”安全守护行动,摩托车、电动车驾驶人乘车人按照规定正确使用头盔,是保障司乘安全的一道重要屏障,据统计,摩托车、电动自行车驾乘人员死亡事故中约80%为颅脑损伤致…...
浮点数值计算精度丢失问题剖析及解决方法
文章目录1、原因分析2、解决方法2.1、Java中使用 BigDecimal 类2.2、JavaScript 中解决计算精度丢失的问题3、使用建议1、原因分析 首先我们来看个反直觉的浮点数值计算 System.out.println(0.3*3);有的同学可能要问为啥不是0.9? 首先要知道为什么会产生这个问题…...
字符串匹配 - 模式预处理:朴素算法(Naive)(暴力破解)
朴素的字符串匹配算法又称为暴力匹配算法(Brute Force Algorithm),最为简单的字符串匹配算法。算法简介朴素的字符串匹配算法又称为暴力匹配算法(Brute Force Algorithm),它的主要特点是:没有预…...
CVE-2021-42278 CVE-2021-42287域内提权漏洞
漏洞介绍2021 年 11 月 9 日,国外研究员在推特上发布了AD相关的 CVE,CVE-2021-42278 & CVE-2021-42287 ,两个漏洞组合可导致域内普通用户权限提升至域管权限。CVE-2021-42278:是一个安全绕过漏洞,允许通过修改机器…...
关于IcmpSendEcho2的使用和回调问题
由于我的需求是短时间内ping多台机子,所以需要异步执行,微软提供的例子是同步方式的,根据微软官方提供的icmpSendEcho2 函数的信息 ,我需要定义一个空的宏PIO_APC_ROUTINE_DEFINED ,定义完之后,编译又出现…...
XQuery 术语
在 XQuery 中,有七种节点:元素、属性、文本、命名空间、处理指令、注释、以及文档节点(或称为根节点)。 XQuery 术语 节点 在 XQuery 中,有七种节点:元素、属性、文本、命名空间、处理指令、注释、以及文…...
会议论文分享-Security22-状态感知符号执行
Ferry: State-Aware Symbolic Execution for Exploring State-Dependent Program Paths1.引言2.问题陈述与分析2.1.实现状态感知符号执行的挑战2.2.真实程序的特征2.3.Ferry的模型2.3.1.程序状态的定义2.3.2.状态描述变量的特征3.Design3.1.Overview of Ferry3.2.状态描述变量识…...
吴恩达深度学习笔记(八)——卷积神经网络(上)
一、卷积相关 用一个ff的过滤器卷积一个nn的图像,假如padding为p,步幅为s,输出大小则为: [n2p−fs1][n2p−fs1][\frac{n2p-f}{s}1][\frac{n2p-f}{s}1][sn2p−f1][sn2p−f1] []表示向下取整(floor) 大部分深度学习…...
14 基数排序(桶排序)
文章目录1 基数排序基本思想2 基数排序的代码实现2.1 java2.2 scala3 基数排序总结1 基数排序基本思想 1) 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort&#…...
汉明距离Java解法
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。 给你两个整数 x 和 y,计算并返回它们之间的汉明距离。 例: 输入:x 1, y 4 输出:2 解释: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上…...
Netty服务端请求接受过程源码剖析
目标 服务器启动后,客户端进行连接,服务器端此时要接受客户端请求,并且返回给客户端想要的请求,下面我们的目标就是分析Netty 服务器端启动后是怎么接受到客户端请求的。我们的代码依然与上一篇中用同一个demo, 用io.…...
金三银四春招特供|高质量面试攻略
🔰 全文字数 : 1万5千 🕒 阅读时长 : 20min 📋 关键词 : 求职规划、面试准备、面试技巧、谈薪职级 👉 公众号 : 大摩羯先生 本篇来聊聊一个老生常谈的话题————“面试”。利用近三周工作午休时间整理了这篇洋洋洒洒却饱含真诚…...
搭建Hexo博客-第4章-绑定自定义域名
搭建Hexo博客-第4章-绑定自定义域名 搭建Hexo博客-第4章-绑定自定义域名 搭建Hexo博客-第4章-绑定自定义域名 在这一篇文章中,我将会介绍如何给博客绑定你自己的域名。其实绑定域名本应该很简单的,但我当初在这上走了不少弯路,所以我觉得有…...
lightdb-sql拦截
文章目录LightDB - sql 审核拦截一 简介二 参数2.1 lightdb_sql_mode2.2 lt_firewall.lightdb_business_time三 规则介绍及使用3.1 select_without_where3.1.1 案例3.2 update_without_where/delete_without_where3.2.1 案例3.3 high_risk_ddl3.3.1 案例LightDB - sql 审核拦截…...
二进制中1的个数-剑指Offer-java位运算
一、题目描述编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 1 的个数(也被称为 汉明重量).)。提示:请注意,在某些语言(如 Java&…...
学自动化测试可以用这几个练手项目
练手项目的业务逻辑比较简单,只适合练手,不能代替真实项目。 学习自动化测试最难的是没有合适的项目练习。 测试本身既要讲究科学,又有艺术成分,单单学几个 api 的调用很难应付工作中具体的问题。 你得知道什么场景下需要添加显…...
2023年保健饮品行业分析:市场规模不断攀升,年度销额增长近140%
随着人们健康意识的不断增强,我国保健品市场需求持续增长,同时,保健饮品的市场规模也在不断攀升。 根据鲸参谋电商数据显示,2022年度,京东平台上保健饮品的年度销量超60万件,同比增长了约124%;该…...
2023-02-17 学习记录--TS-邂逅TS(一)
TS-邂逅TS(一) 不积跬步,无以至千里;不积小流,无以成江海。💪🏻 一、TypeScript在线编译器 https://www.typescriptlang.org/play/ 二、类型 1、普通类型 number(数值型ÿ…...
SpringMVC创建异步回调请求的4种方式
首先要明确一点,同步请求和异步请求对于客户端用户来讲是一样的,都是需客户端等待返回结果。不同之处在于请求到达服务器之后的处理方式,下面用两张图解释一下同步请求和异步请求在服务端处理方式的不同:同步请求异步请求两个流程…...
MySQL(二)表的操作
一、创建表 CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎; 说明: field 表示列名 datatype 表示列的类型 character set 字符集,如…...
SpringCloud - 入门
目录 服务架构演变 单体架构 分布式架构 分布式架构要考虑的问题 微服务 初步认识 案例Demo 服务拆分注意事项 服务拆分示例 服务调用 服务架构演变 单体架构 将业务的所有功能集中在一个项目中开发,打成一个包部署优点: 架构简单部署成本低缺…...
进一步了解C++函数的各种参数以及重载,了解C++部分的内存模型,C++独特的引用方式,巧妙替换指针,初步了解类与对象。满满的知识,希望大家能多多支持
C的编程精华,走过路过千万不要错过啊!废话少说,我们直接进入正题!!!! 函数高级 C的函数提高 函数默认参数 在C中,函数的形参列表中的形参是可以有默认值的。 语法:返…...
Chapter6:机器人SLAM与自主导航
ROS1{\rm ROS1}ROS1的基础及应用,基于古月的课,各位可以去看,基于hawkbot{\rm hawkbot}hawkbot机器人进行实际操作。 ROS{\rm ROS}ROS版本:ROS1{\rm ROS1}ROS1的Melodic{\rm Melodic}Melodic;实际机器人:Ha…...
Sass的使用要点
Sass 是一个 CSS 预处理器,完全兼容所有版本的 CSS。实际上,Sass 并没有真正为 CSS 语言添加任何新功能。只是在许多情况下可以可以帮助我们减少 CSS 重复的代码,节省开发时间。 一、注释 方式一:双斜线 // 方式二:…...
计算机启动过程,从按下电源按钮到登录界面的详细步骤
1、背景 自接触计算机以来,一直困扰着我一个问题。当我们按下电脑的开机键后,具体发生了哪些过程呢?计算机启动的具体步骤是什么? 计算机启动过程通常分为五个步骤:电源自检、BIOS自检、引导设备选择、引导程序加载和…...
LeetCode 刷题之 BFS 广度优先搜索【Python实现】
1. BFS 算法框架 BFS:用来搜索 最短路径 比较合适,如:求二叉树最小深度、最少步数、最少交换次数,一般与 队列 搭配使用,空间复杂度比 DFS 大很多DFS:适合搜索全部的解,如:寻找最短…...
杭州投资公司自适应网站/网络营销好不好
量子计算机!又是一个令人生畏的新概念,也是一个令人期待的革命性技术,他的出现将使得大数据分析成为真正的大数据分析。量子计算的概念源于海外,所以我们还是来看一看老外怎么说的。1.1.量子物理学量子物理学是现代科学最成功的系…...
免费微网站开发平台/免费打广告平台有哪些
一、什么是反射 java 运行时,识别对象和类的信息的传统方式是 RTTI,它要求我们再编译阶段就确定所以对象的信息,比如,如何去构造它,参数是什么...而反射机制则是在运行阶段去确认这些信息。 二、反射的实现 简单的例子…...
重庆百度网站推广/深圳网站快速排名优化
1.创建docker daemon.json sudo mkdir -p /etc/docker 2.添加docker镜像加速地址 sudo tee /etc/docker/daemon.json <<-EOF {"registry-mirrors": ["https://阿里云镜像加速地址.mirror.aliyuncs.com"] } EOF 3.重启守护进程 sudo systemct…...
集宁有做蒙古黑石材网站的嘛/百度搜索引擎服务项目
list3 list1 list2print(list3) # 不去重只进行两个列表的组合print(set(list3)) # 去重,类型为set需要转换成listprint(list(set(list3)))15、随机生成验证码的两种方式import randomlist1[]fori in range( 65, 91):list1.append( chr(i)) #通过for循环遍历asii追加到空列表…...
做网站备案是个人还是企业好/品牌策划公司介绍
本教程为大家共享了Linux安装MySQL具体步骤,供大家参考,详细内容如下第一步:下载MySQL安装包进入mysql官方网站,进入download界面,选择自己需要的版本和操作系统,我的电脑是Centos 7。我这里操作系统选择li…...
网站建设网站制作价格/今日热点事件
我们再登录账号密码的时候,账号可以回显在屏幕上,但是对于比较隐私的项目例如密码最好是不要再屏幕上回显。就像我们再终端登录linux服务器的时候,输入信息的时候只显示用户名,而不显示登录密码。以下是Python代码对比:…...