【力扣-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)。实现这些目标最终会改善世界各地许多人的生活。这些目标并不是相互独立的。所以,在某些目标上的积极收获通常是有影响的(积极的或消极的,有时两者都有)。这种相互联系使…...
石家庄建设局官方网站/网页搜索优化seo
我们通常使用cin和>>来输入字符或数字,但有时会出现问题,比如cin遇到空格就会停止,如果我们想输入带空格的字符串,比如"Hello World!",它就只能读取到Hello,如下所示: #includ…...
你对网站第一印象/免费推广软件下载
第10章 HBase:Hadoop数据库 10.3 HBase安装与配置 HBase服务规划 机器名HMasterHRegionServerZookeepernode1YYYnode2YYYnode3NYY 注意,如果集群较大,HMaster可以大于2。 首先通过物理机(Windows系统)下载HBase软件…...
i网站制作/潍坊网站收录
c#中的三种用法: 1.忽略转义字符 \ string str "C:\\windows\\system32"; string str "C:\windows\system32"; 2.字符串跨行 string str "line one" "line two" "line three" "line fore"; …...
wordpress爆路径/湖南百度seo排名点击软件
自媒体还能赚钱么? 疫情的影响导致大部分人的收入出现了问题,不得不想办法另谋出路。自媒体这半年越来越热,成为更多人副业的首选。 自媒体怎么做才能持久变现?这些是做好自媒体的前提 这里呢,凯哥先给大家泼盆冷水…...
深圳网站设计设计/山东济南seo整站优化公司
Android 基于4.4系统截屏的三指截屏Android5.0屏幕截屏与屏幕录制Android多媒体二:Android 5.0新增的屏幕捕捉系统级实时传输Android屏幕截图(实时抓图)并实现PC端控制(免ROOT)EasyPusher实现Android手机屏幕桌面直播,实时推送操作画面,用于手游直播等应用minicap, …...
最简洁wordpress主题/微信推广引流平台
前言 继续ctf的旅程 攻防世界Misc高手进阶区的3分题 本篇是misc_pic_again的writeup 发现攻防世界的题目分数是动态的 就仅以做题时的分数为准了 解题过程 下下来一个png 扔进winhex 无果 扔进stegsolve 发现压缩包 解压得到一个无后缀文件 扔进winhex 得到flag 结语 e…...