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吗?貌似很难,即使知道是一个dp题也很难想到解法。 直观来看,使用bfs以一个点为中点进行遍历,需要的时间复杂度为 O ( n 2 m 2 ) O(n^2m^2) O(n2m2) 但是可以很容易发现,…...
花10分钟写个漂亮的后端API接口模板!
你好,我是田哥 在这微服务架构盛行的黄金时段,加上越来越多的前后端分离,导致后端API接口规范变得越来越重要了。 比如:统一返回参数形式、统一返回码、统一异常处理、集成swagger等。 目的主要是规范后端项目代码,以及…...
评估分类机器学习模型的指标
欢迎来到雲闪世界。一旦我们训练了一个监督机器学习模型来解决分类问题,如果这就是我们工作的结束,我们会很高兴,我们可以直接向他们输入新数据。我们希望它能正确地对所有内容进行分类。然而,实际上,模型做出的预测并…...
农机自动化:现代农业的未来趋势
随着人口的增长和农业生产的需求不断增加,提高农业生产效率成为现代农业的重要目标。农机自动化作为一种新兴技术,可以大幅度提升农机的使用效率和生产能力。农机自动化是指利用先进的传感技术、数据处理和人工智能技术,使农机能够自动完成农…...
25考研操作系统复习·1.1/1.2/1.3 操作系统的基本概念/发展历程/运行环境
目录 操作系统的基本概念 概念(定义) 功能和目标 资源的管理者 向上层提供服务 给普通用户的 给软件/程序员的 对硬件机器的拓展 操作系统的特征 操作系统的发展历程 操作系统的运行环境 操作系统的运行机制 中断和异常 中断的作用 中断的…...
如何培养学生的创新意识和实践能力
培养学生的创新意识和实践能力是一个复杂而系统的过程,涉及多个方面的努力和措施。以下是一些具体的做法: 一、培养学生的创新意识 提供创新环境: 为学生创造一个开放、自由、支持创新的学习环境,让他们能够自由地表达自己的想法…...
四、GD32 MCU 常见外设介绍(15)CAN 模块介绍
CAN是控制器局域网络(Controller Area Network)的简称,它是由研发和生产汽车电子产品著称的德国BOSCH公司开发的,并最终成为国际标准(ISO11519),是国际上应用最广泛的现场总线之一。 CAN总线协议已经成为汽车计算机控…...
AIGC大模型产品经理高频面试大揭秘‼️
近期有十几个学生在面试大模型产品经理(薪资还可以,详情见下图),根据他们面试(包括1-4面)中出现高频大于3次的问题汇总如下,一共32道题目(有答案)。 29.讲讲T5和Bart的区…...
【嵌入式笔记】【C语言】struct union
结构体(Struct)定义: struct 结构体名 {member1; // 成员1,可以是任何基本数据类型或复合类型member2; // 成员2... };//例如: struct Point {float x;float y;...
【初学人工智能原理】【9】深度学习:神奇的DeepLearning
前言 本文教程均来自b站【小白也能听懂的人工智能原理】,感兴趣的可自行到b站观看。 代码及工具箱 本专栏的代码和工具函数已经上传到GitHub:1571859588/xiaobai_AI: 零基础入门人工智能 (github.com),可以找到对应课程的代码 正文 深度…...
[RoarCTF 2019]Easy Calc1
打开题目 查看源码,看到 看到源代码有 calc.php,构造url打开 看到php审计代码, 由于页面中无法上传num,则输入 num,在num前加入一个空格可以让num变得可以上传,而且在进行代码解析时,php会把前…...
安卓APK安装包arm64-v8a、armeabi-v7a、x86、x86_64有何区别?如何选择?
在GitHub网站下载Android 安装包,Actions资源下的APK文件通常有以下版本供选择: 例如上图是某Android客户端的安装包文件,有以下几个版本可以选择: mobile-release.apk(通用版本,体积最大)mobi…...
【AI大模型】通义千问:开启语言模型新篇章与Function Call技术的应用探索
文章目录 前言一、大语言模型1.大模型介绍2.大模型的发展历程3.大模型的分类a.按内容分类b.按应用分类 二、通义千问1.通义千问模型介绍a.通义千问模型介绍b.应用场景c.模型概览 2.对话a.对话的两种方式通义千问API的使用 b.单轮对话Vue页面代码:Django接口代码 c.多…...
详细教程 MySQL 数据库 下载 安装 连接 环境配置 全面
数据库就是储存和管理数据的仓库,对数据进行增删改查操作,其本质是一个软件。 首先数据有两种,一种是关系型数据库,另一种是非关系型数据库。 关系型数据库是以表的形式来存储数据,表和表之间可以有很多复杂的关系&a…...
门控循环单元GRU
目录 一、GRU提出的背景:1.RNN存在的问题:2.GRU的思想: 二、更新门和重置门:三、GRU网络架构:1.更新门和重置门如何发挥作用:1.1候选隐藏状态H~t:1.2隐藏状态Ht: 2.GRU: 四、底层源码…...
程序员修炼之路
成为一名优秀的程序员,需要广泛而深入地学习多个领域的知识。这些课程不仅帮助建立扎实的编程基础,还培养了问题解决、算法设计、系统思维等多方面的能力。以下是一些核心的必修课: 计算机基础 计算机组成原理:理解计算机的硬件组…...
PHP时间相关函数
时间、日期 time()获取当前时间戳(10位)microtime(true)返回一个浮点时间戳data(格式,时间戳)日期格式化 $time time(); echo date(Y-m-d H:i:s, $time);strtotime&am…...
python进阶——python面向对象
前言 Python是一种面向对象的编程语言,可在Python中使用类和对象来组织和封装代码。面向对象编程(OOP)是一种编程范例,它将数据和操作数据的方法封装在一个对象内部,通过对象之间的交互来实现程序的功能。 1、面向对象…...
【无标题】vue2鼠标悬停(hover)时切换图片
在Vue 2中,要实现鼠标悬停(hover)时切换图片的功能,你不能直接在模板的:src绑定中处理这个逻辑,因为Vue的模板不支持条件渲染的复杂逻辑(如基于鼠标状态的动态图片切换)。但是,你可以…...
每天一个数据分析题(四百五十九)- 分析法
故障树分析法经常与哪些方法联合使用? A. 头脑风暴法 B. 五问法 C. 配对法 D. 引力法 数据分析认证考试介绍:点击进入 题目来源于CDA模拟题库 点击此处获取答案 数据分析专项练习题库 内容涵盖Python,SQL,统计学…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
