专栏首页aCloudDeveloperLeetCode: 221_Maximal Square | 二维0-1矩阵中计算包含1的最大正方形的面积 | Medium

LeetCode: 221_Maximal Square | 二维0-1矩阵中计算包含1的最大正方形的面积 | Medium

题目:

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area. 

For example, given the following matrix: 
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4. 

解题思路:

  这种包含最大、最小等含优化的字眼时,一般都需要用到动态规划进行求解。本题求面积我们可以转化为求边长,由于是正方形,因此可以根据正方形的四个角的坐标写出动态规划的转移方程式(画一个图,从左上角推到右下角,很容易理解):

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

根据此方程,就可以写出如下的代码:

代码展示:

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 //dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1;
 7 //where matrix[i][j] == 1
 8 int maximalSquare(vector<vector<char>>& matrix) 
 9 {
10     if (matrix.empty())
11         return 0;
12 
13     int rows = matrix.size();//行数
14     int cols = matrix[0].size(); //列数
15 
16     vector<vector<int> > dp(rows+1, vector<int>(cols+1, 0));
17     /*
18         0 0 0 0 0 0
19         0 1 0 1 0 0
20         0 1 0 1 1 1
21         0 1 1 1 1 1
22         0 1 0 0 1 0
23     */
24     int result = 0; //return result
25 
26     for (int i = 0; i < rows; i ++) {
27         for (int j = 0; j < cols; j ++) {
28             if (matrix[i][j] == '1') {
29                 int temp = min(dp[i][j], dp[i][j+1]);
30                 dp[i+1][j+1] = min(temp, dp[i+1][j]) + 1;
31             }
32             else 
33                 dp[i+1][j+1] = 0;
34             
35             result = max(result, dp[i+1][j+1]);
36         }
37     }
38     return result * result; //get the area of square;
39 }
40 
41 // int main()
42 // {
43 //     char *ch1 = "00000";
44 //     char *ch2 = "00000";
45 //     char *ch3 = "00000";
46 //     char *ch4 = "00000";
47 //     vector<char> veccol1(ch1, ch1 + strlen(ch1));
48 //     vector<char> veccol2(ch2, ch2 + strlen(ch2));
49 //     vector<char> veccol3(ch3, ch3 + strlen(ch3));
50 //     vector<char> veccol4(ch4, ch4 + strlen(ch4));
51 //     
52 //     vector<vector<char> > vecrow;
53 //     vecrow.push_back(veccol1);
54 //     vecrow.push_back(veccol2);
55 //     vecrow.push_back(veccol3);
56 //     vecrow.push_back(veccol4);
57 //     
58 //     vector<vector<char> > vec;
59 //     cout << maximalSquare(vec);
60 //     return 0;
61 // }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • VC库中快排函数的详解

    Author: bakari  Date:  2012.8.9 以前都是自己手动写这个算法,觉得也不是一件很麻烦的事,但现在写的程序基本上都用得着快排,重新去写...

    CloudDeveloper
  • 局部变量,静态局部变量,全局变量,静态全局变量在内存中的存放区别(转)

         我们先来看内存中的几大区:  内存到底分几个区? 下面有几种网上的理解,我整理一下: 一:  1、栈区(stack)— 由编译器自动分配释放 ,存放函...

    CloudDeveloper
  • 大神洗礼第三讲——接上一讲

    Author:bakari                 Date:2012.10.26 这一讲的主要内容和上一讲相同,是上一讲的深入分析。内存对齐涉及内存实...

    CloudDeveloper
  • 开发板通用刷机教程

        这是STM通用的刷固件方法,不仅仅适用于.Net Micro Framework,支持我们当前所有板子,包括阿波罗、探索者和雅典娜三个系列。     ...

    大石头
  • 如何将 Hexo 博客部署到云开发静态网站托管

    Hexo 是一个快速、简洁且高效的博客框架,依赖少易于安装使用,可以方便的生成静态网页托管在其他平台上,是搭建博客的首选框架。除了在 Github Pages ...

    腾讯云开发TCB
  • 微信小程序云开发 初学者入门教程一

    本教程适合刚刚入门的小白,云开发为开发者提供完整的云端支持,弱化后端和运维概念,无需搭建服务器,使用平台提供的 API 进行核心业务开发,即可实现快速上线和迭代...

    王小婷
  • 分支限界法

        我们可以按照行优先和列优先。 这里我们采用行优先,找出每一行最小值求和,那么最优解一定不会大于这个值,

    用户2965768
  • Windows查看网卡驱动版本

    2015版的驱动需要升级到2016版,参考这个文档进行驱动升级https://cloud.tencent.com/document/product/213/27...

    shawyang
  • 零基础利用腾讯云服务器搭建网站-服务器选购-环境一键配置

    地域可以随意的选择,操作系统选择centos,相对于Windows系统的话更加稳定,不会没有关系,这次是一点一点的教大家

    勤劳的小蜜蜂
  • 快速解决工作中的文本合并问题

    首先建立一个新列,给这个新列的列名起名字叫“辅助列1”,在C2单元格里写上公式【=B2】

    猴子数据分析

扫码关注云+社区

领取腾讯云代金券