LeetCode 0059 - Spiral Matrix II
# Hints
- 模拟
# 前置题目
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a positive integer , generate a square matrix filled with elements from to in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
# 题意
给定一个正整数 ,要求按题意所述的螺旋形顺序生成一个 的矩阵。
# 题解
事实上本题比 LeetCode 0054 更简单。我们可以直接用 来表示 未被访问,直接实现 的额外空间复杂度,因而计算前进长度就不再有意义了。
# AC代码
class Solution {
private:
static constexpr int dx[4] = {0, 1, 0, -1};
static constexpr int dy[4] = {1, 0, -1, 0};
public:
vector<vector<int>> generateMatrix(int n) {
// 初始化
vector<vector<int>> res(n, vector<int>(n, 0));
// 遍历
int x = 0, y = 0;
int dir = 0;
for (int i = 1; i <= n * n; i ++) {
// 更新答案
res[x][y] = i;
// 递进
int nx = x + dx[dir], ny = y + dy[dir];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && res[nx][ny] == 0) {
x = nx;
y = ny;
} else {
dir = (dir + 1) % 4;
x = x + dx[dir];
y = y + dy[dir];
}
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01