当前位置:网站首页>LeetCode:221. Largest Square
LeetCode:221. Largest Square
2022-07-06 08:51:00 【Bertil】
In a ‘0’ and ‘1’ In the two-dimensional matrix , Found contains only ‘1’ The largest square of , And return its area .
Example 1:
Input :matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output :4
Example 2:
Input :matrix = [["0","1"],["1","0"]]
Output :1
Example 3:
Input :matrix = [["0"]]
Output :0
Tips :
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 300
- matrix[i][j] by ‘0’ or ‘1’
Their thinking
1. First define an array dp Said to [i][j] Is the maximum side length of the lower right corner of the square , Define a variable max_len Represents the side length of the largest square
2. State transition equation :dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;( The minimum value of the three is taken because it is necessary to form a square )
3. Be careful : If the points on the left and top are ’1’, be dp[i][j] = 1
Code
/** * @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;
};
边栏推荐
- [embedded] cortex m4f DSP Library
- 角色动画(Character Animation)的现状与趋势
- Detailed explanation of heap sorting
- Cesium draw points, lines, and faces
- LeetCode:劍指 Offer 42. 連續子數組的最大和
- 数学建模2004B题(输电问题)
- Super efficient! The secret of swagger Yapi
- Image, CV2 read the conversion and size resize change of numpy array of pictures
- LeetCode:236. 二叉树的最近公共祖先
- Export IEEE document format using latex
猜你喜欢
LeetCode:498. 对角线遍历
Fairguard game reinforcement: under the upsurge of game going to sea, game security is facing new challenges
ROS compilation calls the third-party dynamic library (xxx.so)
Analysis of the source code of cocos2d-x for mobile game security (mobile game reverse and protection)
Visual implementation and inspection of visdom
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
ESP8266-RTOS物联网开发
Excellent software testers have these abilities
After reading the programmer's story, I can't help covering my chest...
MySQL uninstallation and installation methods
随机推荐
marathon-envs项目环境配置(强化学习模仿参考动作)
UML圖記憶技巧
Swagger setting field required is mandatory
Restful API design specification
torch建立的网络模型使用torchviz显示
Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
软件压力测试常见流程有哪些?专业出具软件测试报告公司分享
如何进行接口测试测?有哪些注意事项?保姆级解读
Computer graduation design PHP Zhiduo online learning platform
优秀的软件测试人员,都具备这些能力
LeetCode:剑指 Offer 03. 数组中重复的数字
个人电脑好用必备软件(使用过)
UML图记忆技巧
@Jsonbackreference and @jsonmanagedreference (solve infinite recursion caused by bidirectional references in objects)
Navicat premium create MySQL create stored procedure
随手记01
win10系统中的截图,win+prtSc保存位置
深度剖析C语言数据在内存中的存储
Screenshot in win10 system, win+prtsc save location
egg. JS getting started navigation: installation, use and learning