LeetCode 0054 - Spiral Matrix
# Hints
- 模拟
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a matrix of elements ( rows, 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]
# 题意
给定一个 的矩阵,要求按题意所述的螺旋形顺序遍历矩阵,并返回遍历的结果序列。
# 题解
如果可以接受 的额外空间复杂度,那么我们直接模拟即可。我们用 表示 是否已访问,用标号取模的方法来模拟遍历方向的变化,然后用递归或非递归的方式遍历均可。
如果希望用 的额外空间复杂度解决问题,则稍微麻烦一些。观察不难发现,在旋转遍历的过程中,沿着每一条直线前进的长度是有简单规律的。我们在模拟遍历方向的同时维护当前前进长度即可。
细节问题:
- 注意特判空矩阵。
# AC代码(有额外空间消耗)
class Solution {
private:
static constexpr int dx[4] = {0, 1, 0, -1};
static constexpr int dy[4] = {1, 0, -1, 0};
public:
vector<int> spiralOrder(vector<vector<int>> & matrix) {
// 特判
if (matrix.empty() || matrix.front().empty()) {
return vector<int>();
}
// 初始化
int m = matrix.size(), n = matrix.front().size();
bool visited[m][n];
memset(visited, false, sizeof(visited));
// 遍历
vector<int> res;
int x = 0, y = 0;
int dir = 0;
for (int i = 0; i < m * n; i ++) {
// 更新答案
res.push_back(matrix[x][y]);
visited[x][y] = true;
// 递进
int nx = x + dx[dir], ny = y + dy[dir];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
x = nx;
y = ny;
} else {
dir = (dir + 1) % 4;
x = x + dx[dir];
y = y + dy[dir];
}
}
// 返回
return res;
}
};
# AC代码(无额外空间消耗)
class Solution {
private:
static constexpr int dx[4] = {0, 1, 0, -1};
static constexpr int dy[4] = {1, 0, -1, 0};
public:
vector<int> spiralOrder(vector<vector<int>> & matrix) {
// 特判
if (matrix.empty() || matrix.front().empty()) {
return vector<int>();
}
// 初始化
int m = matrix.size(), n = matrix.front().size();
// 遍历
vector<int> res;
int len[] = {n, m - 1};
int x = 0, y = -1;
int dir = 0;
while (len[dir % 2] > 0) {
// 处理当前方向
for (int i = 0; i < len[dir % 2]; i ++) {
x += dx[dir];
y += dy[dir];
res.push_back(matrix[x][y]);
}
// 递进
len[dir % 2] --;
dir = (dir + 1) % 4;
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01