【1139. 最大的以 1 为边界的正方形】
来源:力扣(LeetCode)
描述:
给你一个由若干 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
方法:动态规划
思路与算法
我们假设以 (x, y) 为右下方顶点的最大的正方形边长为 l,此时正方形的四个顶点分别为 (x − l + 1, y − l + 1), (x, y − l + 1), (x − l + 1, y), (x, y),此时需要保证正方形的四条边上的数字均为 1。我们设 left[x][y] 表示以 (x, y) 为起点左侧连续 1 的最大数目,right[x][y] 表示以 (x, y) 为起点右侧连续 1 的最大数目,up[x][y] 表示从 (x, y) 为起点上方连续 1 的最大数目,down[x][y] 表示以 (x, y) 为起点下方连续 1 的最大数目。此时正方形的四条边中以四个顶点为起点的连续 1 的数目分别为:上侧边中以 (x − l + 1, y − l + 1) 为起点连续 1 数目为 right[x − l + 1][y − l + 1],左侧边中以 (x − l + 1, y − l + 1) 为起点连续 1 的数目为 down[x − l + 1][y − l + 1],右侧边中以 (x, y) 为起点连续 1 的数目为 up[x][y],下侧边中以 (x,y) 为起点连续 1 的数目为 left[x][y]。
如果连续 1 的数目大于等于 l,则构成一条「合法」的边,如果正方形的四条边均「合法」,此时一定可以构成边界全为 1 且边长为 l 的正方形。
我们只需要求出以 (x, y) 为起点四个方向上连续 1 的数目,枚举边长 l 即可求出以 (x, y) 为右下顶点构成的边界为 1 的最大正方形,此时我们可以求出矩阵中边界为 1 的最大正方形。
本题即转换为求矩阵中任意位置 (x, y) 为起点上下左右四个方向连续 1 的最大数目,此时可以利用动态规划:
-
如果当前 grid[x][x] = 0 此时,四个方向的连续 1 的长度均为 0;
-
如果当前 grid[x][x] = 1 此时,四个方向的连续 1 的最大数目分别等于四个方向上前一个位置的最大数目加 1,计算公式如下:
在实际计算过程中我们可以进行优化,不必全部计算出四个方向上的最大连续 1 的数目,可以进行如下优化:
只需要求出每个位置 (x, y) 为起点左侧连续 1 的最大数目 left[x][y] 与上方连续 1 的最大数目 up[x][y] 即可。假设当前正方形的边长为 l,此时只需检测 up[x][y], left[x][y], left[x − l + 1][y], up[x][y − l + 1] 是否均满足大于等于 l 即可检测正方形的合法性。
枚举正方形的边长时可以从大到小进行枚举,我们已经知道以 (x, y) 为起点左侧连续 1 的最大数目 left[x][y] 与上方连续 1 的最大数目 up[x][y],此时能够成正方形的边长的最大值一定不会超过二者中的最小值 min(left[x][y], up[x][y]),从大到小枚举直到可以构成“合法”的正方形即可。
代码:
class Solution {
public:int largest1BorderedSquare(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> left(m + 1, vector<int>(n + 1));vector<vector<int>> up(m + 1, vector<int>(n + 1));int maxBorder = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (grid[i - 1][j - 1] == 1) {left[i][j] = left[i][j - 1] + 1;up[i][j] = up[i - 1][j] + 1;int border = min(left[i][j], up[i][j]);while (left[i - border + 1][j] < border || up[i][j - border + 1] < border) {border--;}maxBorder = max(maxBorder, border);}}}return maxBorder * maxBorder;}
};
执行用时:8 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:11.4 MB, 在所有 C++ 提交中击败了54.29%的用户
复杂度分析
时间复杂度:O(m × n × min(m, n)),其中 m 表示矩阵的行数,n 表示矩阵的列数。
空间复杂度:O(m × n),其中 m 表示矩阵的行数,n 表示矩阵的列数。需要保存矩阵中每个位置的最长连续 1 的数目,需要的空间为 O(m × n)。
author:LeetCode-Solution
相关文章:

【1139. 最大的以 1 为边界的正方形】
来源:力扣(LeetCode) 描述: 给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。 示例 1&#…...

windows11安装sqlserver2022报错
window11安装SQL Server 2022 报错 糟糕… 无法安装SQL Server (setup.exe)。此 SQL Server安装程序介质不支持此OS的语言,或没有SQL Server英语版本的安装文件。请使用匹配的特定语言SQL Server介质;或安装两个特定语言MUI,然后通过控制面板的区域设置…...

Python快速上手系列--日志模块--详解篇
前言本篇主要说说日志模块,在写自动化测试框架的时候我们就需要用到这个模块了,方便我们快速的定位错误,了解软件的运行情况,更加顺畅的调试程序。为什么要用到日志模块,直接print不就好了!那得写多少print…...

【THREE.JS学习(1)】绘制一个可以旋转、放缩的立方体
学习新技能,做一下笔记。在使用ThreeJS的时候,首先创建一个场景const scene new THREE.Scene();接着,创建一个相机其中,THREE.PerspectiveCamera()四个参数分别为:1.fov 相机视锥体竖直方向视野…...

