LeetCode:最大正方形
题目
【LeetCode:最大正方形】在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
解题思路
使用动态规划的思想，对于matrix[i][j]对应的dp[i][j]表示i，j作为正方形的右下角的正方形边长，当dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]存在零的时候，dp[i][j]为matrix[i][j]的值，当都不为零时，dp[i][j] 为三个值中最小的值+1。
代码
class Solution {
public:
int maximalSquare(vector>& matrix) {
if(matrix.size() == 0) return 0;
int dp[matrix.size()][matrix[0].size()] = {0};
int maxRec = 0;
//初始化
for(int i=0;
i < matrix.size();
i++){
dp[i][0] = matrix[i][0] - '0';
maxRec = max(matrix[i][0] - '0', maxRec);
}for(int j = 0;
j < matrix[0].size();
j++){
dp[0][j] = matrix[0][j] - '0';
maxRec = max(matrix[0][j]-'0', maxRec);
}//开始查找
for(int i=1;
i < matrix.size();
i++){
for(int j=1;
j < matrix[0].size();
j++){
if(matrix[i][j] == '1'){
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
maxRec = max(dp[i][j], maxRec);
}else{
dp[i][j] = 0;
}
}
}
return maxRec*maxRec;
}
};
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 无私便是最大的自私---多久没有无私过了
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- 人最大的教养，是原谅父母的不完美.读后感
- Leetcode|Leetcode No.198打家劫舍
- 股票最大利润|股票最大利润 II
- 公司最大的问题在中层|公司最大的问题在中层 管理