当前位置:网站首页>leetcode:1139. The largest square bounded by 1
leetcode:1139. The largest square bounded by 1
2022-07-05 21:01:00 【Oceanstar's study notes】
Title source
Title Description
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
}
};
for instance : It can be seen with the naked eye that the side length of an array that meets the conditions is 33 , It is also the largest side length .
vector<vector<int>> grid ={
{
0, 1, 0, 1, 1},
{
1, 1, 1, 1, 1},
{
1, 1, 0, 1, 1},
{
1, 1, 1, 1, 0},
{
0, 1, 1, 1, 1},
{
1, 1, 1, 0, 1},
{
0, 1, 1, 1, 1},
{
1, 1, 1, 0, 1}
};
std::vector<std::vector<int>> grid = {
{
1, 1, 1},
{
1, 0, 1},
{
1, 1, 1}
};
title
Dynamic programming
class Solution {
public:
// Using the idea of dynamic planning , Create a three-dimensional array to store the left and top continuous 1 The number of
int largest1BorderedSquare(vector<vector<int>>& grid) {
if(grid.empty()){
return 0;
}
int length = grid.size(); // Length of matrix
int width = grid[0].size(); // The width of the matrix
// use dp[i][j][0] To represent the i Xing di j Column On the left Successive 1 The number of
// use dp[i][j][1] To represent the i Xing di j Column above Successive 1 The number of
std::vector<std::vector<std::vector<int>>> dp(
length + 1, std::vector<std::vector<int>>(
width + 1, std::vector<int>(
2, 0
)
)
);
int maxLen = 0;
for (int i = 1; i <= length; ++i) {
for (int j = 1; j <= width; ++j) {
if(grid[i - 1][j - 1] == 1){
// Because the code above i and j from 1 Start , To m,n end , It can be understood as adding a layer on the left and top of the rectangle 0, So actually dp[i][j][0] It's actually grid[i-1][j-1] Continuous on the left 1 The number of ( Include yourself ), This is actually done to facilitate initialization , Avoid writing too much if-else, Is a very common skill
dp[i][j][0] += dp[i][j - 1][0] + 1;
dp[i][j][1] += dp[i - 1][j][1] + 1;
// Try to i Xing di j Column ( Current point ) Form a square for the lower right corner
int len = std::min(dp[i][j][0], dp[i][j][1]); // Maximum possible length
while (len > 0){
// Judge whether there is continuity on the left side of the upper right corner of this possible square len individual 1 && Whether there is continuity above the lower left corner len individual 1
if(dp[i - len + 1][j][0] >= len && dp[i][j - len + 1][1] >= len){
break;
}
len--;
}
maxLen = std::max(maxLen, len);
}
}
}
return maxLen * maxLen;
}
};
边栏推荐
- 获取前一天的js(时间戳转换)
- Determine the best implementation of horizontal and vertical screens
- Monorepo management methodology and dependency security
- Hdu2377bus pass (build more complex diagram +spfa)
- The development of research tourism practical education helps the development of cultural tourism industry
- SYSTEMd resolved enable debug log
- Which is the best online collaboration product? Microsoft loop, notion, flowus
- Research and development efficiency improvement practice of large insurance groups with 10000 + code base and 3000 + R & D personnel
- Mathematical analysis_ Notes_ Chapter 9: curve integral and surface integral
- Abnova cyclosporin a monoclonal antibody and its research tools
猜你喜欢
ArcGIS\QGIS无插件加载(无偏移)MapBox高清影像图
Analyze the knowledge transfer and sharing spirit of maker Education
【案例】元素的显示与隐藏的运用--元素遮罩
How to make ERP inventory accounts of chemical enterprises more accurate
Enclosed please find. Net Maui's latest learning resources
学习机器人无从下手?带你体会当下机器人热门研究方向有哪些
ArcGIS栅格重采样方法介绍
Phpstudy Xiaopi's MySQL Click to start and quickly flash back. It has been solved
Cutting edge technology for cultivating robot education creativity
Prosci LAG-3 recombinant protein specification
随机推荐
解读协作型机器人的日常应用功能
研學旅遊實踐教育的開展助力文旅產業發展
Enclosed please find. Net Maui's latest learning resources
最长摆动序列[贪心练习]
WPF gets the control in the datagridtemplatecolumn of the specified row and column in the DataGrid
How to make ERP inventory accounts of chemical enterprises more accurate
Research and development efficiency improvement practice of large insurance groups with 10000 + code base and 3000 + R & D personnel
matplotlib绘图润色(如何形成高质量的图,例如设如何置字体等)
[case] Application of element display and hiding -- element mask
显示器要申请BS 476-7 怎么送样?跟显示屏一样吗??
sql系列(基础)-第二章 限制和排序数据
基於flask寫一個接口
基于AVFoundation实现视频录制的两种方式
hdu2377Bus Pass(构建更复杂的图+spfa)
Comparison table of foreign lead American abbreviations
Using webassembly to operate excel on the browser side
示波器探头对测量带宽的影响
ts 之 泛型
【案例】定位的运用-淘宝轮播图
2.<tag-哈希表, 字符串>补充: 剑指 Offer 50. 第一个只出现一次的字符 dbc