时间轴

2025-11-16

init

题目：

P54 螺旋矩阵

https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-interview-150

注意如果不通过 cnt 和 total 比较判断是否结束，当只有一行或只有一列时会出现重复加入的情况。

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
57
58
59
60
61
62
63
64
65
66
#include <vector>
using std::vector;

class Solution {
    public:
	bool spiral_edge(vector<vector<int> > &matrix, vector<int> &res, int curr_m, int curr_n, int start_i,
			 int start_j)
	{
		int i = start_i, j = start_j;
		int cnt = 0, total = curr_m * curr_n;

		if (curr_m <= 0 || curr_n <= 0) {
			return false;
		}
		// 从(start_i,start_j)开始,长度为curr_m,curr_n
		for (i = start_i, j = start_j; j < start_j + curr_n; j++) {
			res.push_back(matrix[i][j]);
			cnt++;
		}
		if (cnt == total) {
			return true;
		}
		for (i = start_i + 1, j = start_j + curr_n - 1; i < start_i + curr_m - 1; i++) {
			res.push_back(matrix[i][j]);
			cnt++;
		}
		if (cnt == total) {
			return true;
		}
		for (i = start_i + curr_m - 1, j = start_j + curr_n - 1; j >= start_j; j--) {
			res.push_back(matrix[i][j]);
			cnt++;
		}
		if (cnt == total) {
			return true;
		}
		for (i = start_i + curr_m - 2, j = start_j; i > start_i; i--) {
			res.push_back(matrix[i][j]);
			cnt++;
		}
		return true;
	}
	vector<int> spiralOrder(vector<vector<int> > &matrix)
	{
		int m = matrix.size();
		int n = matrix[0].size();
		vector<int> res;
		int curr_m = m, curr_n = n;
		int start_i = 0, start_j = 0;

		while (spiral_edge(matrix, res, curr_m, curr_n, start_i, start_j)) {
			curr_m -= 2;
			curr_n -= 2;
			start_i += 1;
			start_j += 1;
		}

		return res;
	}
};
int main()
{
	vector<vector<int> > matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
	Solution S;
	S.spiralOrder(matrix);
}

leetcode hot 100 rewrite:

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
57
#include <vector>
using std::vector;

class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int> > &matrix)
        {
                // 1 <= m, n <= 10
                int i, j, m = matrix.size(), n = matrix[0].size();
                vector<int> ret;
                int start_i = 0, start_j = 0;

                while (m > 0 && n > 0) {
                        if (start_j >= start_j + n)
                                break;
                        for (j = start_j; j < start_j + n; j++)
                                ret.push_back(matrix[start_i][j]);
                        j--;

                        if (start_i + 1 >= start_i + m)
                                break;
                        for (i = start_i + 1; i < start_i + m; i++)
                                ret.push_back(matrix[i][j]);
                        i--;

                        if (j - 1 < start_j)
                                break;
                        for (j = j - 1; j >= start_j; j--)
                                ret.push_back(matrix[i][j]);
                        j++;

                        if (i - 1 <= start_i)
                                break;
                        for (i = i - 1; i > start_i; i--)
                                ret.push_back(matrix[i][j]);
                        i++;

                        m -= 2;
                        n -= 2;
                        start_i++;
                        start_j++;
                }

                return ret;
        }
};

#include <stdio.h>
int main()
{
        // vector<vector<int> > matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        vector<vector<int> > matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
        Solution S;
        vector<int> ret = S.spiralOrder(matrix);
        for (int val : ret)
                printf("%d ", val);
}