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

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)>0f(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(ik+1,j,0)>=kf(i,jk+1,1)>=k,如果条件成立,说明可以构成一个最后一点是 (i,j),边长为 k的正方形。

时间复杂度:O(m∗n∗min(m∗n))O(m*n*min(m*n))O(mnmin(mn))

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 &#xff1a; 1744 题目描述 给你一个由若干 0 和 1 组成的二维网格 grid&#xff0c;请你找出边界全部由 1 组成的最大 正方形 子网格&#xff0c;并返回该子网格中的元素数量。 如果不存在&#xff0c;则返回 0。…...

Bing+ChatGPT 对传统搜索引擎的降维打击

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

【JS】数组常用方法总结-功能、参数、返回值

数组常用方法总结-功能、参数、返回值 用简单的js示例 运行在线工具&#xff1a;链接: 菜鸟工具 菜鸟工具示意图&#xff1a; ![在这里插入图片描述](https://img-blog.csdnimg.cn/de8589eb1acf42abb0347d8a3a3bbdfa.png 1.会改变原有数组方法 &#xff08;1&#xff09;pu…...

pytest 单元测试前后置处理

文章目录方法1 setup/teardown方法2 fixture 夹具方法3 conftest.py测试用例执行前后的一些处理动作&#xff0c;也叫夹具。以下介绍使用前后置操作的几种方法。方法1 setup/teardown setup&#xff0c;每个测试用例执行前要进行的处理。 teardown&#xff0c;每个测试用例执行…...

汽车安全硬件扩展 AUTOSAR SHE SecureHardwareExtensions

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

2023年美国大学生数学建模C题:预测Wordle结果建模详解+模型代码

目录 前言 一、题目理解 背景 解析 字段含义&#xff1a; 建模要求 二、建模思路 灰色预测&#xff1a; ​编辑 二次指数平滑法&#xff1a; person相关性 只希望各位以后遇到建模比赛可以艾特认识一下我&#xff0c;我可以提供免费的思路和部分源码&#xff0c;以后…...

5、HAL库驱动W25Qxx

一、 SPI通信驱动W25Qxx 1、使用驱动文件快速配置工程代码驱动W25Qxx &#xff08;此驱动文件只适合W25Qxx 16M及以下型号&#xff0c;因为访问地址位数不同&#xff09; 注&#xff1a;本次使用SPI的方式进行访问W25Qxx Flash进行数据读写&#xff0c;关于W25Qxx芯片不会做…...

git rebase 洐合(变基)

洐合 把一个分支整合到另一个分支的办法有两种&#xff1a;merge&#xff08;合并&#xff09; 和 rebase&#xff08;衍合&#xff09; 为什么使用&#xff1f; 使提交记录更简洁 三种情况 第一种&#xff1a; 合并多条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技术 浏览器是多进程的&#xff0c;简单的说就是&#xff0c;浏览器每打开一个标签页&#xff0c;就相当于创建了一个独立的浏览器进程。但是js是基于单线程的&#xff0c;而这个线程就是浏览器的js引擎&#xff0c;浏览器无论在什么时候都只且只有一个线程在运行JavaScri…...

华为OD机试 - 最大排列(JS)

最大排列 题目 给定一组整数&#xff0c;重排序后输出一个最大的整数 输入 数字组合 输出 最大的整数 示例一 输入 10 9输出 910解题思路 我们可以读入一个字符串&#xff0c;将字符串中的单词按照每个单词的字典序长度&#xff0c;字典序从大到小的顺序排序&#x…...

Prometheus Docker安装及监控自身

前提环境&#xff1a; Docker环境 涉及参考文档&#xff1a; 安装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 中的内存优化表现 本文只是分享个人开源框架的内存优化测试&#xff0c;你可以直接跳到最后&#xff0c;参考内存泄漏的分析过程&#xff01; 项目地址&#xff1a; https://github.com/StudyNoteOfTu/fylisten2-alpha1 由于使用到 AOP&#xff0c;所以直接…...

Qt代码单元测试以及报告生成

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

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每日自动提醒待处理工作任务

对于中小团队来说&#xff0c;由于不需要繁琐的流程和高频的异地沟通&#xff0c;需要一款更适合中小团队的日程和项目管理工具。而Prowork就是这样一款敏捷高效的协同平台。Prowork与以往各种项目管理⼯具最⼤的不同在于&#xff0c;其弱化流程和弱化权限的特性&#xff0c;不…...

Linux自定义系统服务

文章目录一. Linux系统服务二. 自定义系统服务一. Linux系统服务 Linux 系统服务有时也称为守护程序&#xff0c;是在Linux启动时自动加载并在Linux退出时自动停止的系统任务&#xff0c;CentOS 7.x开始&#xff0c;CentOS开始使用 systemd服务来代替 daemon &#xff0c;原来…...

mongodb lambda 查询插件

需求背景需要一个像mybatis plus 一样的基于lambda, 且面向对象的查询mongo数据的插件。在网上找了很久&#xff0c;没有发现有类似功能的插件。于是自己手写了一个&#xff0c;借助mongoTemplate屏蔽了底层查询语句的实现细节。在此基础上&#xff0c;实现了查询的统一封装。技…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#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…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...