【力扣-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 上的精选热门应用类型:热门游戏或应用,畅销应用,安装量增长的应用,产生最多收入的应用。 那么…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权
摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题:安全。文章将详细阐述认证(Authentication) 与授权(Authorization的核心概念,对比传统 Session-Cookie 与现代 JWT(JS…...
