leetcode764 Largest Plus Sign
2024-10-20 20:41:33
思路:
首先使用dp计算出在每个位置(i, j)上下左右最多有多少个连续的1,得到up[i][j], down[i][j], left[i][j], right[i][j]。然后计算这四个值中的最小值,所有最小值中的最大值就是答案。
实现:
class Solution
{
public:
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines)
{
vector<vector<int>> left(N, vector<int>(N, )), right(N, vector<int>(N, ));
vector<vector<int>> up(N, vector<int>(N, )), down(N, vector<int>(N, ));
vector<vector<int>> a(N, vector<int>(N, ));
for (int i = ; i < mines.size(); i++)
a[mines[i][]][mines[i][]] = ;
for (int i = ; i < N; i++)
{
left[i][] = (a[i][] == ? : );
right[i][N - ] = (a[i][N - ] == ? : );
for (int j = ; j < N; j++)
{
left[i][j] = a[i][j] == ? : left[i][j - ] + ;
right[i][N - - j] = a[i][N - - j] == ? : right[i][N - j] + ;
}
}
for (int j = ; j < N; j++)
{
up[][j] = (a[][j] == ? : );
down[N - ][j] = (a[N - ][j] == ? : );
for (int i = ; i < N; i++)
{
up[i][j] = a[i][j] == ? : up[i - ][j] + ;
down[N - - i][j] = a[N - - i][j] == ? : down[N - i][j] + ;
}
}
int maxn = ;
for (int i = ; i < N; i++)
{
for (int j = ; j < N; j++)
{
int tmp = min(min(min(up[i][j], down[i][j]), left[i][j]), right[i][j]);
maxn = max(maxn, tmp);
}
}
return maxn;
}
};
最新文章
- zookeeper工作原理、安装配置、工具命令简介
- Spring中Bean的作用域
- 使用OData技术遇到的问题及解决办法
- javascript之纯数字验证
- MyEclipse8.5快速搭建SSH框架
- 【Java基础之Object类(一)】Java中Object类中的所有方法(toString、equals、hashCode、clone、finalize、wait和notify等)详解(转载)
- [Flex] PopUpButton系列 —— 控制弹出菜单的透明度、可用、可选择状态
- javascript之处理Ajax错误
- JavaScript,通过分析Array.prototype.push重新认识Array
- CSS3属性之一:border-radius
- C++ enum 作用域问题和解决方案
- 基于visual Studio2013解决C语言竞赛题之0707月份输出
- GooglePlay - 文件上传限制的扩展
- HDU 6468 zyb的面试
- Hillstone设备管理-设备软件Stone-OS升级
- MyEclipse中jsp编码设置
- linux 的常用命令---------第八阶段
- jquery animate()背景色渐变的处理
- SpringBoot引入freemaker前端模板
- hdu 2918(IDA*)
热门文章
- android.view.View
- mysql15--垂直分表水平分表
- mysql11---主键普通全文索引
- mongo13----application set与分片结合
- java操作json
- YTU 1098: The 3n + 1 problem
- EF1:MVC/EF(Entity Framewok) /First Migrations
- 1.import和include区别 2.NSLog 和printf区别 3.创建对象做的事情 4. 类和对象方法比较 5 匿名对象优缺点 6. 封装 7.作用域范围 8.id和instancetype 9.自定义构造方法规范 10.nil和Nil及NULL、NSNull区别
- plink 与 ssh 远程登录问题
- Asp.net MVC 中Code First 迁移使用