【力扣-LeetCode】1139. 最大的以 1 为边界的正方形 C++题解
1139. 最大的以 1 为边界的正方形
难度中等137收藏分享切换为英文接收动态反馈
给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。
示例 1:
输入:grid = [[1,1,1],[1,0,1],[1,1,1]]
输出:9
示例 2:
输入:grid = [[1,1,0,0]]
输出:1
提示:
1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为 0 或 1
解题思路:以正方形周长的路径扫描每个子网格;
以当前坐标(i,j)为起点,L为边长,扫描一个正方形的周长,判断是否构成一个正方形,并不断更新maxL(当前的最大边长);
最后返回maxL*maxL即可。
AC代码:
class Solution {
public:bool hasSquare(int SI,int SJ,int L,vector<vector<int>>& grid){// 扫描顺序:上、右、下、左for(int k=0;k<4;k++){if(k==0){//上边for(int m=0;m<L;m++){if(SJ<0 || SJ>=grid[0].size())return false;if(grid[SI][SJ]!=1)return false;if(m<L-1)SJ++;}}if(k==1){//右边for(int m=0;m<L;m++){if(SI<0 || SI>=grid.size())return false;if(grid[SI][SJ]!=1)return false;if(m<L-1)SI++;}}if(k==2){//下边for(int m=0;m<L;m++){if(SJ<0 || SJ>=grid[0].size())return false;if(grid[SI][SJ]!=1)return false;if(m<L-1)SJ--;}}if(k==3){//左边for(int m=0;m<L;m++){if(SI<0 || SI>=grid.size())return false;if(grid[SI][SJ]!=1)return false;if(m<L-1)SI--;}} }return true;}int largest1BorderedSquare(vector<vector<int>>& grid) {if(grid.size()==1){for(int i=0;i<grid[0].size();i++){if(grid[0][i]==1)return 1;}return 0;}//解题思路:以正方形周长的路径扫描每个子网格int maxL=0;int row=grid.size(); //行数int col=grid[0].size(); //列数for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(grid[i][j]!=1)continue;int L=max(maxL,1);//以当前坐标(i,j)为起点,L为边长,扫描一个正方形的周长//判断是否构成一个正方形int LLen=min(row-i,col-j);bool isOk=false;for(;L<=LLen;L++){isOk=hasSquare(i,j,L,grid);if(isOk)maxL=max(L,maxL);} }}return maxL*maxL;}
};
相关文章:
【力扣-LeetCode】1139. 最大的以 1 为边界的正方形 C++题解
1139. 最大的以 1 为边界的正方形难度中等137收藏分享切换为英文接收动态反馈给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。示例 1…...
【JavaGuide面试总结】Redis篇·下
【JavaGuide面试总结】Redis篇下1.如何使用 Redis 事务?2.如何解决 Redis 事务的缺陷?3.说说Redis bigkey吧4.大量 key 集中过期问题怎么解决的5.如何保证缓存和数据库数据的一致性?6.缓存穿透有哪些解决办法?7.缓存击穿有哪些解决…...
ForkJoinPool原理
1、概述 Fork/Join框架是Java7提供了的一个用于并行执行任务的框架。ForkJoinPool是Java中提供了一个线程池,特点是用来执行分治任务。主题思想是将大任务分解为小任务,然后继续将小任务分解,直至能够直接解决为止,然后再依次将任…...
02 python基本语法和数据类型
基本语法 python脚本可以在python交互式shell或者代码编辑器中编写与运行。python文件的扩展名一般为.py python使用缩进来区分不同的代码块,此特性有利于提高代码可读性。 下面是一个简单的python条件语句代码: 小明=矮穷错 小红=白富美 小华=高富帅 小李=程序员某人 = &quo…...
【办公类-16-09】“2022下学期 大班运动场地分配表-跳过节日循环排序”(python 排班表系列)
样例展示:跳过节日的运动场地循环排序表(8个班级8组内容 下学期一共20周)背景需求:上学期做过一次大班运动场地安排,跳过节日。2023.2下学期运动场地排班(跳过节日)又来了。一、场地器械微调二、…...
全网多种方法分析解决HTTP Status 404资源未找到的错误,TCP的3次握手,dns域名解析,发起http请求以及cookie和session的区别
文章目录1. 文章引言2. 简述URL3. http完整请求3.1 DNS域名解析3.2 TCP的3次握手3.3 发起http请求3.4 浏览器解析html代码3.5 浏览器对页面进行渲染呈现给用户4. 解决404错误的方法5. 补充知识点5.1 cookie和session的区别5.2 ChatGPT的介绍1. 文章引言 正赶上最近ChatGPT很火…...
Django图书商场购物系统python毕业设计项目推荐
mysql数据库进行开发,实现了首页、个人中心、用户管理、卖家管理、图书类型管理、图书信息管理、订单管理、系统管理等内容进行管理,本系统具有良好的兼容性和适应性,为用户提供更多的网上图书商城信息,也提供了良好的平台&#x…...
基于模型预测控制(MPC)的悬架系统仿真分析
目录 前言 1.悬架系统 2.基于MPC的悬架系统仿真分析 2.1 simulink模型 2.2仿真结果 2.3 结论 3 总结 前言 模型预测控制是无人驾驶中较为热门的控制算法,但是对于悬架等这类系统的控制同样适用。 我们知道模型预测控制主要可以划分为三个部分: …...
Word处理控件Aspose.Words功能演示:使用 Java 拆分 MS Word 文档
Aspose.Words 是一种高级Word文档处理API,用于执行各种文档管理和操作任务。API支持生成,修改,转换,呈现和打印文档,而无需在跨平台应用程序中直接使用Microsoft Word。此外,API支持所有流行的Word处理文件…...
图扑数字孪生智慧机场,助推民航“四型机场“建设
前言 民航局印发的《智慧民航建设路线图》文件中,明确提出智慧机场是智慧民航的四个核心抓手之一。并从机场全域协同运行、作业与服务智能化、智慧建造与运维方面,为智慧机场的发展绘制了清晰的蓝图。 效果展示 图扑软件应用自主研发核心产品 HT for …...
内网安装管家婆软件如何实现外网访问?内网穿透的几种方案教程
管家婆软件从网络架构上分两种版本:web(浏览器http端口)访问的版本和客户端(211固定端口sqlserver数据库)访问的版本。公司库管经常用仓库登录管家婆,一旦需要在公司外部登陆访问管家婆客户端,就…...
CCNP350-401学习笔记(1-50题)
1、Which function does a fabric edge node perform in an SD-Access deployment?A. Connects endpoints to the fabric and forwards their traffic. B. Encapsulates end-user data traffic into LISP. C. Connects the SD-Access fabric to another fabric or external La…...
基于微信小程序的新冠肺炎服务预约小程序
文末联系获取源码 开发语言:Java 框架:ssm JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7/8.0 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包:Maven3.3.9 浏览器…...
网站项目部署在k8s案例与Jenkins自动化发布项目(CI/CD)
在K8s平台部署项目流程 在K8s平台部署Java网站项目 制作镜像流程 第一步:制作镜像 使用镜像仓库(私有仓库、公共仓库): 1、配置可信任(如果仓库是HTTPS访问不用配置) # vi /etc/docker/daemon.json { "…...
网络原理 (1)
网络原理 文章目录1. 前言: 2. 应用层2.1 XML2.2 json2.3 protobuffer3. 传输层3.1 UDP3.1 TCP4. TCP 内部的工作机制 (重点)1. 确认应答 2.超时重传3. 连接管理3.1 建立联系 :三次握手3.2 断开连接 : 四次挥手4. 滑动窗口5. 流量…...
LeetCode-1139. 最大的以 1 为边界的正方形【前缀和,矩阵】
LeetCode-1139. 最大的以 1 为边界的正方形【前缀和,矩阵】题目描述:解题思路一:前缀和。前缀和来记录边长。解题思路二:0解题思路三:0题目描述: 给你一个由若干 0 和 1 组成的二维网格 grid,请…...
windows10/11,傻瓜式安装pytorch(gpu),在虚拟环境anaconda
安装anaconda地址 :Anaconda | The Worlds Most Popular Data Science Platform安装选项全默认点击next就行。查看支持cuda版本cmd命令行输入nvidia-smi。下图右上角显示11.6为支持的cuda版本。要是显示没有nvidia-smi命令。得安装nvidia驱动,一般情况都…...
Revit导出PDF格式图纸流程及“批量导出图纸”
一、Revit导出PDF格式图纸流程 1、点击左上方“应用程序菜单”即“R”图标,进择“打印”选项。 2、在弹出的对话框中,需要设置图纸“打印范围”,选择“所选的视图/图纸选项”,点击“选择”,按钮,选择我们需…...
【自学Linux】 Linux文件目录结构
Linux文件目录结构 Linux文件目录结构教程 在 Linux 中,有一个很经典的说法,叫做一切皆文件,因此,我们在系统学习 Linux 之前,首先要了解 Linux 的文件目录结构。Linux 主要的目录有三大类,即根目录(/)&a…...
如何让APP在Google Play中成为特色
Google Play覆盖了 190 多个地区,数十亿的用户,所以开发者都会希望APP在应用商店中获得推荐位。 Google Play 上的精选热门应用类型:热门游戏或应用,畅销应用,安装量增长的应用,产生最多收入的应用。 那么…...
【C++】cin的处理过程
使用cin进行输入时,程序将输入视为一系列的字节,其中每个字节都被解释为字符编码。不管目标数据 类型是什么,输入一开始都是字符数据——文本数据。然后,cin对象负责将文本转换为其他类型。 为说明这是如何完成的,来看…...
读取Sentinel和Landsat 压缩包数据,直接进行波段重组、影像裁剪或者匀色镶嵌处理
波段重组在软件中查找:菜单栏-》影像基本处理-》波段处理-》波段重组,弹出如下对话框:根据对话框中的提示,输入需要处理的数据。注意:1、输入数据添加之后,需要点击其中任意一条数据,获取数据波…...
Yakit Web Fuzzer 终极能力强化:热加载 Fuzz
Background 在 HTB:BountyHunter 中,我们发现 Web Fuzzer 在使用中可以 “更强”,我们需要编写 Yak 脚本的事情,如果可以经过某些 Web Fuzzer 的优化,可以达到同样的效果。 在一个标签中,我们实现{{base6…...
Qt新手入门指南 - 如何创建模型/视图(三)
每个UI开发人员都应该了解ModelView编程,本教程的目标是为大家提供一个简单易懂的介绍。Qt 是目前最先进、最完整的跨平台C开发工具。它不仅完全实现了一次编写,所有平台无差别运行,更提供了几乎所有开发过程中需要用到的工具。如今ÿ…...
【Spring】手动实现简易AOP和IOC
前言 XML:通过Dom4j对XML进行解析和验证。 IOC:通过获取要创建对象的Class类型、构造函数后,通过反射来实现。 AOP:通过使用JDK动态代理和Cglib动态代理实现。 一、解析XML 1.1、解析bean标签 /*** 解析bean标签* param xmlBean…...
EasyExcel的使用
这里写目录标题先导入依赖最简单的写最简单的读項目开发中的一些操作xml一定要默認放先导入依赖 <dependencies><dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>2.1.7</version><…...
基础篇(-1)-java特点、JDK、JRE、JVM区别、字节码编译、跨平台、程序运行
文章目录1.Java的特点有哪些?2.JDK和JRE和JVM的区别3.Java为什么采用字节码编译?4.什么是跨平台?5.Java程序从源代码到运行需要三步?1.Java的特点有哪些? Java是一种编程语言,被特意设计用于互联网的分布式…...
【网络编程】Java快速上手InetAddress类
概念 Java具有较好的网络编程模型/库,其中非常重要的一个API便是InetAddress。在Java.net 网络编程中中有许多类都使用到了InetAddress 这个类代表一个互联网协议(IP)地址。 IP地址是一个32(IPV4)位或128(…...
小小bat-day1-自动文件上传
前言:日常服务器备份文件或者生产设备等数据文件都统一保存至文件服务器,进行日志分析或者将生产文件CSV、图片等转存至数仓进行数据分析,尤其生产的部分数据是保存在个人电脑的PC端,数据杂,获取困难,手动整…...
2023年美赛D题公布
问题D:联合国可持续发展目标的优先次序背景联合国制定了17项可持续发展目标(SDGs)。实现这些目标最终会改善世界各地许多人的生活。这些目标并不是相互独立的。所以,在某些目标上的积极收获通常是有影响的(积极的或消极的,有时两者都有)。这种相互联系使…...
最好的响应式网站有哪些/最常用的几个关键词
插入到表名(列值)后跟一个查询语句的话就代表值,简单的说就是后面select select出来的值就是要插入的值,即 insert into tb(字段名一,字段名二)select 字段名一,字段名二 from tb 等…...
科技馆网站建设方案/曹操博客seo
安装前说明: 本文将介绍在ubuntu16.04系统下安装和升级docker、docker-compose、docker-machine。 docker:有两个版本:docker-ce(社区版)和docker-ee(企业版)。 笔者这里介绍安装或升级的是最新版docker-ce(社区版)。 参考官网地址:https://docs.docker.…...
网站套餐报价 模版/成都公司建站模板
http://blog.csdn.net/wuxiaokaixinguo/article/details/8895187...
哪个网站可以做彩经专家/网络营销与电子商务的区别
引用自:http://www.cnblogs.com/anytao/category/155694.html 作者:Anytao 本文将介绍以下内容: • 类型转换 • is/as操作符小议 1. 引言 类型安全是.NET设计之初重点考虑的内容之一,对于程序设计者来说,完全把握系…...
郑州做网站托管/漯河搜狗关键词优化排名软件
我现在无法对其进行严格测试,但是从我发现的结果来看,以下方法可能有效:SQL语句SELECT rownum : rownum 1 rownum, t.*FROM ((SELECT t.id, t.name, c.company AS owner, t.creation_date AS date, t.notesFROM tool t, client cWHERE t.id_customer 15AND t.tras…...
怎么做网站企业文化栏目/怎么营销推广
题意:传送门 题解:分类如果按照codeforcescodeforcescodeforces上的话就是最朴素的implementionimplementionimplemention,但是却卡我半天,题意也是强调(一脸苦)得用四舍五入,那么四舍五入的小trick都有哪些呢…...