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

dp:221. 最大正方形

221. 最大正方形
在这里插入图片描述
看到这个题目真能立马想到dp吗?貌似很难,即使知道是一个dp题也很难想到解法。

直观来看,使用bfs以一个点为中点进行遍历,需要的时间复杂度为 O ( n 2 m 2 ) O(n^2m^2) O(n2m2)

但是可以很容易发现,如果求以一个点为角 构成的最大正方形,可以通过其他周围的点作为角来快速找到这个点的最大正方形。

我们用数组存以该点为右下角,左下角,左上角,右上角的最大正方形,可以通过周围的转移,然后求出以它为“中心”构成的最大正方形。于是有如下代码

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();if(n == 1 && m == 1) return matrix[0][0];vector<vector<vector<int>>> dp(n, vector<int>(m, vector<int>(4, 0)));int ans = 0;for(int j = 0; j < m; ++ j){dp[0][j][0] = dp[0][j][1]= dp[0][j][2] = dp[0][j][3] = matrix[0][j];}for(int i = 1; i < n - 1; ++ i){dp[i][0][0] = dp[i][0][1] = dp[i][0][2] = dp[i][0][3] = matrix[i][0];for(int j = 1; j < m - 1; ++ j){dp[i][j][0] = min(dp[i - 1][j][0], min(dp[i - 1][j - 1][0], dp[i][j - 1][0])) + 1;dp[i][j][1] = min(dp[i - 1][j][1], min(dp[i - 1][j + 1][1], dp[i][j + 1][1])) + 1;····}//最后一列}//最后一行return ans * ans;}
};

