文档章节

矩阵中十字形的最大阶(1组成的十字的最大长度),Largest Plus Sign

叶枫啦啦
 叶枫啦啦
发布于 2018/02/01 11:17
字数 1124
阅读 32
收藏 0

问题:

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s 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:

  1. N will be an integer in the range [1, 500].
  2. mines will have length at most 5000.
  3. mines[i] will be length 2 and consist of integers in the range [0, N-1].
  4. (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 ++){//初始化为矩阵的