友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
-
m == matrix.length -
n == matrix[i].length -
1 <= m, n <= 10 -
-100 <= matrix[i][j] <= 100
思路分析
从回溯思想得到启发，使用递归来逐层推进。每次方法调用只负责指定层的遍历，向里推进层次的工作，交给递归来完成。这样避免了复杂的判断。
-
一刷
-
二刷
-
三刷
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);
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-12 23:18:24
*/
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>(matrix.length * matrix[0].length);
bfs(matrix, 0, 0, matrix.length - 1, matrix[0].length - 1, result);
return result;
}
private void bfs(int[][] matrix,
int columnStart, int rowStart,
int columnEnd, int rowEnd,
List<Integer> result) {
if (columnStart > columnEnd || rowStart > rowEnd) {
return;
}
// 上
for (int i = rowStart; i <= rowEnd; i++) {
result.add(matrix[columnStart][i]);
}
// 右
for (int i = columnStart + 1; i <= columnEnd; i++) {
result.add(matrix[i][rowEnd]);
}
if (result.size() == matrix.length * matrix[0].length) {
return;
}
// 下
for (int i = rowEnd - 1; i >= rowStart; i--) {
result.add(matrix[columnEnd][i]);
}
// 左
for (int i = columnEnd - 1; i > columnStart; i--) {
result.add(matrix[i][rowStart]);
}
bfs(matrix, columnStart + 1, rowStart + 1,
columnEnd - 1, rowEnd - 1, result);
}