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

【LeetCode】221.最大正方形

题目

在一个由 ‘0' 和 ‘1' 组成的二维矩阵内,找到只包含 ‘1' 的最大正方形,并返回其面积。

示例 1:

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4

示例 2:

输入:matrix = [["0","1"],["1","0"]]
输出:1

示例 3:

输入:matrix = [["0"]]
输出:0

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 ‘0' 或 ‘1'

解答

源代码

class Solution {public int maximalSquare(char[][] matrix) {int maxSide = 0;int[][] dp = new int[matrix.length][matrix[0].length];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (matrix[i][j] == '1') {if (i == 0 || j == 0) {dp[i][j] = 1;} else {dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;}}maxSide = Math.max(maxSide, dp[i][j]);}}return maxSide * maxSide;}
}

总结

隐隐觉得是动态规划,但是不知道怎么根据之前的dp值推算下一个dp值,看了题解学习到了新的思路:dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1。

相关文章:

【LeetCode】221.最大正方形

题目 在一个由 ‘0 和 ‘1 组成的二维矩阵内&#xff0c;找到只包含 ‘1 的最大正方形&#xff0c;并返回其面积。 示例 1&#xff1a; 输入&#xff1a;matrix [["1","0","1","0","0"],["1","0",&q…...

生成模型相关算法:EM算法步骤和公式推导

EM算法 引言EM算法例子及解法EM算法步骤和说明 引言 EM 算法是一种选代算法&#xff0c;1977 年 Dempster 等人总结提出&#xff0c;用于含有隐变量(hidden variable)的概率模型参数的极大似然估计&#xff0c;或极大后验概率估计EM算法的每次选代由两步组成:E步&#xff0c;求…...

Compose手势

Compose手势 本文链接&#xff1a; 点击 拖动 滑动 锚点 Compose Drag 拖动原理 Compose Drag 拖动原理:等待第一次按下 挂起 // UI展现出来的时候&#xff0c;这个while循环就已经在等待第一次按下了。事件 -> 恢复判断拖动合法性合法onDragStartonDragonDragEndforEa…...

【雕爷学编程】Arduino动手做(177)---ESP-32 掌控板2

37款传感器与执行器的提法&#xff0c;在网络上广泛流传&#xff0c;其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块&#xff0c;依照实践出真知&#xff08;一定要动手做&#xff09;的理念&#xff0c;以学习和交流为目的&am…...

Ubuntu-文件和目录相关命令

&#x1f52e;linux的文件系统结构 ⛳目录结构及目录路径 &#x1f9e9;文件系统层次结构标准FHS Filesystem Hierarchy Standard(文件系统层次结构标准&#xff09; Linux是开源的软件&#xff0c;各Linux发行机构都可以按照自己的需求对文件系统进行裁剪&#xff0c;所以众多…...

