Largest Plus Sign

2018-02-03 10:19:37来源:oschina作者:叶枫啦啦人点击

分享

问题:


In a 2Dgridfrom (0, 0) to (N-1, N-1), every cell contains a1, except those cells in the given listmineswhich are0. What is the largest axis-aligned plus sign of1s contained in the grid? Return the order of the plus sign. If there is none, return 0.


An "axis-aligned plus sign of1sof orderk" has some centergrid[x][y] = 1along with 4 arms of lengthk-1going up, down, left, and right, and made of1s. This is demonstrated in the diagrams below. Note that there could be0s or1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.


Examples of Axis-Aligned Plus Signs of Order k:


Order 1:
000
010
000
Order 2:
00000
00100
01110
00100
00000
Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

Example 1:


Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.One of them is marked in bold.

Example 2:


Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.

Example 3:


Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.

Note:

Nwill be an integer in the range[1, 500].
mineswill have length at most5000.
mines[i]will be length 2 and consist of integers in the range[0, N-1].
(Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)

解决:


【题意】


在从(0,0)到(N-1,N-1)的二维网格中,每个单元格包含一个1,mines指定的单元格设为0.返回最大“十字形全1区域”阶,如果没有,返回0。


“k阶十字形全1区域”中心点[x] [y] = 1以及长度为k-1的四向上,向下,向左和向右方向的点,均由1构成。


例如:


Input: N = 5, mines = [[4, 2]]


可以看出,十字形全1区域的阶为2.


Input: N = 2, mines = []


可以看出,十字形全1区域的阶为1


Input: N = 1, mines = [[0, 0]]


0 因为没有满足十字形全1区域的值,所以返回0.


① https://leetcode.com/problems/largest-plus-sign/discuss/113314


对于网格矩阵的每个位置(i,j),我们试图尽可能延长四个方向(左,右,上,下)的每一个方向,然后取四个方向中的全为1的最小长度作为在位置(i,j)处居中的最大轴对齐加号的顺序。

通常我们总共需要五个矩阵来使上述思想起作用 - 一个是网格本身的矩阵,四个方向是四个矩阵。但是,这五个矩阵可以使用两个简单的技巧组合成一个:


对于每个位置(i,j),我们只关心四个方向中的包含1的最小长度。这意味着我们可以通过只跟踪最小长度来将这四个矩阵组合成一个矩阵。
对于每个位置(i,j),当且仅当grid [i] [j] == 0时,以其为中心的十字形全1区域的阶为0.这意味着我们可以进一步将网格矩阵与上面得到的那个合并。

grid[i][j]表示第i行第j列的元素的十字形全1区域的阶。时间复杂度O(n^2),空间复杂度O(n^2)


class Solution { //143ms public int orderOfLargestPlusSign(int N, int[][] mines) { int[][] grid = new int[N][N]; for (int i = 0;i < N;i ++){//初始化为矩阵的长度,阶一定会小于该值,遍历到每一个位置时会更新它Arrays.fill(grid[i],N); } for(int[] m : mines){grid[m[0]][m[1]] = 0; } for (int i = 0;i < N;i ++){for (int j = 0,l = 0;j < N;j ++){//j表示列,由左至右遍历,检查左侧可以到达多远,如果grid[i][j]=0,l需要再次从0开始,否则l递增grid[i][j] = Math.min(grid[i][j],l = (grid[i][j] == 0 ? 0 : l + 1));}for (int k = N - 1,r = 0;k >= 0;k --){//k表示列,从右向左遍历,每次检查右侧可以到达多远,如果grid[i][j]=0,r需要再次从0开始,否则r递增grid[i][k] = Math.min(grid[i][k],r = (grid[i][k] == 0 ? 0 : r + 1));}for (int j = 0,u = 0;j < N;j ++){//j表示行,从上到下遍历,每次检查上侧可以到达多远,如果grid[i][j]=0,u需要再次从0开始,否则u递增grid[j][i] = Math.min(grid[j][i],u = (grid[j][i] == 0 ? 0 : u + 1));}for (int k = N - 1,d = 0;k >= 0;k --){grid[k][i] = Math.min(grid[k][i],d = (grid[k][i] == 0 ? 0 : d + 1));} } int res = 0; for (int i = 0;i < N;i ++){for (int j = 0;j < N;j ++){res = Math.max(res,grid[i][j]);} } return res; } }

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台