LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

2024-09-08 15:04

本文主要是介绍LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

64. 最大正方形

题目链接

题目描述

给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。

示例1:

输入: 1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0输出: 4

示例2:

输入: 0 1 1 0 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1输出: 9

解题思路

这道题的思路是使用动态规划来解决。

首先,我们可以定义一个二维数组 dp,其中 dp[i][j] 表示以矩阵中第 i 行第 j 列为右下角的最大正方形的边长。

然后,我们可以从左上角开始,逐行逐列地更新 dp 数组。

如果当前matrix[i][j]1,则 dp[i][j] 可以由以下三个位置的较小值加 1 得到:

  • dp[i-1][j]
  • dp[i][j-1]
  • dp[i-1][j-1]

依据此,我们可以写出状态转移方程:

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

初始条件:

dp[0][j] = 1 if matrix[0][j] == '1'
dp[i][0] = 1 if matrix[i][0] == '1'

最后,我们返回 dp 数组中最大值乘以最大值,即为最大正方形的面积。

复杂度分析

  • 时间复杂度: O ( n m ) O(nm) O(nm),其中 n n n m m m 分别是矩阵的行数和列数。
  • 空间复杂度: O ( n m ) O(nm) O(nm),其中 n n n m m m 分别是矩阵的行数和列数。

代码实现

Go版本

func maximalSquare(matrix [][]byte) int {n:=len(matrix)m:=len(matrix[0])dp:=make([][]int,n)res:=0for i:=range dp{dp[i]=make([]int,m)if(matrix[i][0]=='1'){dp[i][0]=1res=1}}for j:=0;j<m;j++{if(matrix[0][j]=='1'){dp[0][j]=1res=1}}for  i:=1;i<n;i++{for  j:=1;j<m;j++{if(matrix[i][j]=='1'){dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1}res=max(res,dp[i][j])}}return res*res
}

Python版本

class Solution(object):def maximalSquare(self, matrix):n=len(matrix)m=len(matrix[0])dp=[[0]*m for i in range(n)]res=0 for i in range(n):if matrix[i][0]=='1':res=1dp[i][0]=1for j in range(m):if matrix[0][j]=='1':res=1dp[0][j]=1for i in range(1,n):for j in range(1,m):if matrix[i][j]=='1':dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1res=max(res,dp[i][j])return res*res

C++版本

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();vector<vector<int>> dp(n, vector<int>(m, 0));int res = 0;for (int i = 0; i < n; ++i) {if (matrix[i][0] == '1') {dp[i][0] = 1;res = 1;}}for (int j = 0; j < m; ++j) {if (matrix[0][j] == '1') {dp[0][j] = 1;res = 1;}}for (int i = 1; i < n; ++i) {for (int j = 1; j < m; ++j) {if (matrix[i][j] == '1') {dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;res = max(res, dp[i][j]);}}}return res * res;  }
};

这篇关于LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1148440

相关文章

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

Feign Client超时时间设置不生效的解决方法

《FeignClient超时时间设置不生效的解决方法》这篇文章主要为大家详细介绍了FeignClient超时时间设置不生效的原因与解决方法,具有一定的的参考价值,希望对大家有一定的帮助... 在使用Feign Client时,可以通过两种方式来设置超时时间:1.针对整个Feign Client设置超时时间

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义