Leetcode.1139 最大的以 1 为边界的正方形
题目链接
Leetcode.1139 最大的以 1 为边界的正方形 Rating : 1744
题目描述
给你一个由若干 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<=1001 <= grid.length <= 1001<=grid.length<=100
- 1<=grid[0].length<=1001 <= grid[0].length <= 1001<=grid[0].length<=100
grid[i][j]
为 0 或 1
分析:
使用 dp 求解,我们定义 f(i,j,0)和f(i,j,1)f(i,j,0)和f(i,j,1)f(i,j,0)和f(i,j,1)分别为以点 (i,j)
结尾,向左 和 向上的连续 1
的个数。
在f(i,j,0)>0和f(i,j,1)>0f(i,j,0) > 0和f(i,j,1) > 0f(i,j,0)>0和f(i,j,1)>0 的情况下,我们取 d=min(f(i,j,0),f(i,j,1))d = min(f(i,j,0),f(i,j,1))d=min(f(i,j,0),f(i,j,1))。
遍历kkk (0<=k<=d)(0<=k<=d)(0<=k<=d),判断 f(i−k+1,j,0)>=k和f(i,j−k+1,1)>=kf(i-k+1,j,0) >= k 和 f(i,j-k+1,1) >= kf(i−k+1,j,0)>=k和f(i,j−k+1,1)>=k,如果条件成立,说明可以构成一个最后一点是 (i,j)
,边长为 k
的正方形。
时间复杂度:O(m∗n∗min(m∗n))O(m*n*min(m*n))O(m∗n∗min(m∗n))
C++代码:
class Solution {
public:int largest1BorderedSquare(vector<vector<int>>& grid) {int m = grid.size(),n = grid[0].size();int f[m+1][n+1][2];memset(f,0,sizeof f);int ans = 0;for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){//为1就记录if(grid[i-1][j-1]){f[i][j][0] = 1 + (j - 1 >= 1 ? f[i][j-1][0] : 0);f[i][j][1] = 1 + (i - 1 >= 1 ? f[i-1][j][1] : 0);}if(f[i][j][0] > 0 && f[i][j][1] > 0){int d = min(f[i][j][0],f[i][j][1]);//倒序判断能构成正方形的最大边长for(int k = d;k >= 0;k--){if(i-k+1 >= 1 && j-k+1 >= 1 && f[i-k+1][j][0] >= k && f[i][j-k+1][1] >= k){ans = max(ans,k*k);break;}}}}}return ans;}
};
Java代码:
class Solution {public int largest1BorderedSquare(int[][] grid) {int m = grid.length,n = grid[0].length;int[][][] f = new int[m+1][n+1][2];int ans = 0;for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){if(grid[i-1][j-1]==1){f[i][j][0] = 1 + (j - 1 >= 1 ? f[i][j-1][0] : 0);f[i][j][1] = 1 + (i - 1 >= 1 ? f[i-1][j][1] : 0);}if(f[i][j][0] > 0 && f[i][j][1] > 0){int d = Math.min(f[i][j][0],f[i][j][1]);for(int k = d;k >= 0;k--){if(i-k+1 >= 1 && j-k+1 >= 1 && f[i-k+1][j][0] >= k && f[i][j-k+1][1] >= k){ans = Math.max(ans,k*k);break;}}}}}return ans;}
}
相关文章:
Leetcode.1139 最大的以 1 为边界的正方形
题目链接 Leetcode.1139 最大的以 1 为边界的正方形 Rating : 1744 题目描述 给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。 如果不存在,则返回 0。…...

Bing+ChatGPT 对传统搜索引擎的降维打击
早些时候申请了新版 Bing 的内测资格,终于收到了通过的邮件。 一天的体验之后,我的感受是:当新版 Bing 具备了 ChatGPT 的聊天能力之后,它的能力不论是对传统搜索引擎,还是 ChatGPT 自身,都将是降维打击。 …...

【JS】数组常用方法总结-功能、参数、返回值
数组常用方法总结-功能、参数、返回值 用简单的js示例 运行在线工具:链接: 菜鸟工具 菜鸟工具示意图: pu…...
pytest 单元测试前后置处理
文章目录方法1 setup/teardown方法2 fixture 夹具方法3 conftest.py测试用例执行前后的一些处理动作,也叫夹具。以下介绍使用前后置操作的几种方法。方法1 setup/teardown setup,每个测试用例执行前要进行的处理。 teardown,每个测试用例执行…...

汽车安全硬件扩展 AUTOSAR SHE SecureHardwareExtensions
SHE(Secure Hardware Extension)在车联网中,被应用在车端ECU中负责安全存储与安全计算。是由HIS(由Audi、BMW、Porsche、Volkswagen组成)制定的标准,中文意思“安全硬件扩展”,是对任何给定微控…...

2023年美国大学生数学建模C题:预测Wordle结果建模详解+模型代码
目录 前言 一、题目理解 背景 解析 字段含义: 建模要求 二、建模思路 灰色预测: 编辑 二次指数平滑法: person相关性 只希望各位以后遇到建模比赛可以艾特认识一下我,我可以提供免费的思路和部分源码,以后…...

