焦作做网站,四川省住房和城乡建设厅官网查询,烟台汽车租赁网站建设,深圳十大外贸公司排名文章目录1. 题目2. 解题1. 题目
在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中#xff0c;除了在 mines 中给出的单元为 0#xff0c;其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶#xff1f;返回加号标志的阶数。如果未找到加号标志#xff…
文章目录1. 题目2. 解题1. 题目
在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中除了在 mines 中给出的单元为 0其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶返回加号标志的阶数。如果未找到加号标志则返回 0。
一个 k 阶由 1 组成的“轴对称”加号标志具有中心网格 grid[x][y] 1 以及4个从中心向上、向下、向左、向右延伸长度为 k-1由 1 组成的臂。
下面给出 k 阶“轴对称”加号标志的示例。 注意只有加号标志的所有网格要求为 1别的网格可能为 0 也可能为 1。 示例 1
输入: N 5, mines [[4, 2]]
输出: 2
在上面的网格中最大加号标志的阶只能是2。一个标志已在图中标出。示例 2
输入: N 2, mines []
输出: 1
解释:
11
11
没有 2 阶加号标志有 1 阶加号标志。示例 3
输入: N 1, mines [[0, 0]]
输出: 0
解释:
0
没有加号标志返回 0 。提示
整数N 的范围 [1, 500].
mines 的最大长度为 5000.
mines[i] 是长度为2的由2个 [0, N-1] 中的数组成.
(另外,使用 C, C, 或者 C# 编程将以稍小的时间限制进行判断.)来源力扣LeetCode 链接https://leetcode-cn.com/problems/largest-plus-sign 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
动态规划记录每个位置上4个方向上的连续 1 的个数时间复杂度 O(N2)O(N^2)O(N2)
class Solution {
public:int orderOfLargestPlusSign(int N, vectorvectorint mines) {vectorvectorint g(N, vectorint(N, 1));for(auto m : mines)g[m[0]][m[1]] 0;vectorvectorint up(N, vectorint(N, 0));//该方向上的连续1的个数vectorvectorint left(N, vectorint(N, 0));vectorvectorint down(N, vectorint(N, 0));vectorvectorint right(N, vectorint(N, 0));for(int i 0; i N; i){for(int j 0; j N; j){if(g[i][j] 0)continue;left[i][j] (j 0 ? left[i][j-1] : 0) 1;up[i][j] (i 0 ? up[i-1][j] : 0) 1;}}for(int i N-1; i 0; i--){for(int j N-1; j 0; j--){if(g[i][j] 0)continue;right[i][j] (j N-1 ? right[i][j1] : 0) 1;down[i][j] (i N-1 ? down[i1][j] : 0) 1;}}int ans 0;for(int i 0; i N; i){for(int j 0; j N; j)ans max(ans, min(left[i][j], min(right[i][j],min(up[i][j], down[i][j]))));}return ans;}
};352 ms 87.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
