当前位置: 首页 > 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…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...