区块链技术博客
www.b2bchain.cn

Leetcode最大正方形(C++)思路分析及代码

这篇文章主要介绍了Leetcode最大正方形(C++)思路分析及代码的讲解,通过具体代码实例进行22903 讲解,并且分析了Leetcode最大正方形(C++)思路分析及代码的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=22903

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

Leetcode最大正方形(C++)思路分析及代码

    • 题目
    • 思路
    • 代码

题目

Leetcode最大正方形(C++)思路分析及代码

思路

这道题第一眼感觉就是动态规划,因为之前过类似的题,但是还是太菜了,没有想到解决方法,看了题解后才发现思路其实挺简单的。

这里回顾一下动态规划和贪心算法。这两个算法都用到了局部最优解。两种算法要求问题都具有的一个性质就是“子问题最优性”。即,组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的。

贪心算法:结果与之前的每步最优解都有关,之前的最优解不会保留。

动态规划:一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解。

决定动态规划之后,首先就要找状态方程,我们假设从上往下,从左往右遍历,当已知某一点时,要判断是不是更大的正方形,要看三个点,对角线,和反对角线上的点。

根据遍历情况,如果假设该点为左上角、左下角、右上角,都会造成重复计算,所以我们设已知右下角,当对角线与反对角线上的点均为1时,该正方形边长为2。

对于更多的情况,该点为右下角正方形的最大边长时,它最大只可能为左上角、左下角、右上角正方形的边长+1,当左上角、左下角、右上角三个正方形边长相等时,是最完美条件,会结合出一个边长+1的三角形,而右下角的这一点会补上这个空缺。

若三个正方形边长不相等,则会有缺口,所以右下角正方形的边长选择三个中边长最小的+1。

我们得出状态方程 dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])+1

这里要注意min用了两个,因为min函数只能比较两个数值,所以三个要用两次。

代码

class Solution { public:     int maximalSquare(vector<vector<char>>& matrix) {         if(matrix.size()==0||matrix[0].size()==0){             return 0;         }         int rows = matrix.size(), columns = matrix[0].size(), MaxSize = 0;         vector<vector<int>> dp(rows, vector<int>(columns));         for(int i = 0; i < rows; i++){             for(int j = 0; j < columns; j++){                 if(matrix[i][j] == '1'){                     if((i==0||j==0))                         dp[i][j]=1;                     else                         dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;                     if(dp[i][j] > MaxSize)  MaxSize = dp[i][j];                 }             }         }         return MaxSize*MaxSize;     } }; 

本文转自互联网,侵权联系删除Leetcode最大正方形(C++)思路分析及代码

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » Leetcode最大正方形(C++)思路分析及代码
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们