59. Spiral Matrix II
1.問題
給予一個正整數n, 產生一個正方形矩形, 以螺旋方式存放1 ~ n^2

2.想法
提問
parameter
整數n
回傳一個2D list
test input
說明想法
Create一個2D list, 並且填入對應的數字
為了怕overflow, 填入數字時可以計算cnt
用上, 下, 左, 右四個指標來移動, 當left <= right -1且up <= down - 1時繼續執行以下動作
上排: 從left到right, 依序將數值放到res, 並遞增up
右排: 從up到down, 依序將數值放到res, 並遞減right
下排: 從right到left, 依序將數值放到res, 並遞減down
左排: 從down到up, 依序將數值放到res, 並遞增left
測試計算複雜度
3.程式碼
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
if (n == 0) {
return res;
}
int top = 0, bottom = n, left = 0, right = n, cnt = 0, total = n * n;
while (top <= bottom - 1 && left <= right - 1) {
for (int i = left; i < right; i++) {
if (cnt < total) {
res[top][i] = cnt + 1;
cnt++;
}
}
++top;
for (int i = top; i < bottom; i++) {
if (cnt < total) {
res[i][right - 1] = cnt + 1;
cnt++;
}
}
--right;
for (int i = right - 1; i >= left; i--) {
if (cnt < total) {
res[bottom - 1][i] = cnt + 1;
cnt++;
}
}
--bottom;
for (int i = bottom - 1; i >= top; i--) {
if (cnt < total) {
res[i][left] = cnt + 1;
cnt++;
}
}
++left;
}
return res;
}
};
Last updated