当前位置:网站首页>LeetCode:221. 最大正方形
LeetCode:221. 最大正方形
2022-07-06 08:44:00 【Bertil】
在一个由 ‘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’
解题思路
1.首先定义一个数组dp表示以[i][j]为正方形右下角的最大边长,定义一个变量max_len表示最大正方形的边长
2.状态转移方程:dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;(取三者的最小值是因为要构成正方形)
3.注意:若左边和上边的点为’1’,则dp[i][j] = 1
代码
/** * @param {character[][]} matrix * @return {number} */
var maximalSquare = function(matrix) {
let max_len = 0;
let dp = Array.from(Array(matrix.length), () => Array(matrix[0].length).fill(0));
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] === '1') {
if (i === 0 || j === 0) {
dp[i][j] = 1;
}else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
}
max_len = Math.max(max_len, dp[i][j]);
}
}
}
return max_len ** 2;
};
边栏推荐
- 目标检测——Pytorch 利用mobilenet系列(v1,v2,v3)搭建yolov4目标检测平台
- Deep analysis of C language pointer
- win10系统中的截图,win+prtSc保存位置
- sublime text中conda环境中plt.show无法弹出显示图片的问题
- View computer devices in LAN
- 同一局域网的手机和电脑相互访问,IIS设置
- PLT in Matplotlib tight_ layout()
- What are the common processes of software stress testing? Professional software test reports issued by companies to share
- MySQL learning records 12jdbc operation transactions
- 如何有效地进行自动化测试?
猜你喜欢
Verrouillage [MySQL]
生成器参数传入参数
Deep learning: derivation of shallow neural networks and deep neural networks
MySQL learning record 11jdbcstatement object, SQL injection problem and Preparedstatement object
Unified ordering background interface product description Chinese garbled
Cisp-pte practice explanation
[embedded] cortex m4f DSP Library
2022.02.13 - NC001. Reverse linked list
[embedded] print log using JLINK RTT
Roguelike游戏成破解重灾区,如何破局?
随机推荐
Screenshot in win10 system, win+prtsc save location
优秀的软件测试人员,都具备这些能力
Indentation of tabs and spaces when writing programs for sublime text
Current situation and trend of character animation
超高效!Swagger-Yapi的秘密
生成器参数传入参数
Light of domestic games destroyed by cracking
游戏解包的危害及资源加密的重要性
Research and investment forecast report of citronellol industry in China (2022 Edition)
Synchronized solves problems caused by sharing
堆排序详解
Deep anatomy of C language -- C language keywords
Analysis of the source code of cocos2d-x for mobile game security (mobile game reverse and protection)
Roguelike game into crack the hardest hit areas, how to break the bureau?
【嵌入式】使用JLINK RTT打印log
marathon-envs项目环境配置(强化学习模仿参考动作)
[MySQL] log
PLT in Matplotlib tight_ layout()
如何进行接口测试测?有哪些注意事项?保姆级解读
tree树的精准查询