但是实际上,以该点为右下角就足以解决这个问题,因为对于任何一个最大正方形而言,它一定有一个右下角,那么找到这个右下角能构成的最大正方形就是这个正方形了

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();if(n == 1 && m == 1) return matrix[0][0] - '0';vector<vector<int>> dp(n, vector<int>(m, 0));int ans = 0;for(int i = 0; i < m; ++ i){dp[0][i] = matrix[0][i] - '0';ans = max(ans, dp[0][i]);}for(int i = 1; i < n; ++ i){dp[i][0] = matrix[i][0] - '0';ans = max(ans, dp[i][0]);for(int j = 1; j < m; ++ j){if(matrix[i][j] == '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;}
};

相关文章:

dp:221. 最大正方形

221. 最大正方形 看到这个题目真能立马想到dp吗&#xff1f;貌似很难&#xff0c;即使知道是一个dp题也很难想到解法。 直观来看&#xff0c;使用bfs以一个点为中点进行遍历&#xff0c;需要的时间复杂度为 O ( n 2 m 2 ) O(n^2m^2) O(n2m2) 但是可以很容易发现&#xff0c;…...

花10分钟写个漂亮的后端API接口模板!

你好&#xff0c;我是田哥 在这微服务架构盛行的黄金时段&#xff0c;加上越来越多的前后端分离&#xff0c;导致后端API接口规范变得越来越重要了。 比如&#xff1a;统一返回参数形式、统一返回码、统一异常处理、集成swagger等。 目的主要是规范后端项目代码&#xff0c;以及…...

评估分类机器学习模型的指标

欢迎来到雲闪世界。一旦我们训练了一个监督机器学习模型来解决分类问题&#xff0c;如果这就是我们工作的结束&#xff0c;我们会很高兴&#xff0c;我们可以直接向他们输入新数据。我们希望它能正确地对所有内容进行分类。然而&#xff0c;实际上&#xff0c;模型做出的预测并…...

农机自动化:现代农业的未来趋势

随着人口的增长和农业生产的需求不断增加&#xff0c;提高农业生产效率成为现代农业的重要目标。农机自动化作为一种新兴技术&#xff0c;可以大幅度提升农机的使用效率和生产能力。农机自动化是指利用先进的传感技术、数据处理和人工智能技术&#xff0c;使农机能够自动完成农…...

25考研操作系统复习·1.1/1.2/1.3 操作系统的基本概念/发展历程/运行环境

目录 操作系统的基本概念 概念&#xff08;定义&#xff09; 功能和目标 资源的管理者 向上层提供服务 给普通用户的 给软件/程序员的 对硬件机器的拓展 操作系统的特征 操作系统的发展历程 操作系统的运行环境 操作系统的运行机制 中断和异常 中断的作用 中断的…...

如何培养学生的创新意识和实践能力

培养学生的创新意识和实践能力是一个复杂而系统的过程&#xff0c;涉及多个方面的努力和措施。以下是一些具体的做法&#xff1a; 一、培养学生的创新意识 提供创新环境&#xff1a; 为学生创造一个开放、自由、支持创新的学习环境&#xff0c;让他们能够自由地表达自己的想法…...

四、GD32 MCU 常见外设介绍(15)CAN 模块介绍

CAN是控制器局域网络(Controller Area Network)的简称&#xff0c;它是由研发和生产汽车电子产品著称的德国BOSCH公司开发的&#xff0c;并最终成为国际标准&#xff08;ISO11519&#xff09;&#xff0c;是国际上应用最广泛的现场总线之一。 CAN总线协议已经成为汽车计算机控…...

AIGC大模型产品经理高频面试大揭秘‼️

近期有十几个学生在面试大模型产品经理&#xff08;薪资还可以&#xff0c;详情见下图&#xff09;&#xff0c;根据他们面试&#xff08;包括1-4面&#xff09;中出现高频大于3次的问题汇总如下&#xff0c;一共32道题目&#xff08;有答案&#xff09;。 29.讲讲T5和Bart的区…...

【嵌入式笔记】【C语言】struct union

结构体(Struct)定义: struct 结构体名 {member1; // 成员1,可以是任何基本数据类型或复合类型member2; // 成员2... };//例如: struct Point {float x;float y;...

【初学人工智能原理】【9】深度学习:神奇的DeepLearning

前言 本文教程均来自b站【小白也能听懂的人工智能原理】&#xff0c;感兴趣的可自行到b站观看。 代码及工具箱 本专栏的代码和工具函数已经上传到GitHub&#xff1a;1571859588/xiaobai_AI: 零基础入门人工智能 (github.com)&#xff0c;可以找到对应课程的代码 正文 深度…...

[RoarCTF 2019]Easy Calc1

打开题目 查看源码&#xff0c;看到 看到源代码有 calc.php&#xff0c;构造url打开 看到php审计代码&#xff0c; 由于页面中无法上传num&#xff0c;则输入 num&#xff0c;在num前加入一个空格可以让num变得可以上传&#xff0c;而且在进行代码解析时&#xff0c;php会把前…...

安卓APK安装包arm64-v8a、armeabi-v7a、x86、x86_64有何区别?如何选择?

在GitHub网站下载Android 安装包&#xff0c;Actions资源下的APK文件通常有以下版本供选择&#xff1a; 例如上图是某Android客户端的安装包文件&#xff0c;有以下几个版本可以选择&#xff1a; mobile-release.apk&#xff08;通用版本&#xff0c;体积最大&#xff09;mobi…...

【AI大模型】通义千问:开启语言模型新篇章与Function Call技术的应用探索

文章目录 前言一、大语言模型1.大模型介绍2.大模型的发展历程3.大模型的分类a.按内容分类b.按应用分类 二、通义千问1.通义千问模型介绍a.通义千问模型介绍b.应用场景c.模型概览 2.对话a.对话的两种方式通义千问API的使用 b.单轮对话Vue页面代码&#xff1a;Django接口代码 c.多…...

详细教程 MySQL 数据库 下载 安装 连接 环境配置 全面

数据库就是储存和管理数据的仓库&#xff0c;对数据进行增删改查操作&#xff0c;其本质是一个软件。 首先数据有两种&#xff0c;一种是关系型数据库&#xff0c;另一种是非关系型数据库。 关系型数据库是以表的形式来存储数据&#xff0c;表和表之间可以有很多复杂的关系&a…...

门控循环单元GRU

目录 一、GRU提出的背景&#xff1a;1.RNN存在的问题&#xff1a;2.GRU的思想&#xff1a; 二、更新门和重置门&#xff1a;三、GRU网络架构&#xff1a;1.更新门和重置门如何发挥作用&#xff1a;1.1候选隐藏状态H~t&#xff1a;1.2隐藏状态Ht&#xff1a; 2.GRU: 四、底层源码…...

程序员修炼之路

成为一名优秀的程序员&#xff0c;需要广泛而深入地学习多个领域的知识。这些课程不仅帮助建立扎实的编程基础&#xff0c;还培养了问题解决、算法设计、系统思维等多方面的能力。以下是一些核心的必修课&#xff1a; 计算机基础 计算机组成原理&#xff1a;理解计算机的硬件组…...

PHP时间相关函数

时间、日期 time&#xff08;&#xff09;获取当前时间戳&#xff08;10位&#xff09;microtime&#xff08;true&#xff09;返回一个浮点时间戳data&#xff08;格式&#xff0c;时间戳&#xff09;日期格式化 $time time(); echo date(Y-m-d H:i:s, $time);strtotime&am…...

python进阶——python面向对象

前言 Python是一种面向对象的编程语言&#xff0c;可在Python中使用类和对象来组织和封装代码。面向对象编程&#xff08;OOP&#xff09;是一种编程范例&#xff0c;它将数据和操作数据的方法封装在一个对象内部&#xff0c;通过对象之间的交互来实现程序的功能。 1、面向对象…...

【无标题】vue2鼠标悬停(hover)时切换图片

在Vue 2中&#xff0c;要实现鼠标悬停&#xff08;hover&#xff09;时切换图片的功能&#xff0c;你不能直接在模板的:src绑定中处理这个逻辑&#xff0c;因为Vue的模板不支持条件渲染的复杂逻辑&#xff08;如基于鼠标状态的动态图片切换&#xff09;。但是&#xff0c;你可以…...

每天一个数据分析题(四百五十九)- 分析法

故障树分析法经常与哪些方法联合使用&#xff1f; A. 头脑风暴法 B. 五问法 C. 配对法 D. 引力法 数据分析认证考试介绍&#xff1a;点击进入 题目来源于CDA模拟题库 点击此处获取答案 数据分析专项练习题库 内容涵盖Python&#xff0c;SQL&#xff0c;统计学&#xf…...

云容笔谈开源镜像优势:免编译、免依赖、BF16原生支持,开箱即生成

云容笔谈开源镜像优势&#xff1a;免编译、免依赖、BF16原生支持&#xff0c;开箱即生成 最近在尝试各种AI图像生成工具时&#xff0c;我发现了一个很有意思的现象&#xff1a;很多工具要么安装配置复杂&#xff0c;要么生成效果不尽如人意&#xff0c;特别是想要生成具有东方…...

【仿真】Carla跨平台部署指南:从零到一,附ROS2与Autoware.auto连接实战

1. Carla仿真平台概述 Carla是一款开源的自动驾驶仿真平台&#xff0c;基于虚幻引擎构建&#xff0c;能够提供高度逼真的城市环境和交通场景。我第一次接触Carla是在2018年&#xff0c;当时它还处于早期开发阶段&#xff0c;但已经展现出惊人的潜力。经过多年发展&#xff0c;现…...

zotero-style:智能文献管理在学术研究中的创新实践

zotero-style&#xff1a;智能文献管理在学术研究中的创新实践 【免费下载链接】zotero-style zotero-style - 一个 Zotero 插件&#xff0c;提供了一系列功能来增强 Zotero 的用户体验&#xff0c;如阅读进度可视化和标签管理&#xff0c;适合研究人员和学者。 项目地址: ht…...

告别单打独斗!Apipost 8协作版数据迁移保姆级教程(含团队项目处理)

Apipost 8协作版数据迁移实战&#xff1a;从个人到团队的无缝衔接 第一次打开Apipost 8协作版时&#xff0c;我盯着那个"迁入项目"按钮犹豫了整整十分钟——作为独立开发者&#xff0c;我的旧版本里积累了237个接口文档和56个测试集合&#xff0c;它们就像我精心搭建…...

突破PDF转换困境:Marker全攻略——从格式混乱到精准转换的革新之路

突破PDF转换困境&#xff1a;Marker全攻略——从格式混乱到精准转换的革新之路 【免费下载链接】marker 一个高效、准确的工具&#xff0c;能够将 PDF 和图像快速转换为 Markdown、JSON 和 HTML 格式&#xff0c;支持多语言和复杂布局处理&#xff0c;可选集成 LLM 提升精度&am…...

告别手动编码烦恼:用CANopenEditor高效定制CANopenNode对象字典

告别手动编码烦恼&#xff1a;用CANopenEditor高效定制CANopenNode对象字典 【免费下载链接】CANopenNode CANopen protocol stack 项目地址: https://gitcode.com/gh_mirrors/ca/CANopenNode 你是否曾为CANopenNode项目中繁琐的对象字典配置而头疼&#xff1f;手动编写…...

使用PyTorch Lightning优化PETRV2-BEV模型训练流程

使用PyTorch Lightning优化PETRV2-BEV模型训练流程 如果你正在训练像PETRV2这样的BEV感知模型&#xff0c;可能已经体会过那种“一步一坑”的感觉。数据加载复杂、多GPU训练配置繁琐、日志记录混乱、实验难以复现……这些工程上的琐事&#xff0c;常常比模型本身更让人头疼。 …...

《数据结构》| 第十章 排序算法实战指南

1. 排序算法入门&#xff1a;为什么我们需要这么多排序方法&#xff1f; 第一次接触排序算法时&#xff0c;很多人都会有这样的疑问&#xff1a;既然都能把数据排好序&#xff0c;为什么还要学这么多种算法&#xff1f;这就像装修时既有电钻又有锤子——每种工具都有最适合的使…...

Nginx反向代理实战:不改代码轻松解决前后端跨域问题(附完整配置模板)

Nginx反向代理实战&#xff1a;不改代码轻松解决前后端跨域问题&#xff08;附完整配置模板&#xff09; 前后端分离架构已成为现代Web开发的主流模式&#xff0c;但随之而来的跨域问题却让不少开发者头疼。想象一下这样的场景&#xff1a;你的前端运行在https://frontend.com&…...

如何快速实现Font Awesome图标字体文件格式转换:终极在线工具指南

如何快速实现Font Awesome图标字体文件格式转换&#xff1a;终极在线工具指南 【免费下载链接】Font-Awesome The iconic SVG, font, and CSS toolkit 项目地址: https://gitcode.com/GitHub_Trending/fo/Font-Awesome Font Awesome作为一款标志性的SVG、字体和CSS工具包…...