当前位置:首页 > 智能硬件 > 人工智能AI
[导读] 题目描述:给定二维0,1串的矩阵,找出最大的正方形的只有1串的区域。 例如: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 答案

题目描述:给定二维0,1串的矩阵,找出最大的正方形的只有1串的区域。
例如:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

答案为4.

解题思路:动态规划。
dp[i][j]是以(i,j)为右下角顶点的最大正方形的边长。

矩阵从左到右、从上到下进行扫描,当发现:
1. (i, j), (i-1, j), (i, j-1)三个位置都为1的时候,(i, j)这个值能够与这个值左边上边的某个大小的区域组成一个矩阵。例如:

1 0 1 0 0
1 0 1 1 1
1 1 1 1

接下来扫描(2, 4),发现(i, j), (i-1, j), (i, j-1)三个位置都为1,那么(i, j)这个值能够与另外五个1构成一个矩阵。
但是题目要求的是正方形的大小,因此还要找出dp(i-1, j-1), dp(i-1, j), dp(i, j-1)中的最小值min,这个最小值是以这三个值为右下角顶点的三个正方形中的最小边长,而扫描(i, j)这个值我们发现它能够补成一个更大的矩阵,因此这个补上之后最小正方形的边长必定能够增加1,因此令dp(i, j) = min + 1.
之所以要找dp(i-1, j-1), dp(i-1, j), dp(i, j-1)中的最小值,是因为补上的是一个矩阵,而矩阵的宽限制了正方形的边长。
2. (i, j), (i-1, j), (i, j-1)三个位置有一个为0时,肯定无法补成一个矩形,因此dp(i, j) = 0.

扫描过程中,变量res纪录了所找到的最大的正方形的边长。

最终代码如下:

class SoluTIon {

public:

int maximalSquare(vector《vector《char》》& matrix) {

if(matrix.size() == 0) return 0;

int row = matrix.size(), col = matrix[0].size();

int res = 0;

vector《int》 dp(col, 0);

// first row

for(int i = 0;i 《 col;i++) dp[i] = matrix[0][i] - ‘0’;

res = max(res, *max_element(dp.begin(), dp.end()));

// dp

for(int i = 1;i 《 row;i++) {

// first col

dp[0] = matrix[i][0] - ‘0’;

// other cols

for(int j = 1;j 《 col;j++) {

if(matrix[i][j] == ‘1’) {

int temp = min(dp[j], dp[j-1]);

dp[j] = temp + (matrix[i-temp][j-temp] - ‘0’);

} else {

dp[j] = 0;

}

}

res = max(res, *max_element(dp.begin(), dp.end()));

}

return res * res;

}

};

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除( 邮箱:macysun@21ic.com )。
换一批
延伸阅读

Python和Java是两种广泛应用于编程领域的高级编程语言,它们各有优劣。本文从程序设计应用、系统资源占用、高性能处理和语言特点等四方面详细介绍两种编程语言的区别。

关键字: python java 高性能处理

在这篇文章中,小编将为大家带来Java接口的相关报道。如果你对本文即将要讲解的内容存在一定兴趣,不妨继续往下阅读哦。

关键字: java 接口 Interface

应该有不少小伙伴有假期打工的经历,那今天就来给公众号的读者朋友们分享一个二哥编程星球里一个球友在富士康打工 50 天的感受,相信大家看完后会深深触动的。

关键字: 物联网 java 博客

在过去的几年中,Python的普及速度令人惊叹,Java的王者地位也常年不衰。目前两者的竞争愈发激烈,怎么选择成为了许多初学者萦绕心中的问题,网上有很多版本的说法牵引着他们的思维,让本来很简单的问题复杂化。

关键字: python java

我们都知道,浏览一个网页,有两个很主要的“电脑”在共同运行,一台是远程的,为你提供网页数据的“服务器”,一台是你正在使用的客户端电脑。

关键字: javascript java

在各种网页制作技术论坛中,常常有人询问javascript与Java有什么区别,甚至有人误认为javascript就是Java。javascript与Java确实有一定的联系,但它们并不像我们想象的那样联系紧密,甚至可以...

关键字: javascript java

对于很多初学者来讲,不太清楚Java和C语言的区别,为了让那个大家更清晰的了解,近日特意给大家归纳了一些两者的大致区别,希望能够给大家带来一定的帮助作用,也欢迎大家进行详细补充和归纳。

关键字: C语言 java

Java封装案例

关键字: java 实例

今天我们就要来讲讲看似线程安全的双重检查锁单例模式中可能会出现的指令重排问题。

关键字: java 单例模式 双重检查锁

今天我们来放松下心情,不聊分布式,云原生,来聊一聊初学者接触的最多的 java web 基础。

关键字: Spring xml java
关闭