LeetCode HOT100系列题解之最大正方形(6/100)

devtools/2024/9/20 7:05:09/ 标签: leetcode, 算法, 职场和发展

题目:最大正方形. - 力扣(LeetCode)

题解:

第一种方法:前缀和+二分答案(暴力优化)我感觉比官方给的暴力好一点

时间复杂度: O(NM\log min(N,M))

  • 暴力优化1:通过前缀和减少判断1出现得次数(这个题比较特别,只有0,1)
  • 暴力优化2:答案单调,二分答案

在check函数中,我去找了当答案为x时,即找到所有x * x得正方形来进行判断,如果它得值为x * x,那么说明答案成立。

代码1

class Solution {
public:bool check(int x, int n, int m, const vector<vector<int>>& sum){if(x == 0) return true;int ans = x * x;for(int i = x; i <= n; i ++){for(int j = x; j <= m; j ++){int x1 = i - x + 1;int y1 = j - x + 1;int x2 = i;int y2 = j;if(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] == ans)return true; }}return false;}int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();vector<vector<int>>sum;sum.resize(n + 1, vector<int>(m + 1, 0));for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++){sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (matrix[i - 1][j - 1] == '1');//cout << sum[i][j] << endl;}int l = 0, r = min(n, m);while(l <= r){int mid = l + (r + 1) >> 1;if(check(mid, n, m, sum)) l = mid + 1;else r = mid - 1; }return (l - 1) * (l - 1);}
};

第二种方法:DP(动态规划)

题解来源:该题官网题解。

时间复杂度: O(NM)

这里仅解释一下为什么转移方程是

 dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1

通俗易懂得理解方法是,因为本题需要得是正方形,因此仅需要保证周围点为1且加上自己构成正方形即可。如果左、上、左上有一个点为0,那么将无法转移。至于为什么不会被判断成长方形呢?可以看到

