在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
示例:
正方形内最大的圆面积?输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
——————————————————————————————————————————
解题思路:使用动态规划,dp[i][j]表示以当前结点为正方形的边界点所能形成的最大的正方形。考虑其状态方程,有
leetcode第二题?dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]),其前提条件是nums[i][i]!=0;
用图表示为:
其C++代码如下:
class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int hang = matrix.size();if(hang==0) //判断是否为零维矩阵return 0;int lie = matrix[0].size();vector<vector<int>> dp(hang+1,vector<int>(lie+1,0)); //用于存储状态量,使用+1是为了可以直接讨论初始状态int num = 0;for(int i=0;i<hang;i++){for(int j=0;j<lie;j++){if(matrix[i][j]!='0') //使用状态转移方程的前提条件dp[i+1][j+1] = min(dp[i][j],min(dp[i][j+1],dp[i+1][j])) + 1;num = max(num,dp[i+1][j+1]); }}return num*num;}
};
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态