当前位置: 首页 > news >正文

【1139. 最大的以 1 为边界的正方形】

来源:力扣(LeetCode)

描述:

给你一个由若干 01 组成的二维网格 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 的正方形。
1

我们只需要求出以 (x, y) 为起点四个方向上连续 1 的数目,枚举边长 l 即可求出以 (x, y) 为右下顶点构成的边界为 1 的最大正方形,此时我们可以求出矩阵中边界为 1 的最大正方形。

本题即转换为求矩阵中任意位置 (x, y) 为起点上下左右四个方向连续 1 的最大数目,此时可以利用动态规划:

  • 如果当前 grid[x][x] = 0 此时,四个方向的连续 1 的长度均为 0;

  • 如果当前 grid[x][x] = 1 此时,四个方向的连续 1 的最大数目分别等于四个方向上前一个位置的最大数目加 1,计算公式如下:

2

在实际计算过程中我们可以进行优化,不必全部计算出四个方向上的最大连续 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 为边界的正方形】

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

windows11安装sqlserver2022报错

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

Python快速上手系列--日志模块--详解篇

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

【THREE.JS学习(1)】绘制一个可以旋转、放缩的立方体

学习新技能&#xff0c;做一下笔记。在使用ThreeJS的时候&#xff0c;首先创建一个场景const scene new THREE.Scene();接着&#xff0c;创建一个相机其中&#xff0c;THREE.PerspectiveCamera&#xff08;&#xff09;四个参数分别为&#xff1a;1.fov 相机视锥体竖直方向视野…...

数仓实战 - 滴滴出行

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

python虚拟环境与环境变量

一、环境变量 1.环境变量 在命令行下&#xff0c;使用可执行文件&#xff0c;需要来到可执行文件的路径下执行 如果在任意路径下执行可执行文件&#xff0c;能够有响应&#xff0c;就需要在环境变量配置 2.设置环境变量 用户变量&#xff1a;当前用户登录到系统&#xff0c;…...

BeautifulSoup文档4-详细方法 | 用什么方法对文档树进行搜索?

4-详细方法 | 用什么方法对文档树进行搜索&#xff1f;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语句面试题&#xff0c;关于group by表内容&#xff1a; 3.表中有A B C三列,用SQL语句实现&#xff1a;当A列大于B列时选择A列否则选择B列&#xff0c;当B列大于C列时选择B列否则选择C列 4. 5.姓名&#xff1a;name 课程&#xff1a;subject 分数&…...

VS实用调试技巧

一.什么是BUG&#x1f41b;Bug一词的原意是虫子&#xff0c;而在电脑系统或程序中隐藏着的一些未被发现的缺陷或问题&#xff0c;人们也叫它"bug"。这是为什么呢&#xff1f;这就要追溯到一个程序员与飞蛾的故事了。Bug的创始人格蕾丝赫柏&#xff08;Grace Murray H…...

通俗易懂理解三次握手、四次挥手(TCP)

文章目录1、通俗语言理解1.1 三次握手1.2 四次挥手2、进一步理解三次握手和四次挥手2.1 三次握手2.2 四次挥手1、通俗语言理解 1.1 三次握手 C:客户端 S&#xff1a;服务器端 第一次握手&#xff1a; C&#xff1a;在吗&#xff1f;我要和你建立连接。 第二次握手&#xff…...

1.1 什么是并发

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

万字讲解你写的代码是如何跑起来的?

今天我们来思考一个简单的问题&#xff0c;一个程序是如何在 Linux 上执行起来的&#xff1f; 我们就拿全宇宙最简单的 Hello World 程序来举例。 #include <stdio.h> int main() {printf("Hello, World!\n");return 0; } 我们在写完代码后&#xff0c;进行…...

034.Solidity入门——21不可变量

Solidity 中的不可变量是在编译时就被确定的常量&#xff0c;也称为常量变量&#xff08;constant variable&#xff09;或只读变量&#xff08;read-only variable&#xff09;。这些变量在定义时必须立即初始化&#xff0c;并且在整个合约中都无法被修改&#xff0c;可以在函…...

Vulnhub 渗透练习(四)—— Acid

环境搭建 环境下载 kail 和 靶机网络适配调成 Nat 模式&#xff0c;实在不行直接把网络适配还原默认值&#xff0c;再重试。 信息收集 主机扫描 没扫到&#xff0c;那可能端口很靠后&#xff0c;把所有端口全扫一遍。 发现 33447 端口。 扫描目录&#xff0c;没什么有用的…...

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 的目标检测开源工具箱&#xff0c;它是 OpenMMLab 项目的一部分。包含以下主要特性&#xff1a; 支持三个任务 目标检测&#xff08;Object Detection&#xff09;是指分类并定位图片中物体的任务实例分割&#xff08;Instance Segmentation&a…...

使用ThreadLocal实现当前登录信息的存取

有志者&#xff0c;事竟成 文章持续更新&#xff0c;可以关注【小奇JAVA面试】第一时间阅读&#xff0c;回复【资料】获取福利&#xff0c;回复【项目】获取项目源码&#xff0c;回复【简历模板】获取简历模板&#xff0c;回复【学习路线图】获取学习路线图。 文章目录一、使用…...

高通平台开发系列讲解(Android篇)AudioTrack音频流数据传输

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

BUUCTF-firmware1

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

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

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兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用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面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...