代码2:

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();int ans = 0;vector<vector<int>>dp(n + 1, vector<int>(m + 1, 0));for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){if(matrix[i-1][j-1] == '0') dp[i][j] = 0;else{dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;//保证周围点为正方形}ans = max(ans, dp[i][j]);}}return ans * ans;}
};

思考:

思考二:如果是求长方形,又该如何去做?

这个题就会变得非常有趣。动态规划应该依旧有求解得办法,但是原方程必定失效。而这个题是LeetCode 8585.最大矩形. - 力扣(LeetCode)得题,使用的是单调栈来求解,我将在后续对这个题单独学习。


http://www.ppmy.cn/devtools/109019.html

相关文章

SpringBoot教程(十五) | SpringBoot集成RabbitMq(消息丢失、消息重复、消息顺序、消息顺序)

SpringBoot教程&#xff08;十五&#xff09; | SpringBoot集成RabbitMq&#xff08;消息丢失、消息重复、消息顺序、消息顺序&#xff09; RabbitMQ常见问题解决方案问题一&#xff1a;消息丢失的解决方案&#xff08;1&#xff09;生成者丢失消息丢失的情景解决方案1&#xf…

Elasticsearch之原理详解

简介 ES是使用 Java 编写的一种开源搜索引擎&#xff0c;它在内部使用 Lucene 做索引与搜索&#xff0c;通过对 Lucene 的封装&#xff0c;隐藏了 Lucene 的复杂性&#xff0c;取而代之的提供一套简单一致的 RESTful API 然而&#xff0c;Elasticsearch 不仅仅是 Lucene&#…

【ES备份和还原索引数据】

文章目录 备份&#xff08;Snapshot&#xff09;还原&#xff08;Restore&#xff09;注意事项示例 在 Elasticsearch 中&#xff0c;备份和还原索引数据通常通过快照&#xff08;Snapshot&#xff09;和恢复&#xff08;Restore&#xff09;机制来实现。以下是详细的操作步骤&…

【RabbitMQ】核心概念

界⾯上的导航栏共分6部分, 这6部分分别是什么意思呢, 我们先看看RabbitMQ的工作流程 1. Producer和Consumer Producer:生产者,是RabbitMQ Server的客户端,向RabbitMQ发送消息 Consumer: 消费者,也是RabbitMQ Server的客户端,从RabbitMQ接收消息 Broker:其实就是RabbitMQSer…

策略规划:在MySQL中实现数据恢复的全面指南

数据恢复是数据库管理中至关重要的一环&#xff0c;它确保在发生数据丢失或损坏的情况下&#xff0c;能够迅速且准确地恢复数据。在MySQL中&#xff0c;实现有效的数据恢复策略规划需要综合考虑备份策略、备份类型、存储管理、故障转移机制以及恢复流程。本文将深入探讨如何在M…

springcloud-GateWay

Spring Cloud Gateway 是 Spring Cloud 微服务架构中的一个重要组件&#xff0c;用于提供 API 网关功能。作为 API 网关&#xff0c;Spring Cloud Gateway 充当客户端和后端服务之间的代理&#xff0c;负责请求路由、过滤、安全认证、负载均衡等功能。在分布式系统中&#xff0…

2024数学建模国赛B题代码

B题已经完成模型代码&#xff01;详情查看文末名片 问题1&#xff1a;可以考虑使用统计学中的“样本量估算”方法&#xff0c;使用二项分布或正态近似来决定最少的样本量&#xff0c;并通过假设检验&#xff08;如单侧检验&#xff09;在95%和90%置信度下进行判断。 import n…

漫谈设计模式 [6]:适配器模式

引导性开场 菜鸟&#xff1a;老鸟&#xff0c;我最近在项目中遇到一个问题&#xff0c;我们的系统需要集成一个新的第三方库&#xff0c;但这个库的接口和我们现有的代码完全不兼容。我该怎么办&#xff1f; 老鸟&#xff1a;这是个常见的问题&#xff0c;很多开发者都会遇到…

浙大数据结构:03-树3 Tree Traversals Again

这道题也不算难&#xff0c;我依然采用map来进行处理 &#xff0c;代码依旧较短 机翻 1、条件准备 我这里采用数组模拟栈&#xff0c;tt指向栈顶&#xff1b; map的键存结点值&#xff0c;后面数对存左右子树的结点值 head存头节点的值 #include<iostream> #include…

【自动驾驶】控制算法(八)横向控制Ⅰ | 算法与流程

写在前面&#xff1a; &#x1f31f; 欢迎光临 清流君 的博客小天地&#xff0c;这里是我分享技术与心得的温馨角落。&#x1f4dd; 个人主页&#xff1a;清流君_CSDN博客&#xff0c;期待与您一同探索 移动机器人 领域的无限可能。 &#x1f50d; 本文系 清流君 原创之作&…

go-gin响应被覆盖为400,即使正常返回

问题描述及排查过程 一个正常响应里&#xff0c;http状态码为400&#xff0c;但实际已经成功返回了数据&#xff0c;且无论是自己写的业务逻辑代码还是中间件都没有返回400&#xff08;bad request&#xff09;这个状态码。 而且gin debug日志中也提示说有操作试图将状态码40…

基于EPS32C3电脑远程开机模块设计

基于EPS32C3电脑远程开机模块设计 前言 缘起&#xff0c;手头资料太多了&#xff0c;所以想组一台NAS放在家里存储数据。在咸鱼淘了一套J3160主板加机箱&#xff0c;加上几块硬盘组建NAS。 对于NAS&#xff0c;我的需求是不用的时候关机(节省功耗)&#xff0c;要用的时候开机…

Web

关于Web Web是基于HTTP协议进行交互的应用网络Web就是通过使用浏览器/APP访问的各种资源 一个请求对应一个响应 eg. 淘宝网 输入一个url&#xff0c;就会返回一个页面 简单的网站开发 简单代码 package mainimport ("fmt""net/http" )/*http.ResponseWr…

linux 链接库时 -I(大写i)、-L、-l(小写l) 选项的含义

-I(大写i) 选项 -I 选项用于指定编译器在搜索头文件时应该包括的额外目录。当编译器在编译过程中遇到#include指令时&#xff0c;它会在标准路径&#xff08;如/usr/include&#xff09;和通过-I指定的路径中查找指定的头文件。 # 在这个例子中&#xff0c;编译器会在/usr/loc…

【内网】ICMP出网ew+pingtunnel组合建立socks5隧道

❤️博客主页&#xff1a; iknow181 &#x1f525;系列专栏&#xff1a; 网络安全、 Python、JavaSE、JavaWeb、CCNP &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐评论✍ 通过环境搭建&#xff0c;满足以下条件&#xff1a; 攻击机模拟公网vps地址&#xff0c;WEB边界服务器(…

Web服务器配置管理

目录 一、设计内容&#xff1a; 二、摘 要 三、课题描述 四、需求分析 五、概要设计 六、详细设计 七、结果分析 八、总结 一、设计内容 Web服务器的安装与配置管理。 1.任务说明 C/S 模式的网络环境&#xff0c;包括一台Windows工作站和一台Windows Server 服务器。 2.要求 ①…

redis之缓存淘汰策略

1.查看redis的最大占用内存 使用redis-cli命令连接redis服务端&#xff0c;输入命令&#xff1a;config get maxmemory 输出的值为0&#xff0c;0代表redis的最大占用内存等同于服务器的最大内存。 2.设置redis的最大占用内存 编辑redis的配置文件&#xff0c;并重启redis服务…

python测试开发基础---线程和进程的概念

多线程和多进程 多线程和多进程是实现并发的两种主要方法&#xff0c;它们各有特点和适用场景。下面详细讲解它们的区别&#xff1a; 1. 基本定义 多线程&#xff08;Multithreading&#xff09;&#xff1a; 在一个单一进程内创建多个线程&#xff0c;每个线程都可以独立执行…

二、Maven工程的创建--JavaSEJavaEE

1、idea创建Maven JavaSE工程&#xff1a; 2、idea创建Maven JavaEE工程&#xff1a; &#xff08;1&#xff09;手动创建 &#xff08;2&#xff09;插件方式创建 在idea里安装插件JBLJavaToWeb&#xff1b; 选择需要生成的项目文件后&#xff0c;右击&#xff1a; 项目…

spring boot 项目 跟 JavaScript 简单 websocket 使用

文章目录 websocket 简绍WebSocket 的优势包括&#xff1a;JavaScript 设置处理事件 Java 服务端设置导jar包创建WebSocket端点EnableWebSocketregisterWebSocketHandlers 实现WebSocket处理器afterConnectionEstablishedafterConnectionClosedhandleTextMessage 注销WebSocket…