Spiral-Matrix

发表于 | 更新于：

题目地址

LeetCode#54 Spiral Matrix

题目描述

  给出一个 m x n 的矩阵（m 行, n 列），请按照顺时针螺旋顺序返回元素。

  例如，给出以下矩阵：

1
2
3
4
5
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

  应该返回 [1,2,3,6,9,8,7,4,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
class Solution {
    void spiral(const vector<vector<int>> &matrix, vector<int> &result, int idx) {
        int left = idx;
        int top = idx;
        int right = matrix[top].size() - 1 - idx;
        int bottom = matrix.size() - 1 - idx;

        if (right < left || bottom < top) return;

        if (right == left && bottom == top) {
            result.push_back(matrix[bottom][right]);
            return;
        }

        for (int i = left; i <= right; ++i) {    // A -> B
            result.push_back(matrix[top][i]);
        }
        for (int i = top + 1; i <= bottom; ++i) {    // B -> C
            result.push_back(matrix[i][right]);
        }
        for (int i = right - 1; i >= left; --i) {    // C -> D
            result.push_back(matrix[bottom][i]);
        }
        for (int i = bottom - 1; i > top; --i) {    // D -> A
            result.push_back(matrix[i][left]);
        }

        spiral(matrix, result, idx + 1);
    }

public:
    vector<int> spiralOrder(vector<vector<int>> &matrix) {
        vector<int> result(0);
        if (matrix.empty())
            return result;
        spiral(matrix, result, 0);
        return result;
    }
};
0%