力扣221.最大正方形(动态规划)

思路:

  1. 思路:从[0,0]元素开始,计算每个元素对应其与[0,0]之间矩阵块中最大正方形边长
  2. 情况:1)matrix [ i , j ] = ‘0’ --> 元素对应的最大正方形为0。
  3. 情况:2)matrix [ i , j ] = ‘1’ --> max ( matrix [ i-1 , j ] , matrix [ i - 1 , j - 1 ) ,matrix [ i , j - 1 ] ) + 1
  4. 具体实现:1)先找出第一行和第一列的最大正方形边长(只有1、0两种结果);2)计算中间部分的每个元素对应最大正方形边长;3)找出所有元素对应正方形边长中最大值,计算面积;
/*** @author Limg* @date 2022/08/10* 在一个由 '0' 和 '1' 组成的二维矩阵内,* 找到只包含 '1' 的最大正方形,并返回其面积。
*/
#include<iostream>
#include<vector>
using namespace std;
int maximalSquare(vector<vector<char>>& matrix);
int main()
{//输入矩阵,便于测试int m=0,n=0;cin>>m;cin>>n;vector<vector<char> > matrix;char value;vector<char> temp;  for(int i=0;i<m;i++){for(int j=0;j<n;j++){cin>>value;temp.push_back(value);}matrix.push_back(temp);temp.clear();}//调用函数cout<<maximalSquare(matrix)<<endl;return 0;
}
//解题函数
int maximalSquare(vector<vector<char>>& matrix) 
{int m = matrix.size();int n = matrix[0].size();int record[m][n];int max_curr = 0;  //计算最大边长for(int i=0;i<m;i++)  //第一列最大1,最小0{record[i][0] = int(matrix[i][0]-'0');max_curr = max(record[i][0],max_curr);}for(int j=0;j<n;j++)  //第一行最大1,最小0{record[0][j] = int(matrix[0][j]-'0');max_curr = max(record[0][j],max_curr);}for(int i=1;i<m;i++)  //中间部分依次计算{for(int j=1;j<n;j++){if(matrix[i][j]-'0'==0){record[i][j] = 0;}else{int min_2 = min(record[i-1][j-1],record[i-1][j]);record[i][j] = min(min_2,record[i][j-1])+1;max_curr = max(record[i][j],max_curr);} }}return max_curr*max_curr;
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/94100.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

当速度很重要时:使用 Hazelcast 和 Redpanda 进行实时流处理

在本教程中&#xff0c;了解如何构建安全、可扩展、高性能的应用程序&#xff0c;以释放实时数据的全部潜力。 在本教程中&#xff0c;我们将探索 Hazelcast 和 Redpanda 的强大组合&#xff0c;以构建对实时数据做出反应的高性能、可扩展和容错的应用程序。 Redpanda 是一个流…

openCV使用c#操作摄像头

效果如下&#xff1a; 1.创建一个winform的窗体项目&#xff08;框架.NET Framework 4.7.2&#xff09; 2.Nuget引入opencv的c#程序包&#xff08;版本最好和我一致&#xff09; 3.后台代码 using System; using System.Collections.Generic; using System.ComponentModel;…

LeetCode算法心得——限制条件下元素之间的最小绝对差(TreeSet)

大家好&#xff0c;我是晴天学长&#xff0c;今天用到了Java一个非常实用的类TreeSet&#xff0c;能解决一些看起来棘手的问题。 1 &#xff09;限制条件下元素之间的最小绝对差 2) .算法思路 初始化变量&#xff1a;n为列表nums的大小。 min为整型最大值&#xff0c;用于记录…

讯飞星火、文心一言和通义千问同时编“贪吃蛇”游戏,谁会胜出?

同时向讯飞星火、文心一言和通义千问三个国产AI模型提个相同的问题&#xff1a; “python 写一个贪吃蛇的游戏代码” 看哪一家AI写的程序直接能用&#xff0c;谁就胜出&#xff01; 讯飞星火 讯飞星火给出的代码&#xff1a; import pygame import sys import random# 初…

k8s 认证和权限控制

k8s 的认证机制是啥&#xff1f; 说到 k8s 的认证机制&#xff0c;其实之前咋那么也有提到过 ServiceAccouont &#xff0c;以及相应的 token &#xff0c;证书 crt&#xff0c;和基于 HTTP 的认证等等 k8s 会使用如上几种方式来获取客户端身份信息&#xff0c;不限于上面几种…

iPhone(iPad)安装deb文件

最简单的方法就是把deb相关的文件拖入手机对应的目录&#xff0c;一般是DynamicLibraries文件夹 参考&#xff1a;探讨手机越狱和安装deb文件的几种方式研究 1、在 Mac 上安装 dpkg 命令 打包 deb 教程之在 Mac 上安装 dpkg 命令_xcode打包root权限deb_qq_34810996的博客-CS…

基于php动漫周边电商购物网站系统

动漫周边电商网站系统&#xff0c;是基于php毕业设计&#xff0c;mysql数据库进行开发&#xff0c;本系统分为用户和管理员两个角色&#xff0c;其中用户可以注册登陆系统&#xff0c;用户查看商品分类&#xff0c;商品列表&#xff0c;查看动漫周边商品详情&#xff0c;加入购…

【学习笔记之java】使用RestTemplate调用第三方接口

1.首先需要导入依赖 <!-- RestTemplate使用导入的依赖--><dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient</artifactId><version>4.5.13</version></dependency>2.跟启动类同级创建…

回归预测 | MATLAB实现GRU门控循环单元多输入多输出

回归预测 | MATLAB实现GRU门控循环单元多输入多输出 目录 回归预测 | MATLAB实现GRU门控循环单元多输入多输出预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 MATLAB实现GRU门控循环单元多输入多输出&#xff0c;数据为多输入多输出预测数据&#xff0c;输入10个…

UDP 的报文结构以及注意事项

UDP协议 1.UDP协议端格式 1.图中的16位UDP长度,表示整个数据报(UDP首部UDP数据)的最大长度 2.若校验和出错,会直接丢弃 2.UDP的报文结构 UDP报文主体分为两个部分:UDP报头(占8个字节)UDP载荷/UDP数据 1.源端口号 16位,2个字节 2.目的端口号 16位,2个字节 3.包长度 指示了…

Vue用JSEncrypt对长文本json加密以及发现解密失败

哈喽 大家好啊&#xff0c;最近发现进行加密后 超长文本后端解密失败&#xff0c;经过看其他博主修改 JSEncrypt原生代码如下&#xff1a; // 分段加密&#xff0c;支持中文JSEncrypt.prototype.encryptUnicodeLong function (string) {var k this.getKey();//根据key所能编…

【Git】(三)回退版本

1、git reset命令 1.1 回退至上一个版本 git reset --hard HEAD^ 1.2 将本地的状态回退到和远程的一样 git reset --hard origin/master 注意&#xff1a;谨慎使用 –-hard 参数&#xff0c;它会删除回退点之前的所有信息。HEAD 说明&#xff1a;HEAD 表示当前版本HEAD^ 上…

【JVM】如何判定一个对象已死以及“标记-清除”、“标记-复制”、“标记-整理”三种垃圾收集算法

文章目录 0、如何判定一个对象的生死&#xff1f;1、上文提到的引用又是什么1、强引用&#xff1a;2、软引用&#xff1a;3、弱引用&#xff1a;4、虚引用&#xff1a; 2、垃圾收集算法1、标记-清除2、标记-复制优化&#xff1a;&#x1f447; 3、标记-整理 0、如何判定一个对象…

星际争霸之小霸王之小蜜蜂(二)--类的使用

目录 前言 一、将设置内容写在一个类里 二、设置小蜜蜂的造型 三、设置猫蜜蜂的参数 四、绘制猫蜜蜂到窗口 总结 前言 昨天我们设置好了窗口&#xff0c;下面我们需要向窗口中添加元素了。 一、将设置内容写在一个类里 我个人理解书上的意思是要创建一个类&#xff0c;将所有需…

vue3动态组件

1 、 可以通过 shallowRef 把 可以把组件进行包裹 <template><div><el-button click"setclick(son1)">1111</el-button><el-button click"setclick(son2)">2222</el-button><el-button click"setclick(son…

日常BUG—— SpringBoot项目DEBUG模式启动慢、卡死。

&#x1f61c;作 者&#xff1a;是江迪呀✒️本文关键词&#xff1a;日常BUG、BUG、问题分析☀️每日 一言 &#xff1a;存在错误说明你在进步&#xff01; 一、问题描述 我们调试程序时&#xff0c;需要使用DEBUG模式启动SpringBoot项目&#xff0c; 有时候会发…

LangChain手记 Evalutation评估

整理并翻译自DeepLearning.AILangChain的官方课程&#xff1a;Evaluation&#xff08;源代码可见&#xff09; 基于LLM的应用如何做评估是一个难点&#xff0c;本节介绍了一些思路和工具。 “从传统开发转换到基于prompt的开发&#xff0c;开发使用LLM的应用&#xff0c;整个工…

docker 容器满了常用处理方法

docker 容器满了常用处理方法 1、运行 df -h 查看剩余磁盘占用情况 2、进入到docker目录 cd /var/lib/docker 3、运行du -h --max-depth1 &#xff08;检索文件的最大深度1&#xff0c;即只检索汇总计算当前目录下的文件&#xff09; 4、进入占用最大的 /containers文件夹&am…

pycharm配置conda虚拟环境

&#x1f4d5;作者简介&#xff1a;热编程的贝贝&#xff0c;致力于C/C、Java、Python等多编程语言&#xff0c;热爱跑步健身&#xff0c;喜爱音乐的一位博主。 &#x1f4d7;本文收录于贝贝的日常汇报系列&#xff0c;大家有兴趣的可以看一看 &#x1f4d8;相关专栏深度学习、…

【数据结构】堆的初始化——如何初始化一个大根堆?

文章目录 源码是如何插入的&#xff1f;扩容向上调整实现大根堆代码&#xff1a; 源码是如何插入的&#xff1f; 扩容 在扩容的时候&#xff0c;如果容量小于64&#xff0c;那就2倍多2的扩容&#xff1b;如果大于64&#xff0c;那就1.5倍扩容。 还会进行溢出的判断&#xff0c…