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

动态规划专题

leecode 221

在这里插入图片描述

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();if (n == 0) return 0; // 如果矩阵为空,则直接返回0  int m = matrix[0].size();vector<vector<int>> ans(n, vector<int>(m, 0)); // 初始化ans为n行m列的二维数组,并全部置为0  int maxSideLength = 0;// 初始化第一行和第一列  for (int i = 0; i < n; i++) {ans[i][0] = matrix[i][0] - '0'; // 假设矩阵中的字符是'1'或'0',直接转换为整数  maxSideLength = max(maxSideLength, ans[i][0]);}for (int j = 0; j < m; j++) {ans[0][j] = matrix[0][j] - '0';maxSideLength = max(maxSideLength, ans[0][j]);}for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {if (matrix[i][j] == '1') { // 使用'1'字符进行判断,而不是true  ans[i][j] = 1 + min(min(ans[i - 1][j - 1], ans[i][j - 1]), ans[i - 1][j]);maxSideLength = max(maxSideLength, ans[i][j]);}}}return maxSideLength * maxSideLength; // 因为返回的是最大正方形的面积,所以需要乘以边长本身  }
};

其实这个题目还可以使用二维前缀和来做

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;int a[101][101];
int b[101][101];int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];}}// 计算前缀和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];}}int len = 1;int ans = 0;while (len < min(n, m)) {for (int i = len; i <= n; i++) {for (int j = len; j <= m; j++) {if (b[i][j] - b[i - len][j] - b[i][j - len] + b[i - len][j - len] == len * len) {ans = max(ans, len);}}}len++;}cout << ans;return 0;
}

相关文章:

动态规划专题

