程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode:Maximal Square淺析

LeetCode:Maximal Square淺析

編輯:關於C++

 

Maximal Square

  Total Accepted:25468Total Submissions:110270Difficulty: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.

 

Credits:
Special thanks to@Freezenfor adding this problem and creating all test cases.

 

Subscribeto see which companies asked this question

Hide Tags Dynamic Programming Hide Similar Problems (H) Maximal Rectangle            

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

思路:

1.動態規劃的題,可以維護一個ret[m*n]的整數數組去表示matrix各元素的狀態;

2.首先邊界i=0,j=0:第一行和第一列與matrix相同(即ret[i][0] = matrix[i][0],ret[0][i] = matrix[0][i]);

3.當i>0,j>0時,

如果matrix[i][j]=='0',ret[i][j]=0;

如果matrix[i][j]=='1',ret[i][j]由左上角的3個值推出;

推導公式,即狀態轉移方程為:ret[i][j]=min(ret[i-1][j],ret[i][j-1],ret[i-1][j-1]) + 1;

 

 

code:

 

class Solution {
public:
    int maximalSquare(vector>& matrix) {
        
        int m = matrix.size();
        if(m==0) return 0;
        int n = matrix[0].size();
        vector> ret(m, vector(n,0));
        int maxSize = 0;
        
        for(int i=0;i

 

 

當然還可以有一些空間上的優化:Easy DP solution in C++ with detailed explanations (8ms, O(n^2) time and O(n) space)

 

 

 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved