当前位置:网站首页>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;
};
边栏推荐
- Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
- Charging interface docking tutorial of enterprise and micro service provider platform
- Promise 在uniapp的简单使用
- C语言深度解剖——C语言关键字
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- 堆排序详解
- What is the role of automated testing frameworks? Shanghai professional third-party software testing company Amway
- poi追加写EXCEL文件
- hutool优雅解析URL链接并获取参数
- ESP8266-RTOS物联网开发
猜你喜欢
Beijing invitation media
游戏解包的危害及资源加密的重要性
Computer cleaning, deleted system files
Cisp-pte practice explanation
生成器参数传入参数
tree树的精准查询
Bottom up - physical layer
Sort according to a number in a string in a column of CSV file
2022.02.13 - NC003. Design LRU cache structure
Unified ordering background interface product description Chinese garbled
随机推荐
China high purity silver nitrate Market Research and investment strategy report (2022 Edition)
Tcp/ip protocol
如何进行接口测试测?有哪些注意事项?保姆级解读
Visual implementation and inspection of visdom
POI add write excel file
可变长参数
View computer devices in LAN
visdom可视化实现与检查介绍
What are the common processes of software stress testing? Professional software test reports issued by companies to share
按位逻辑运算符
JVM performance tuning and practical basic theory - Part 1
China vanadium battery Market Research and future prospects report (2022 Edition)
swagger设置字段required必填
Precise query of tree tree
Promise 在uniapp的简单使用
gcc动态库fPIC和fpic编译选项差异介绍
Deep analysis of C language data storage in memory
JS pure function
Indentation of tabs and spaces when writing programs for sublime text
游戏解包的危害及资源加密的重要性