LeetCode-764. 最大加号标志【动态规划，二维数组】

题目描述：

在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0

返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。

示例 1：

输入: n = 5, mines = [[4, 2]]
输出: 2
解释: 在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

示例 2：

输入: n = 1, mines = [[0, 0]]
输出: 0
解释: 没有加号标志，返回 0 。

提示：

1 <= n <= 500
1 <= mines.length <= 5000
0 <= xi, yi < n
每一对 (xi, yi) 都 不重复
https://leetcode.cn/problems/largest-plus-sign/

解题思路一：动态规划。用一个n*n的数组记录每个点上下左右方向上为1的最小值。最后ans返回数组中最大的加号。

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<int>> dp(n, vector<int>(n, n));//初始化一个所有值全为n的二维网格,因为遍历是取min
        unordered_set<int> banned;//记录为0的点
        for (auto &&vec : mines) banned.emplace(vec[0] * n + vec[1]);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int count = 0;
            /* left */
            for (int j = 0; j < n; j++) {
                if (banned.count(i * n + j))count = 0;
                else count++;
                dp[i][j] = min(dp[i][j], count);
            }
            count = 0;
            /* right */ 
            for (int j = n - 1; j >= 0; j--) {
                if (banned.count(i * n + j)) count = 0;
                else count++;
                dp[i][j] = min(dp[i][j], count);
            }
        }
        for (int i = 0; i < n; i++) {
            int count = 0;
            /* up */
            for (int j = 0; j < n; j++) {
                if (banned.count(j * n + i)) count = 0;
                else count++;
                dp[j][i] = min(dp[j][i], count);
            }
            count = 0;
            /* down */
            for (int j = n - 1; j >= 0; j--) {
                if (banned.count(j * n + i)) count = 0;
                else count++;
                dp[j][i] = min(dp[j][i], count);
                ans = max(ans, dp[j][i]);//ans取最大的加号
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

时间复杂度：O(n²)
空间复杂度：O(n²)

解题思路二：优化1。

很简单，memset是一个字节一个字节设置的，取要赋的值的后8位二进制进行赋值。

1的二进制是（00000000 00000000 00000000 00000001），取后8位（00000001），int型占4个字节，当初始化为1时，它把一个int的每个字节都设置为1，也就是0x01010101,二进制是00000001 00000001 00000001 00000001，十进制就是16843009。

之所以输入0,-1时正确，纯属巧合。

0，二进制是（00000000 00000000 00000000 00000000），取后8位（00000000），初始化后00000000 00000000 00000000 00000000结果是0
-1，负数在计算机中以补码存储，二进制是（11111111 11111111 11111111 11111111），取后8位（11111111），则是11111111 11111111 11111111 11111111结果也是-1

总结：memset()只有在初始化-1,0时才会正确。想要初始化为其他值，就乖乖的DIY吧！
memset 函数适合初始化 0 或 -1，如果是其他值，还是老老实实用 for 循环吧。

class Solution {
public:
    int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
        if (mines.size() == N * N) return 0;
        if (mines.size() > N * N - 5) return 1;
        int grid[N][N];
        int arm[N][N][4];
        // set all the value of grid to be "1", this is a trick to use "-1"
        memset(grid, -1, sizeof(grid));
        // set all the value of arm to be "0"
        memset(arm, 0, sizeof(arm));
        for (auto& v : mines) {
            grid[v[0]][v[1]] = 0;
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 0) continue;
                arm[i][j][0] = 1 + ((i > 0) ? arm[i - 1][j][0] : 0);
                arm[i][j][1] = 1 + ((j > 0) ? arm[i][j - 1][1] : 0);
            }
        }
        for (int i = N - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                if (grid[i][j] == 0) continue;
                arm[i][j][2] = 1 + ((i < N - 1) ? arm[i + 1][j][2] : 0);
                arm[i][j][3] = 1 + ((j < N - 1) ? arm[i][j + 1][3] : 0);
            }
        }
        int res = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 0) continue;
                int s = min(min(arm[i][j][0], arm[i][j][1]), min(arm[i][j][2], arm[i][j][3]));
                res = max(res, s);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间复杂度：O(n²)
空间复杂度：O(n²)

解题思路三：0

1