当前位置:网站首页>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;
};
边栏推荐
- egg. JS project deployment online server
- 查看局域网中电脑设备
- Problems in loading and saving pytorch trained models
- Function coritization
- 2022.02.13 - NC003. Design LRU cache structure
- sys. argv
- win10系统中的截图,win+prtSc保存位置
- The problem and possible causes of the robot's instantaneous return to the origin of the world coordinate during rviz simulation
- 移位运算符
- Roguelike game into crack the hardest hit areas, how to break the bureau?
猜你喜欢
Synchronized solves problems caused by sharing
MySQL learning record 11jdbcstatement object, SQL injection problem and Preparedstatement object
[MySQL] log
Deep learning: derivation of shallow neural networks and deep neural networks
Excellent software testers have these abilities
游戏解包的危害及资源加密的重要性
Detailed explanation of heap sorting
Promise 在uniapp的简单使用
FairGuard游戏加固:游戏出海热潮下,游戏安全面临新挑战
[embedded] cortex m4f DSP Library
随机推荐
gcc动态库fPIC和fpic编译选项差异介绍
Image,cv2读取图片的numpy数组的转换和尺寸resize变化
Navicat premium create MySQL create stored procedure
Deep analysis of C language pointer
China polyether amine Market Forecast and investment strategy report (2022 Edition)
marathon-envs项目环境配置(强化学习模仿参考动作)
2022.02.13 - NC002. sort
The network model established by torch is displayed by torch viz
优秀的软件测试人员,都具备这些能力
After PCD is converted to ply, it cannot be opened in meshlab, prompting error details: ignored EOF
[MySQL] lock
深度剖析C语言数据在内存中的存储
【MySQL】鎖
MySQL learning records 12jdbc operation transactions
Unsupported operation exception
【ROS】usb_ Cam camera calibration
torch建立的网络模型使用torchviz显示
Mobile phones and computers on the same LAN access each other, IIS settings
Research and investment forecast report of citronellol industry in China (2022 Edition)
C语言双指针——经典题型