友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
59. Spiral Matrix II
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路分析
利用 54. Spiral Matrix 的思路，从回溯思想得到启发，使用递归来逐层推进。每次方法调用只负责指定层的遍历，向里推进层次的工作，交给递归来完成。这样避免了复杂的判断。
-
一刷
-
二刷
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
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Spiral Matrix II.
*
* Memory Usage: 34.3 MB, less than 8.33% of Java online submissions for Spiral Matrix II.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2019-10-26 00:54
*/
public int[][] generateMatrix(int n) {
int x1 = 0, x2 = n - 1;
int y1 = 0, y2 = n - 1;
int i = 1;
int[][] matrix = new int[n][n];
while (x1 <= x2 && y1 <= y2) {
for (int x = x1; x <= x2; x++) {
matrix[y1][x] = i++;
}
for (int y = y1 + 1; y <= y2; y++) {
matrix[y][x2] = i++;
}
if (x1 < x2 && y1 < y2) {
for (int x = x2 - 1; x > x1; x--) {
matrix[y2][x] = i++;
}
for (int y = y2; y > y1; y--) {
matrix[y][x1] = i++;
}
}
x1++;
x2--;
y1++;
y2--;
}
return matrix;
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-16 16:02:29
*/
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
backtrack(matrix, 1, 0, 0, n, n);
return matrix;
}
private void backtrack(int[][] matrix, int start,
int row, int column,
int rLen, int cLen) {
int n = matrix.length;
if (n * n < start) {
return;
}
for (int i = column; i < column + cLen; i++) {
matrix[row][i] = start++;
}
for (int i = row + 1; i < row + rLen; i++) {
matrix[i][column + cLen - 1] = start++;
}
// 不想增加复杂判断了，数量足够就直接返回
// 如果不返回，在最后只剩下一层且有多个元素时，中间元素会被重复添加
if (n * n < start) {
return;
}
for (int i = column + cLen - 2; i >= column; i--) {
matrix[row + rLen - 1][i] = start++;
}
for (int i = row + rLen - 2; i > row; i--) {
matrix[i][column] = start++;
}
backtrack(matrix, start, row + 1, column + 1, rLen - 2, cLen - 2);
}