当前位置: 首页 > news >正文

力扣 221. 最大正方形

目录

第一站 LeetCode 新手村

前言

1480. 一维数组的动态和221. 最大正方形1480. 一维数组的动态和

题目描述

解题思路

代码

总结

题目来源


第一站 LeetCode 新手村


前言

最近玩OJ赛,发现对算法的理解还需要更加扎实,code能力还可以进一步提升,所以做这样一个算法的系列文章,用于记录学习心得,交流经验,更好地进步和成长。


221. 最大正方形

题目描述

在一个由 '0' 和 '1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。

示例1

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4

示例 2

输入:matrix = [["0","1"],["1","0"]]
输出:1

 示例 3

输入:matrix = [["0"]]
输出:0

提示

  • m == matrix.length
    n == matrix[i].length
    1 <= m, n <= 300
    matrix[i][j] 为 '0' 或 '1'

解题思路

预知

LeetCode是核心代码模式,所以只需要考虑核心算法,输入由系统自动完成,最后的输出以return返回;

思路

动态规划

代码

C++

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
         if(matrix.size()==0 || matrix[0].size()==0){    //特殊情况的判断,若数组为空,或数组不为空,但其内容为空,返回0
            return 0;
        }
        int maxSide = 0;  //定义最大边,该图像是正方形,最后返回边的平方即可
        int rows = matrix.size(), columns = matrix[0].size(); 
        vector<vector<int>> dp(rows, vector<int>(columns));   //初始化包含row个vector<int>(columns)容器的vector容器     其实就是创建了一个和题目所给数据同样大小的二维数组

        for(int i=0;i<rows;i++){   //按行遍历数组
            for(int j=0;j<columns;j++){   //进入行遍历某一行的某个元素
                if(matrix[i][j]=='1'){    //当元素为1时开始记录
                    if(i==0 || j==0){     //如果是第一行或者是第一列
                        dp[i][j]=1;       //直接给该元素赋值
                    }else{
                        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                        //访问该元素上方和左侧,和左上侧对角元素 
                        //dp[i][j]代表右下角   而记录在dp[i][j]中的数就是最大边长
                        //正方形套正方形,若想构成一个边长为3的正方形其必经过3个边长为2的正方形
                    }
                    maxSide = max(maxSide, dp[i][j]);  //比较dp值并返回最大边长
                }
            }
        }
        int maxSquare = maxSide * maxSide;    //正方形面积
        return maxSquare;
    }
};


总结

以上就是今天要讲的内容,本文仅仅简单讲解了《最大正方形》这一题目,并对动态规划有了进一步的了解

l题目来源

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximal-square

相关文章:

  • 方差分析(ANOVA)
  • 【C语言基础】:数据在内存中的存储
  • jupyter notebook的各种问题和解决办法
  • 【计算机网络】第 11、12 问:流量控制和可靠传输机制有哪些?
  • 关于举办第十五届蓝桥杯全国软件和信息技术专业人才大赛——数字科技创新赛的通知
  • 【React】onClick点击事件传参的4种方式
  • Stable-Diffusion ubuntu服务器部署,报错解决方法(小白教程)
  • spring-boot-starter-validation - 实际开发常见使用归纳
  • 搭建 LNMP 架构
  • Prompt 编程的优化技巧
  • Leetcode3044. 出现频率最高的质数
  • xtu oj 1131 凹数
  • 爬虫报错:twisted.web._newclient.ResponseNeverReceived
  • 前后端分离技术渲染动态页面 - 表白墙(Servlet)
  • 关于springboot多环境设设置说明
  • 一幅长文细学CSS3
  • P2-Net:用于2D像素与3D点匹配的局部特征的联合描述符和检测器(ICCV 2021)
  • 电磁兼容(EMC)基础(二)
  • 面向终客户和设备制造商的Ethernet-APL
  • React.lazy与Suspence实现延迟加载
  • React 中 memo useMemo useCallback 到底该怎么用
  • git命令
  • Vue的思维导图
  • 【Linux】4.0进程控制
  • 【Python应用】自制截图取词小工具-- 解锁文字识别新姿势
  • MYSQL学习笔记(DDL[数据定义]、DML[数据操作]、DQL[数据查询])
  • SpringCloud学习笔记
  • FFT 快速傅里叶变换 NTT 快速数论变换
  • 王传福赚嗨了!比亚迪单季利润超50亿 还大量出口到欧洲
  • 带你趣学算法
  • 设计模式(四)—— 装饰者模式
  • [架构之路-48]:目标系统 - 系统软件 - Linux下的网络通信-4-快速数据平面开发套件DPDK-工作原理