# 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

- 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 ...

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

- 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 ...

- 【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 ...

- 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 ...

- 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 ...

- 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 " ...

- [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 ...

- 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

- 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 ...

- 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 ...

- 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 ...

- SQLite senior ： One database builds multiple tables , Wrapper class
package eoe.database; import android.content.Context; import android.database.sqlite.SQLiteDatabase; ...

- 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 ...

- 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 ...

- 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 ), ...

- 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 : ...

- 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& ...

- 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 ...