本文最后更新于：2022年11月11日 下午
题目描述
思路及实现
好的我们来写今天的每日一题，这什么啊？哦，找上下左右是不是1啊，简单，暴力遍历，其他我也不会（开摆！）
暴力遍历！
在写这题之前，有个小提醒，题目所说的加号标志，最小其实是1而不是2，就算只有一个格子是1，这个单独的格子也算加号。
首先通过题目给出的n构造一个n * n的矩阵，并将每个格子的初值赋为1，然后遍历题目给的mines数组，把矩阵中对应坐标的值改为0。
接下来就开始遍历矩阵了。对于每一个格子，从0阶开始向外扩大，每次扩大，都要判断两个条件：
- 是否越界？
- 是否存在格子中的值为0？
如果通过了上边两个条件测试，说明找到一个符合题目所说的“轴对称”加号标志，重复此过程，直到不满足条件。
不满足条件说明这个格子的最大“轴对称”加号标志已经找到，取返回结果ans和当前格子结果cnt二者中的最大值，然后就可以看下一个格子了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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
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:
break
else:
cnt += 1
ans = cnt if cnt > ans else ans
return ans
|
笑死，python直接超时了，这怎么办，换个java试试呗。
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
| 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阶“轴对称”加号标志。
根据这个规则，构造出动态规划数组，即：
因为有四个方向，所以需要四个数组，分别代表对应坐标上下左右能到达的最大距离。
然后根据所写式子编写程序即可。
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
| 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):
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:
left[i][j] = left[i][j - 1] + 1
if matrix[i][n - 1 - j] == 1:
right[i][n - 1 - j] = right[i][n - j] + 1
if matrix[j][i] == 1:
up[j][i] = up[j - 1][i] + 1
if matrix[n - 1 - j][i] == 1:
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反过来判断，省得麻烦）
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
| 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;
|
希望本文章能够帮到您~