5、HAL库驱动W25Qxx
一、 SPI通信驱动W25Qxx 1、使用驱动文件快速配置工程代码驱动W25Qxx (此驱动文件只适合W25Qxx 16M及以下型号,因为访问地址位数不同) 注:本次使用SPI的方式进行访问W25Qxx Flash进行数据读写,关于W25Qxx芯片不会做…...
git rebase 洐合(变基)
洐合 把一个分支整合到另一个分支的办法有两种:merge(合并) 和 rebase(衍合) 为什么使用? 使提交记录更简洁 三种情况 第一种: 合并多条commit记录 git rebase -i HEAD~合并数量 HEAD~3&a…...

Kubernetes 1.18学习笔记
文章目录一、Kubernetes 概述和架构1、kubernetes 基本介绍2、Kubernetes 功能3、Kubernetes 架构组件4、Kubernetes 核心概念5、Kubernetes 工作原理二、Kubernetes 集群搭建1、系统环境准备1.1 安装要求1.2 系统初始化2、客户端工具kubeadm搭建2.1 安装步骤2.2 安装组件2.3 集…...

AJAX技术
AJAX技术 浏览器是多进程的,简单的说就是,浏览器每打开一个标签页,就相当于创建了一个独立的浏览器进程。但是js是基于单线程的,而这个线程就是浏览器的js引擎,浏览器无论在什么时候都只且只有一个线程在运行JavaScri…...
华为OD机试 - 最大排列(JS)
最大排列 题目 给定一组整数,重排序后输出一个最大的整数 输入 数字组合 输出 最大的整数 示例一 输入 10 9输出 910解题思路 我们可以读入一个字符串,将字符串中的单词按照每个单词的字典序长度,字典序从大到小的顺序排序&#x…...

Prometheus Docker安装及监控自身
前提环境: Docker环境 涉及参考文档: 安装Prometheus开始 Prometheusnode_exporter Agent组件 一、部署Prometheus 1、启动容器将文件拷贝出来 docker run -d prom/prometheus2、容器将文件拷贝出来 docker cp 容器ID:/usr/share/prometheus/conso…...
点云处理PCL常用函数与工具
点云处理PCL常用函数与工具 文章目录点云处理PCL常用函数与工具前言一、点云读取与保存数据读取数据保存自定义的点云保存格式二、点云显示点云显示-根据颜色点云显示-根据指定轴数值点云显示-根据指定信息显示多组点云显示三、点云滤波直通滤波统计滤波均匀下采样滤波VoxelGri…...

FyListen 在 MVP 架构中的内存优化表现
FyListen 在 MVP 中的内存优化表现 本文只是分享个人开源框架的内存优化测试,你可以直接跳到最后,参考内存泄漏的分析过程! 项目地址: https://github.com/StudyNoteOfTu/fylisten2-alpha1 由于使用到 AOP,所以直接…...

Qt代码单元测试以及报告生成
简介 单元测试是所有测试中最底层的一类测试,是第一个环节,也是最重要的一个环节,是唯一一次有保证能够代码覆盖率达到100%的测试,是整个软件测试过程的基础和前提,单元测试防止了开发的后期因bug过多而失控࿰…...

vscode构建Vue3.0项目(vite,vue-cli)
构建Vue3.0项目构建Vue3.0项目1.使用Vite构建vue项目的方法以及步骤1. 安装vite2. 运行vite vue 项目3.说明2.使用vue-cli构建vue项目的方法以及步骤1.安装全局vue cli —— 脚手架2、VSCode3.报错4.运行构建Vue3.0项目 1.使用Vite构建vue项目的方法以及步骤 1. 安装vite n…...
【2023】华为OD机试真题Java-题目0215-优雅数组
优雅数组 题目描述 如果一个数组中出现次数最多的元素出现大于等于 k k k 次,被称为k-优雅数组, k k k 也可以被称为优雅阈值。 例如,数组[1, 2, 3, 1, 2, 3, 1],它是一个3-优雅数组,因为元素1出现次数大于等于3次...

通过Prowork每日自动提醒待处理工作任务
对于中小团队来说,由于不需要繁琐的流程和高频的异地沟通,需要一款更适合中小团队的日程和项目管理工具。而Prowork就是这样一款敏捷高效的协同平台。Prowork与以往各种项目管理⼯具最⼤的不同在于,其弱化流程和弱化权限的特性,不…...
Linux自定义系统服务
文章目录一. Linux系统服务二. 自定义系统服务一. Linux系统服务 Linux 系统服务有时也称为守护程序,是在Linux启动时自动加载并在Linux退出时自动停止的系统任务,CentOS 7.x开始,CentOS开始使用 systemd服务来代替 daemon ,原来…...
mongodb lambda 查询插件
需求背景需要一个像mybatis plus 一样的基于lambda, 且面向对象的查询mongo数据的插件。在网上找了很久,没有发现有类似功能的插件。于是自己手写了一个,借助mongoTemplate屏蔽了底层查询语句的实现细节。在此基础上,实现了查询的统一封装。技…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...

Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...