leecode 221 class Solution { public:int maximalSquare(vector<vector<char>>& matrix) {int n matrix.size();if (n 0) return 0; // 如果矩阵为空&#xff0c;则直接返回0 int m matrix[0].size();vector<vector<int>> ans(n, vector<i…...

.net8.0与halcon编程环境构建

1.安装vs2022 2.安装h-12.0.exe ,不要勾选复选框 3.vs2022新建wpf应用程序 4.依赖项添加项目应用,选择halcondotnet.dll 5.安装System.Drawing 安装 HalconDotNet 安装 Rti.HDevEngineDotNet 在工具箱 空白处右键 应用halcon.dll WPF控件也应用halcon.dll 6.xaml申明hal…...

文心智能体平台:快来创建你的Java学习小助理,全方位辅助学习

文章目录 一、文心智能体平台1.1平台介绍1.2智能体介绍 二、智能体创建三、体验与总结 一、文心智能体平台 文心智能体平台是百度推出的基于文心大模型的智能体&#xff08;Agent&#xff09;平台&#xff0c;支持广大开发者根据自身行业领域、应用场景&#xff0c;选取不同类…...

AppInventor2 表格布局的外面的黑框怎么去掉?

问&#xff1a;表格布局的外面的黑框怎么去掉啊&#xff1f; 答&#xff1a;这个黑框是界面设计的布局位置示意&#xff0c;实际 App 测试时并没有框。 来源&#xff1a;AppInventor2 表格布局的外面的黑框怎么去掉&#xff1f; - App应用开发 - 清泛IT社区&#xff0c;为创新…...

爬楼梯(进阶版)

思路&#xff1a; 没什么难的&#xff0c;就是一个排序的01背包问题&#xff0c;秒了 #include<bits/stdc.h> using namespace std;int n,m; int main(){cin>>n>>m;vector<int>dp(2000,0);dp[0]1;for(int i0;i<n;i){for(int j1;j<m;j){if(i>…...

echarts-事件

echarts部分事件 添加点击事件 添加点击事件&#xff1a; let options {tooltip: {},xAxis: {type: "category",data: ["d1", "d2", "d3", "d4"],},yAxis: {},series: [{type: "line",data: d1,},{type: &qu…...

备受推崇的公司文件加密文件推荐榜单

迄今为止&#xff0c;加密依然是最有效的用于保护数据、通讯安全的手段之一 在数字化时代&#xff0c;文件加密软件成为了保护个人和企业数据安全的重要工具。随着技术的不断进步&#xff0c;市场上涌现出了众多优秀的文件加密软件。 以下十款文件加密软件因其出色的性能、易…...

QT——QSlider实现,QT滑动控件的使用

目录 简介滑动块调节两种方法滑动条触发信号量理想滑动块运用&#xff08;参考&#xff09; 简介 QT中滑动条的控件叫QSlider&#xff0c;继承自QAbstractSlider类。 主要用途是通过滑块的滑动的方式在一定范围内调节某个值。根据调节的后得到的结果去执行一些处理&#xff0c…...

【网络协议Http】Http中get,post,put,delete区别

Http协议 超文本传输协议&#xff08;Hypertext Transfer Protocol&#xff0c;HTTP&#xff09;是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。 【参考】 GET && POST 对比 关于tcp数据包&#xff1a;对于GET方式的请求&#xff0c;浏览器会把http hea…...

软硬中断区别,磁盘块、扇区、页区别与之间的关系

软硬中断&#xff1a; 软中断是执行中断指令产生的&#xff0c;而硬中断是由外设引发的。 硬中断的中断号是由中断控制器提供的&#xff0c;软中断的中断号由指令直接指出&#xff0c;无需使用中断控制器。 硬中断是可屏蔽的&#xff0c;软中断不可屏蔽。 硬中断处理程序要…...

在线思维导图编辑!3个AI思维导图生成软件推荐!

思维导图&#xff0c;一种以创新为驱动的视觉化思考工具&#xff0c;已经渗透到我们日常生活和工作的各个角落。当我们需要整理思绪、规划项目或者梳理信息时&#xff0c;思维导图总能提供极大的帮助。 近些年随着云服务等基础设施的完善&#xff0c;我们可以看到越来越多提供…...

使用 Ubuntu + Docker + Vaultwarden + Tailscale 自建密码管理器

使用 Ubuntu Docker Vaultwarden Tailscale 自建密码管理器 先决条件 一台运行 Ubuntu 系统的服务器。可以是云提供商的 VPS、家庭网络中的树莓派、或者 Windows 电脑上的虚拟机等等 一个 Tailscale 账户。如果还没有 Tailscale 账户&#xff0c;可以通过此链接迅速创建一个…...

YOLOv7添加注意力机制和各种改进模块

YOLOv7添加注意力机制和各种改进模块代码免费下载&#xff1a;完整代码 添加的部分模块代码&#xff1a; ########CBAM class ChannelAttentionModule(nn.Module):def __init__(self, c1, reduction16):super(ChannelAttentionModule, self).__init__()mid_channel c1 // red…...

【OpenGL第一个程序】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、OpenGL第一个程序 前言 本文介绍了OpenGL入门的第一个程序&#xff0c;有详细的注释&#xff0c;便于大家理解其中的逻辑。 一、OpenGL第一个程序 #inclu…...

GPT-4O神器来袭!自动生成Figma设计稿,移动端开发瞬间加速!

2024年5月29日- 近日&#xff0c;一款基于GPT-4O技术的创新工具成功实现根据产品需求文档&#xff08;PRD&#xff09;自动生成Figma设计稿的功能&#xff0c;为移动端应用开发者带来革命性的便捷。据悉&#xff0c;该功能主要针对移动端应用进行优化&#xff0c;并支持使用高质…...

清华大学提出IFT对齐算法,打破SFT与RLHF局限性

监督微调&#xff08;Supervised Fine-Tuning, SFT&#xff09;和基于人类反馈的强化学习&#xff08;Reinforcement Learning from Human Feedback, RLHF&#xff09;是预训练后提升语言模型能力的两大基础流程&#xff0c;其目标是使模型更贴近人类的偏好和需求。 考虑到监督…...

TS(TypeScript)中Array数组无法调出使用includes方法,显示红色警告

解决方法 打开tsconfig.json文件&#xff0c;添加"lib": ["es7", "dom"]即可。 如下图所示。...

基于Kafka的日志采集

目录 前言 架构图 资源列表 基础环境 关闭防护墙 关闭内核安全机制 修改主机名 添加hosts映射 一、部署elasticsearch 修改limit限制 部署elasticsearch 修改配置文件 启动 二、部署filebeat 部署filebeat 添加配置文件 启动 三、部署kibana 部署kibana 修…...

某烟草企业数字化转型物流信息化咨询项目规划方案(117页PPT)

方案介绍&#xff1a; 烟草企业数字化转型物流信息化咨询项目规划方案将为企业带来多方面的价值&#xff0c;包括提升物流运营效率、降低物流成本、优化供应链管理、增强企业竞争力和促进可持续发展等。这些价值的实现将有助于企业在激烈的市场竞争中保持领先地位并实现可持续…...

失落的方舟 命运方舟台服封号严重 游戏封IP怎么办

步入《失落的方舟》&#xff08;Lost Ark&#xff09;&#xff0c;这款由Smilegate精心打造的宏大规模在线角色扮演游戏&#xff08;MMORPG&#xff09;&#xff0c;您将启程前往阿克拉西亚这片饱经沧桑的奇幻大陆&#xff0c;展开一场穿越时空的壮阔探索。在这里&#xff0c;一…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...