当前位置:网站首页>leetcode:1139. 最大的以 1 为边界的正方形
leetcode:1139. 最大的以 1 为边界的正方形
2022-07-05 20:43:00 【OceanStar的学习笔记】
题目来源
题目描述
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
}
};
举个例子:可以肉眼看出一个满足条件的数组边长为 33 ,同时也是最大边长。
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}
};
题目解析
动态规划
class Solution {
public:
// 运用动态规划的思想,建立一个三维数组来存储每个点的左侧和上方连续的1的个数
int largest1BorderedSquare(vector<vector<int>>& grid) {
if(grid.empty()){
return 0;
}
int length = grid.size(); //矩阵的长
int width = grid[0].size(); //矩阵的宽
//用dp[i][j][0]来表示第i行第j列的 左边 连续的1的个数
//用dp[i][j][1]来表示第i行第j列的 上面 连续的1的个数
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){
//因为上面的代码 i 和 j 都是从1开始,到m,n结束,可以理解为在矩形的左边和上边加了一层0,所以实际的dp[i][j][0]其实是grid[i-1][j-1]左边连续的1的个数(包括自身),这样做其实就是为了方便初始化,避免写太多的if-else,是一种很常见的技巧
dp[i][j][0] += dp[i][j - 1][0] + 1;
dp[i][j][1] += dp[i - 1][j][1] + 1;
//尝试以第i行第j列(当前点)为右下角构成正方形
int len = std::min(dp[i][j][0], dp[i][j][1]); //最大可能长度
while (len > 0){
//判断这个可能的正方形右上角左侧是否有连续len个1 && 左下角的上方是否有连续len个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;
}
};
边栏推荐
- Document method
- Frequent MySQL operations cause table locking problems
- Abbkine BCA法 蛋白质定量试剂盒说明书
- Common view container class components
- Return to blowing marshland -- travel notes of zhailidong, founder of duanzhitang
- Informatics Olympiad 1338: [example 3-3] hospital setting | Luogu p1364 hospital setting
- 挖财商学院给的证券账户安全吗?可以开户吗?
- Informatics Olympiad 1340: [example 3-5] extended binary tree
- How to renew NPDP? Here comes the operation guide!
- 3.3、项目评估
猜你喜欢
Pytorch 1.12 was released, officially supporting Apple M1 chip GPU acceleration and repairing many bugs
National Eye Care Education Conference, 2022 the Fourth Beijing International Youth eye health industry exhibition
Duchefa p1001 plant agar Chinese and English instructions
Prosci LAG-3 recombinant protein specification
Ros2 topic [01]: installing ros2 on win10
Kubernetes resource object introduction and common commands (V) - (configmap & Secret)
Use of form text box (II) input filtering (synthetic event)
Duchefa细胞分裂素丨二氢玉米素 (DHZ)说明书
教你自己训练的pytorch模型转caffe(二)
Use of thread pool
随机推荐
重上吹麻滩——段芝堂创始人翟立冬游记
[quick start of Digital IC Verification] 2. Through an example of SOC project, understand the architecture of SOC and explore the design process of digital system
Maker education infiltrating the transformation of maker spirit and culture
How to renew NPDP? Here comes the operation guide!
ProSci LAG3抗体的化学性质和应用说明
解析创客教育的知识迁移和分享精神
Abnova丨 MaxPab 小鼠源多克隆抗体解决方案
Specification of protein quantitative kit for abbkine BCA method
王老吉药业“关爱烈日下最可爱的人”公益活动在南京启动
小程序事件绑定
Relationship between mongodb documents
Usaco3.4 "broken Gong rock" band raucous rockers - DP
[UE4] unrealinsight obtains the real machine performance test report
Mathematical analysis_ Notes_ Chapter 9: curve integral and surface integral
Duchefa丨MS培养基含维生素说明书
National Eye Care Education Conference, 2022 the Fourth Beijing International Youth eye health industry exhibition
Abnova DNA marker high quality control test program
Frequent MySQL operations cause table locking problems
如何让化工企业的ERP库存账目更准确
Informatics Orsay all in one 1339: [example 3-4] find the post order traversal | Valley p1827 [usaco3.4] American Heritage