subject :

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.

Topic link :https://leetcode.com/problems/maximal-square/.

This question is a bit similar :LeetCode OJ And Maximal Rectangle ( Largest rectangle ). But the solution is totally different .

Ideas :

Dynamic programming . set up f[i][j] Represents the maximum length of the square containing the current point , There is a recurrence relation, such as the following :

f[0][j] = matrix[0][j]
f[i][0] = matrix[i][0]
For i > 0 and j > 0:
if matrix[i][j] = 0, f[i][j] = 0;
if matrix[i][j] = 1, f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1.

Code 1:

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int row = matrix.size();
if(row == 0)
return 0;
int col = matrix[0].size();
vector<vector<int> > f(row , vector<int>(col , 0));
int maxsize = 0; // Maximum side length
for(int i = 0 ; i < row ; i++)
{
for(int j = 0 ; j < col ; j++)
{
if(i == 0 || j == 0)
f[i][j] = matrix[i][j]-'0';
else
{
if(matrix[i][j] == '0')
f[i][j] = 0;
else
f[i][j] = min(min(f[i-1][j] , f[i][j-1]) , f[i-1][j-1]) + 1;
}
maxsize = max(maxsize , f[i][j]);
}
}
return maxsize * maxsize;
} };

Code 2:

The optimization space is one dimension

class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int row = matrix.size();
if(row == 0)
return 0;
int col = matrix[0].size(); vector<int> f(col , 0); int tmp1 = 0 , tmp2 = 0; int maxsize = 0; // Maximum side length
for(int i = 0 ; i < row ; i++)
{
for(int j = 0 ; j < col ; j++)
{
tmp1 = f[j]; //tmp1 Put the present f[j] Save the following , For the next inference f[i+1][j+1] Top left corner of f[i-1][j-1]
if(i == 0 || j == 0)
f[j] = matrix[i][j]-'0';
else
{
if(matrix[i][j] == '0')
f[j] = 0;
else
f[j] = min(min(f[j-1] , f[j]) , tmp2) + 1; // there tmp2 That's the code 1 Of f[i-1][j-1]
}
tmp2 = tmp1 ; // hold tmp1 Assign to tmp2, For next time for Circular search f[j+1]
maxsize = max(maxsize , f[j]);
}
}
return maxsize * maxsize;
} };

LeetCode OJ And Maximal Square ( The largest square ) More articles about

  1. LeetCode OJ:Maximal Square( The largest rectangle )

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

  2. 【LeetCode】221. Maximal Square

    Maximal Square Given a 2D binary matrix filled with 0's and 1's, find the largest square containing ...

  3. 50.Maximal Square( The largest square )

    Level   Medium Title Description : Given a 2D binary matrix filled with 0's and 1's, find the largest square conta ...

  4. 【LeetCode 221】Maximal Square

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

  5. LeetCode OJ:Maximal Rectangle( The largest rectangle )

    Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and ...

  6. LeetCode OJ 85. Maximal Rectangle

    Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and ...

  7. Find the maximum square area — leetcode 221. Maximal Square

    I wanted to be like Yuanyou , Write a summary farewell 2015, Or say goodbye to the passing year of the sheep , But what happened in the past year , It's really beyond the imagination of ordinary people , It's not representative either , So the plan is this year 6 Write an article in September " Half year summary " ...

  8. [LintCode] Maximal Square The largest square

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

  9. leetcode How to solve problems everyday 221 Maximal Square

    Problem description : Topic link :221 Maximal Square The solution to the problem is to give a M*N Matrix , Only '1', '0', Two elements : You need to find out from '1' The largest square of the composition . Okay , this is it . We see ...

Random recommendation

  1. Chapter two TP-Link 703N OpenWrt Brush back the original firmware

    (TP Official website ) First, download the original firmware Use terminal , Use cat /proc/mtd View the upgrade commands supported by routing , My is root@OpenWrt:~# cat /proc/mtd dev:    size   erases ...

  2. spring in @param and mybatis in @param Use difference

    spring in @param /** * Query whether the specified user and enterprise have configured roles * @param businessId memberId * @return */ int selectRoleCount ...

  3. VirtualBox Create a virtual computer 、 perform Genymotion The simulator reported an error

    When installed Genynition About Android After debugging the simulator for the application , stay Genymotion Execution platform virtualBox:VirtualBox Create a virtual computer . perform Genymotion The simulator reported an error : Misselling ...

  4. SQLite senior : One database builds multiple tables , Wrapper class

    package eoe.database; import android.content.Context; import android.database.sqlite.SQLiteDatabase; ...

  5. C# Multithreading timeout processing practice in

    Recently I've been dealing with C# About China timeout Some aspects of behavior bug. The solution is very interesting , So I'm here to share with you . I want to deal with the following situations : We made an application , There is a module in the program , Its function is to show the user a ...

  6. django-rest-framework Class based view of

    Preface : In the last blog post , It's mainly about requests and responses , Inside the project views.py The view functions in are all function based , And we introduced @api_view This is a very useful decorator . meanwhile , We also introduced APIView This class , But I haven't used it yet ...

  7. Java Constructors and the use of constructors

    We're in the process of building normal classes , There may be a lot of problems , Scalability . Security and so on . Imagine , Such a scene , Now we're going to create a class , Among them is 6 Attributes , Among them are 4 The value of a property is not very certain ( Maybe an object doesn't need one of its values ), ...

  8. azkaban Comparison of workflow scheduler and related tools

    Reprinted from : Workflow scheduler azkaban, It is mainly used for architecture selection , Please refer to :Azkaban Installation and introduction ,azkaban Simple use Why do we need a workflow scheduling system A complete data analysis system is usually composed of a large number of task units : ...

  9. 20165305 Experiment 1 : Java Familiarity with development environment

    experiment 1-1 establish " My student number exp1" The catalog of . stay " My student number exp1" Create under directory src,bin Such as catalog . javac,java Execution in " My student number exp1& ...

  10. centos7.3 Fast installation mariadb(mysql)

    From the latest version of linux The system starts , The default is Mariadb instead of mysql! Use the system's own repos Easy to install : yum install mariadb mariadb-server systemct ...