LeetCode 59. Spiral Matrix II [Medium] [C++] 解題筆記

這題和 LeetCode 54. Spiral Matrix 基本上是一樣的問題，差別只在於這題沒有事先填好array的內容。詳細作法可以參考之前那篇。

Time Complexity: O(n)

完整程式碼:

class Solution {

public:

    vector<vector<int>> generateMatrix(int n) {

        vector<vector<int>> res(n, vector<int>(n, -1));

        int dir_row[4] = {0, 1, 0, -1};

        int dir_col[4] = {1, 0, -1, 0};

        int cur_row = 0;

        int cur_col = 0;

        int next_row = 0;

        int next_col = 0;

        int dir = 0;

        for (int i = 1; i <= n*n; i++) {

            res[cur_row][cur_col] = i;

            next_row = cur_row + dir_row[dir];

            next_col = cur_col + dir_col[dir];

            if (next_row < 0 || next_row >= n || next_col < 0 || next_col >= n || res[next_row][next_col] != -1) {

                dir = (dir + 1) % 4;

                next_row = cur_row + dir_row[dir];

                next_col = cur_col + dir_col[dir];

            }

            cur_row = next_row;

            cur_col = next_col;

        }

        return res;           

    }

};