数仓实战 - 滴滴出行
项目大致流程: 1、项目业务背景 1.1 目的 本案例将某出行打车的日志数据来进行数据分析,例如:我们需要统计某一天订单量是多少、预约订单与非预约订单的占比是多少、不同时段订单占比等 数据海量 – 大数据 hive比MySQL慢很多 1.2 项目架…...

python虚拟环境与环境变量
一、环境变量 1.环境变量 在命令行下,使用可执行文件,需要来到可执行文件的路径下执行 如果在任意路径下执行可执行文件,能够有响应,就需要在环境变量配置 2.设置环境变量 用户变量:当前用户登录到系统,…...
BeautifulSoup文档4-详细方法 | 用什么方法对文档树进行搜索?
4-详细方法 | 用什么方法对文档树进行搜索?1 过滤器1.1 字符串1.2 正则表达式1.3 列表1.4 True1.5 可以自定义方法2 find_all()2.1 参数原型2.2 name参数2.3 keyword 参数2.4 string 参数2.5 limit 参数2.6 recursive 参数3 find()4 find_parents()和find_parent()5…...
初识Tkinter界面设计
目录 前言 一、初识Tkinter 二、Label控件 三、Button控件 四、Entry控件 前言 本文简单介绍如何使用Python创建一个界面。 一、初识Tk...

软件测试面试题中的sql题目你会做吗?
目录 1.学生表 2.一道SQL语句面试题,关于group by表内容: 3.表中有A B C三列,用SQL语句实现:当A列大于B列时选择A列否则选择B列,当B列大于C列时选择B列否则选择C列 4. 5.姓名:name 课程:subject 分数&…...

VS实用调试技巧
一.什么是BUG🐛Bug一词的原意是虫子,而在电脑系统或程序中隐藏着的一些未被发现的缺陷或问题,人们也叫它"bug"。这是为什么呢?这就要追溯到一个程序员与飞蛾的故事了。Bug的创始人格蕾丝赫柏(Grace Murray H…...

通俗易懂理解三次握手、四次挥手(TCP)
文章目录1、通俗语言理解1.1 三次握手1.2 四次挥手2、进一步理解三次握手和四次挥手2.1 三次握手2.2 四次挥手1、通俗语言理解 1.1 三次握手 C:客户端 S:服务器端 第一次握手: C:在吗?我要和你建立连接。 第二次握手ÿ…...

1.1 什么是并发
1.1 什么是并发 并发:指两个或更多独立的活动同时发生。并发在生活中随处可见。我们可以一边走路一边说话,也可以两只手同时做不同的动作。 1.1.1 计算机系统中的并发 当我们提到计算机术语的“并发”,指的是在单个系统里同时执行多个独立…...

万字讲解你写的代码是如何跑起来的?
今天我们来思考一个简单的问题,一个程序是如何在 Linux 上执行起来的? 我们就拿全宇宙最简单的 Hello World 程序来举例。 #include <stdio.h> int main() {printf("Hello, World!\n");return 0; } 我们在写完代码后,进行…...
034.Solidity入门——21不可变量
Solidity 中的不可变量是在编译时就被确定的常量,也称为常量变量(constant variable)或只读变量(read-only variable)。这些变量在定义时必须立即初始化,并且在整个合约中都无法被修改,可以在函…...

Vulnhub 渗透练习(四)—— Acid
环境搭建 环境下载 kail 和 靶机网络适配调成 Nat 模式,实在不行直接把网络适配还原默认值,再重试。 信息收集 主机扫描 没扫到,那可能端口很靠后,把所有端口全扫一遍。 发现 33447 端口。 扫描目录,没什么有用的…...
C++ 在线工具
online编译器https://godbolt.org/Online C Compiler - online editor (onlinegdb.com) https://www.onlinegdb.com/online_c_compilerC Shell (cpp.sh) https://cpp.sh/在线文档Open Standards (open-std.org)Index of /afs/cs.cmu.edu/academic/class/15211/spring.96/wwwC P…...

使用MMDetection进行目标检测、实例和全景分割
MMDetection 是一个基于 PyTorch 的目标检测开源工具箱,它是 OpenMMLab 项目的一部分。包含以下主要特性: 支持三个任务 目标检测(Object Detection)是指分类并定位图片中物体的任务实例分割(Instance Segmentation&a…...

使用ThreadLocal实现当前登录信息的存取
有志者,事竟成 文章持续更新,可以关注【小奇JAVA面试】第一时间阅读,回复【资料】获取福利,回复【项目】获取项目源码,回复【简历模板】获取简历模板,回复【学习路线图】获取学习路线图。 文章目录一、使用…...

高通平台开发系列讲解(Android篇)AudioTrack音频流数据传输
文章目录 一、音频流数据传输通道创建1.1、流程描述1.2、流程图解二、音频数据传输2.1、流程描述2.2、流程图解沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇章主要图解AudioTrack音频流数据传输 。 一、音频流数据传输通道创建 1.1、流程描述 AudioTrack在set函…...

BUUCTF-firmware1
题目下载:下载 新题型,记录一下 题目给出了flag形式,md5{网址:端口},下载发现是一个.bin文件 二进制文件,其用途依系统或应用而定。一种文件格式binary的缩写。一个后缀名为".bin"的文件&#x…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...

2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...