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