力扣-764. 最大加号标志

题目描述

思路及实现

好的我们来写今天的每日一题，这什么啊？哦，找上下左右是不是1啊，简单，暴力遍历，其他我也不会（开摆！）

暴力遍历！

在写这题之前，有个小提醒，题目所说的加号标志，最小其实是1而不是2，就算只有一个格子是1，这个单独的格子也算加号。

首先通过题目给出的n构造一个n * n的矩阵，并将每个格子的初值赋为1，然后遍历题目给的mines数组，把矩阵中对应坐标的值改为0。
接下来就开始遍历矩阵了。对于每一个格子，从0阶开始向外扩大，每次扩大，都要判断两个条件：

1. 是否越界？
2. 是否存在格子中的值为0？
   如果通过了上边两个条件测试，说明找到一个符合题目所说的“轴对称”加号标志，重复此过程，直到不满足条件。
   不满足条件说明这个格子的最大“轴对称”加号标志已经找到，取返回结果ans和当前格子结果cnt二者中的最大值，然后就可以看下一个格子了。

   class Solution:
       def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
           matrix = [[1 for _ in range(n)] for _ in range(n)]  # 构造矩阵
           for mine in mines:
               matrix[mine[0]][mine[1]] = 0  # 初始化0
           ans = 0
           for i in range(n):
               for j in range(n):
                   cnt = 0
                   while True:
                       if i - cnt < 0 or j - cnt < 0 or i + cnt > n - 1 or j + cnt > n - 1:  # 越界
                           break
                       elif matrix[i - cnt][j] == 0 or matrix[i][j + cnt] == 0 or matrix[i + cnt][j] == 0 or \
                               matrix[i][j - cnt] == 0:  # 存在0
                           break
                       else:  # 满足“轴对称”加号标志
                           cnt += 1
                   ans = cnt if cnt > ans else ans
           return ans

   笑死，python直接超时了，这怎么办，换个java试试呗。

   class Solution {
       public int orderOfLargestPlusSign(int n, int[][] mines) {
           int ans = 0;
           int[][] matrix = new int[n][n];
           for (int[] mine : mines) {
               matrix[mine[0]][mine[1]] = 1;
           }
           for (int i = 0; i < n; i++) {
               for (int j = 0; j < n; j++) {
                   int cnt = 0;
                   while (true) {
                       if (i - cnt < 0 || j - cnt < 0 || i + cnt > n - 1 || j + cnt > n - 1) {
                           break;
                       }
                       else if (matrix[i - cnt][j] == 1 || matrix[i][j + cnt] == 1 || matrix[i + cnt][j] == 1 || matrix[i][j - cnt] == 1) {
                           break;
                       }
                       else {
                           cnt += 1;
                       }
                   }
                   ans = Math.max(cnt, ans);
               }
           }
           return ans;
       }
   }

   java就不超时，什么力扣亲儿子，这就转型！

动态规划

对一个坐标(i, j)，如何去找它的最大“轴对称”加号标志呢？
通过题目可以知道，找出(i, j)沿上下左右方向能走的距离，然后取它们当中的最小值，就是(i ,j)所拥有的k阶“轴对称”加号标志。
根据这个规则，构造出动态规划数组，即：


因为有四个方向，所以需要四个数组，分别代表对应坐标上下左右能到达的最大距离。
然后根据所写式子编写程序即可。

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        matrix = [[1 for _ in range(n)] for _ in range(n)]  # 构造矩阵
        for mine in mines:
            matrix[mine[0]][mine[1]] = 0
        left = [[0 for _ in range(n)] for _ in range(n)]
        right = [[0 for _ in range(n)] for _ in range(n)]
        up = [[0 for _ in range(n)] for _ in range(n)]
        down = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            # 先把最外边一圈都初始化为1
            if matrix[i][0] == 1:  # 第一列
                left[i][0] = 1
            if matrix[i][n - 1] == 1:  # 最后一列
                right[i][n - 1] = 1
            if matrix[0][i] == 1:  # 第一行
                up[0][i] = 1
            if matrix[n - 1][i] == 1:  # 最后一行
                down[n - 1][i] = 1
            for j in range(1, n):  # 开始计算每个坐标的“轴对称”加号标志，顺序为左右上下
                if matrix[i][j] == 1:  # 第i行从左往右计算每个坐标的left中的值
                    left[i][j] = left[i][j - 1] + 1
                if matrix[i][n - 1 - j] == 1:  # 第i行从右往左计算每个坐标的right中的值
                    right[i][n - 1 - j] = right[i][n - j] + 1
                if matrix[j][i] == 1:  # 第i行从上往下计算每个坐标的up中的值
                    up[j][i] = up[j - 1][i] + 1
                if matrix[n - 1 - j][i] == 1:  # 第i行从下往上计算每个坐标的down中的值
                    down[n - 1 - j][i] = down[n - j][i] + 1
        return max(min(left[i][j], right[i][j], up[i][j], down[i][j])for i in range(n) for j in range(n))

再多写个Java熟悉熟悉（对了，java初始化数组中的int的数值默认就是0，所以索性直接把1和0反过来判断，省得麻烦）

int ans = 0;
int[][] matrix = new int[n][n];
for (int[] mine : mines) {
    matrix[mine[0]][mine[1]] = 1;
}
int[][] left = new int[n][n];
int[][] right = new int[n][n];
int[][] up = new int[n][n];
int[][] down = new int[n][n];
for (int i = 0; i < n; i++) {
    if(matrix[i][0] == 0)
        left[i][0] = 1;
    if(matrix[i][n - 1] == 0)
        right[i][n - 1] = 1;
    if(matrix[0][i] == 0)
        up[0][i] = 1;
    if(matrix[n - 1][i] == 0)
        down[n - 1][i] = 1;
    for (int j = 1; j < n; j++) {
        if(matrix[i][j] == 0)
            left[i][j] = left[i][j - 1] + 1;
        if(matrix[i][n - 1 - j] == 0)
            right[i][n - 1 - j] = right[i][n - j] + 1;
        if(matrix[j][i] == 0)
            up[j][i] = up[j - 1][i] + 1;
        if(matrix[n - 1 - j][i] == 0)
            down[n - 1 - j][i] = down[n - j][i] + 1;
    }
}
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        ans = Math.max(ans,Math.min(left[i][j], Math.min(right[i][j], Math.min(up[i][j], down[i][j]))));
    }
}
return ans;

---

希望本文章能够帮到您~