Java实现 LeetCode 764 最大加号标志（暴力递推）

764. 最大加号标志

在一个大小在 (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。

k 阶轴对称加号标志示例:

阶 1:

000

010

000

阶 2:

00000

00100

01110

00100

00000

阶 3:

0000000

0001000

0001000

0111110

0001000

0001000

0000000

示例 1：

输入: N = 5, mines = [[4, 2]]

输出: 2

解释:

11111

11111

11111

11111

11011

在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

示例 2：

输入: N = 2, mines = []

输出: 1

解释:

11

11

没有 2 阶加号标志，有 1 阶加号标志。

示例 3：

输入: N = 1, mines = [[0, 0]]

输出: 0

解释:

没有加号标志，返回 0 。

提示：

整数N 的范围： [1, 500].

mines 的最大长度为 5000.

mines[i] 是长度为2的由2个 [0, N-1] 中的数组成.

(另外,使用 C, C++, 或者 C# 编程将以稍小的时间限制进行判断.)

class Solution { 

    public int orderOfLargestPlusSign(int N, int[][] mines) {

        if (N==0)return 0;

        int max_k=0;

        //填充一个2D网格matrix出来

        int matrix[][] = new int[N][N];

        for (int i=0;i<N;i++)

            Arrays.fill(matrix[i],1);

        int m = mines.length;

        for (int i=0;i<m;i++)

            matrix[mines[i][0]][mines[i][1]]=0;

        int dp[][] = new int[N][N];

        int count = 0;

        //初始化

        //求左、右

        for (int i=0;i<N;i++){

            //求左臂并将值放入dp left->right

            count = 0;

            for (int j=0;j<N;j++){

                count = matrix[i][j]==1?count+1:0;

                dp[i][j]= count;

            }

            //求右臂 并将当前dp与右臂之间的最小值放入dp right->left

            count = 0;

            for (int j=N-1;j>=0;j--){

                count = matrix[i][j]==1?count+1:0;

                dp[i][j]=Math.min(dp[i][j],count);

            }

        }

        //求上、下

        for (int j=0;j<N;j++){

            //求上臂 并将当前dp与上臂间的最小值放入dp up->down

            count = 0;

            for (int i=0;i<N;i++){

                count = matrix[i][j]==1?count+1:0;

                dp[i][j]=Math.min(dp[i][j],count);

            }

            //求下臂 并将当前dp与下臂间的最小值放入dp down->up

            //此时的整个dp数组中的最大值就是所求的k

            count = 0;

            for (int i=N-1;i>=0;i--){

                count = matrix[i][j]==1?count+1:0;

                dp[i][j]=Math.min(dp[i][j],count);

                max_k=Math.max(max_k,dp[i][j]);

            }

        }

        return max_k;

    }

}

巴特西

Java实现 LeetCode 764 最大加号标志（暴力递推）

764. 最大加号标志

最新文章

热门文章