显式接口实现(C# 编程指南)

接口的实现可以有多种方式,下面是C#接口实现的几种方式欢迎交流 两个接口包含签名相同的成员 如果一个类实现的两个接口包含签名相同的成员,则在该类上实现此成员会导致这两个接口将此成员用作其实现。 如下示例中,所有对 Paint 的调用皆调用同一方法。 第一个示例定义类型…...

element-ui 图片上传 及 quillEditor富文本(图片视频上传)

<template><div class"card" style"overflow: hidden; padding-bottom: 10px"><div style"padding: 20px 20px 0 20px"><span class"title_top"><span class"top_icon"></span>基本信息…...

前端技术Vue学习笔记--002

前端技术Vue学习笔记 文章目录 前端技术Vue学习笔记1、指令修饰符2、v-bind对于样式控制的增强2.1、v-bind对于样式控制的增强--class2.2、v-bind对于样式控制的增强--操作style 3、v-model应用于其他表单元素4、计算属性4.1、**computed计算属性 vs methods方法的区别**4.2、计…...

【RabbitMQ(day4)】SpringBoot整合RabbitMQ与MQ应用场景说明

一、SpringBoot 中使用 RabbitMQ 导入对应的依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId></dependency>配置配置文件 spring:application:name: rabbitmq-springbo…...

想了解好用的翻译pdf的软件吗?

在全球化的时代背景下&#xff0c;跨国贸易越来越普遍&#xff0c;跨语言沟通也越来越频繁。小黄是一家跨国公司的员工&#xff0c;他梦想能在全球各地拓展自己的业务&#xff0c;奈何遇到了一个巨大的挑战&#xff1a;跨语言沟通。在这其中&#xff0c;pdf文件是他经常接收到的…...

docker安装nginx并配置SSL

1、拉取镜像 docker pull nginx2、启动nginx容器&#xff0c;复制一份默认配置文件出来 // 以nginx镜像为基础镜像创建一个名为nginx01的容器 docker run -d -p 80:80 --name nginx01 nginx创建成功后会看到nginx的欢迎页面 3、挂载nginx目录 拷贝nginx的配置信息到主机目录…...

【LeetCode 算法】Reorder List 重排链表

文章目录 Reorder List 重排链表问题描述&#xff1a;分析代码PointerReverseMerge Tag Reorder List 重排链表 问题描述&#xff1a; 给定一个单链表 L 的头节点 head &#xff0c;单链表 L 表示为&#xff1a; L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为&#…...

MQ面试题3

1、讲一讲Kafka与RocketMQ中存储设计的异同&#xff1f; Kafka 中文件的布局是以 Topic/partition &#xff0c;每一个分区一个物理文件夹&#xff0c;在分区文件级别实现文件顺序写&#xff0c;如果一个Kafka集群中拥有成百上千个主题&#xff0c;每一个主题拥有上百个分区&am…...

【Linux命令200例】patch 用于将补丁文件应用到源码中

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;全栈领域新星创作者✌&#xff0c;阿里云社区专家博主&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;本文已收录于专栏&#xff1a;Linux命令大全。 &#x1f3c6;本专栏我们会通过具体的系统的命令讲解加上鲜…...

一起来学算法(邻接矩阵)

前言&#xff1a; 邻接矩阵是数学和计算机科学中常用的一种表示方式&#xff0c;用来表述有向图或无向图&#xff0c;一张图由一组顶点&#xff08;或结点&#xff09;和一组表组成&#xff0c;用邻接矩阵就能表示这些顶点间存在的边的关系 1.图的概念 对于图而言&#xff0c;…...

hadoop与HDFS交互

一、利用Shell命令与HDFS进行交互 在进行HDFS编程实践前&#xff0c;需要首先启动Hadoop。可以执行如下命令启动Hadoop&#xff1a; cd /usr/local/hadoop ./sbin/start-dfs.sh #启动hadoop Hadoop支持很多Shell命令&#xff0c;其中fs是HDFS最常用的命令&#xff0c;利用fs…...

MYSQL 分区如何指定不同存储路径(多块磁盘)

理论 可以针对分区表的每个分区指定存储路径&#xff0c;对于innodb存储引擎的表只能指定数据路径&#xff0c;因为数据和索引是存储在一个文件当中&#xff0c;对于MYISAM存储引擎可以分别指定数据文件和索引文件&#xff0c;一般也只有RANGE、LIST分区、sub子分区才有可能需要…...

安全加固服务器

根据以下的内容来加固一台Linux服务器的安全。 首先是限制连续密码错误的登录次数&#xff0c;由于RHEL8之后都不再使用pam_tally.so和pam_tally2.so&#xff0c;而是pam_faillock.so 首先进入/usr/lib64/security/中查看有什么模块&#xff0c;确认有pam_faillock.so 因为只…...

Linux 命令学习:

1. PS命令 ps 的aux和-ef区别 1、输出风格不同&#xff0c;展示的格式略有不同 两者的输出结果差别不大&#xff0c;但展示风格不同。aux是BSD风格&#xff0c;-ef是System V风格。 2、aux会截断command列&#xff0c;而-ef不会&#xff0c;当结合grep时这种区别会影响到结果 …...

牛客网Verilog刷题——VL54

牛客网Verilog刷题——VL54 题目答案 题目 实现一个深度为8&#xff0c;位宽为4bit的双端口RAM&#xff0c;数据全部初始化为0000。具有两组端口&#xff0c;分别用于读数据和写数据&#xff0c;读写操作可以同时进行。当读数据指示信号read_en有效时&#xff0c;通过读地址信号…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...