Leetcode 54- 螺旋输出数组
1. 题目描述
很简单的需求，给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18示例?1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例?2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
2. 思路
就是一层一层（依次按照上、右、下、左的顺序）地将最外层的元素按照需要的顺序输出，再递归求解子问题。思路和官方提供的题解基本一样，如下图：
3. 代码
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53class Solution {
private List<Integer> res = new ArrayList<>();
private int[][] m;
public List<Integer> spiralOrder(int[][] matrix) {
m = matrix;
int rows = matrix.length;
if (rows == 0) return res;
int cols = matrix[0].length;
spiralOrderPrint(0, rows - 1, 0, cols - 1);
return res;
}
public void spiralOrderPrint(int row_b, int row_e, int col_b, int col_e) {
// 当中心没有元素，直接返回
if (row_e < row_b || col_e < col_b)
return;
// 当只剩下中心一行或一列元素
if (row_e == row_b || col_b == col_e) {
if (row_e == row_b) // 是剩下中心一行的情况
{
for (int j = col_b; j <= col_e; j++) {
res.add(m[row_b][j]);
}
// 求解子问题
spiralOrderPrint(row_b + 1, row_e - 1, col_b + 1, col_e - 1);
return;
} else { // 是剩下中心一列的情况
for (int i = row_b; i <= row_e; i++) {
res.add(m[i][col_b]);
}
// 求解子问题
spiralOrderPrint(row_b + 1, row_e - 1, col_b + 1, col_e - 1);
return;
}
}
// 行列数大于等于2
// 依次处理上右下左四个位置的元素
for (int j = col_b; j <= col_e - 1; j++) res.add(m[row_b][j]);
for (int i = row_b; i <= row_e - 1; i++) res.add(m[i][col_e]);
for (int j = col_e; j >= col_b + 1; j--) res.add(m[row_e][j]);
for (int i = row_e; i >= row_b + 1; i--) res.add(m[i][col_b]);
// 求解子问题
spiralOrderPrint(row_b + 1, row_e - 1, col_b + 1, col_e - 1);
return;
}
}
4.类似题
- LeetCode 59- 螺旋矩阵②
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。1
2
3
4
5
6
7输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
思路和之前差不多，递归求解子问题，从最外圈填到最内圈。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
44
45
46
47
48
49
50
51
52
53
54
55
56
57import java.util.Arrays;
/**
* @ClassName SpiralOrder_two_59
* @Deacription // TODO
* @Author LiuZhian
* @Date 2019-11-03 15:40
* @Version 1.0
**/
public class SpiralOrder_two_59 {
private int[][] m;
public int[][] generateMatrix(int n) {
m = new int[n][n];
if (n == 0) return m;
int begin_num = 1;
// 如果n为偶数，一共要填 n/2次
for (int i = 0; i < n / 2; i++) {
begin_num = fill(begin_num, 0 + i, n - 1 - i, 0 + i, n - 1 - i);
}
// 如果n为奇数，最中间那个数还没填,补填
if (n % 2 == 1)
m[n / 2][n / 2] = begin_num;
return m;
}
// 开始填充数组，从begin_num开始填充,返回下一层开始填充的数字
private int fill(int begin_num, int row_b, int row_e, int col_b, int col_e) {
// top
for (int j = col_b; j <= col_e - 1; j++) m[row_b][j] = begin_num++;
// right
for (int i = row_b; i <= row_e - 1; i++) m[i][col_e] = begin_num++;
// bottom
for (int j = col_e; j >= col_b + 1; j--) m[row_e][j] = begin_num++;
// left
for (int i = row_e; i >= row_b + 1; i--) m[i][col_b] = begin_num++;
return begin_num;
}
public static void main(String[] args) {
SpiralOrder_two_59 s = new SpiralOrder_two_59();
int[][] res = s.generateMatrix(5);
for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[0].length; j++) {
System.out.print(res[i][j]);
}
System.out.println();
}
}
}
