59. Spiral Matrix II

題目意思非常簡單, 就是要沿著外圈慢慢轉進去, 然後最後輸出這個二維陣列

所以我一開始想法也非常直覺, 我會做兩張表, 一張記錄是否被走過, 另一張就是要輸出的值, 接著我們會分四個方向, 假設走到底, 或是已經被走過了, 我們就會轉向, 因為邊長是n, 意味我們只會填 n * n 次, 所以可以知道什麼時候要停

code如下

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
        vector<vector<bool>> record(n, vector<bool>(n, false));
        int total_step = n * n;
        int step = 0;
        int i = 0;
        int j = 0;
        int way = 0; // 0: right, 1: down; 2:left, 3:up
        while(step <total_step){
            res[i][j] = step +1;
            record[i][j] = true;
            step++;
            if(way == 0){
                if(j < n -1 && !record[i][j+1]){
                    j++;
                }else{
                    way = 1;// turn down
                    i++;
                }
            }else if (way==1){
                if(i < n -1 && !record[i+1][j]){
i++;
                }else{
                    way = 2;// turn left
                    j--;
                }
            } else if (way==2){
                if(j > 0 && !record[i][j-1]){
                    j--;
                }else{
                    way = 3;// turn up
                    i--;
                }
            }else{
                if(i >0 && !record[i-1][j]){
                    i--;
                }else{
                    way = 0;// turn right
                    j++;
                }
            }
}
        return res;
    }
};

時間複雜度: O(n * n), 空間複雜度: (2 *n * n)

但這上面的code實在太容易出錯, 我上網查後看到比較精簡的版本

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        int up = 0;
        int down = n-1;
        int left =0;
        int right = n-1;
        int val = 1;
        while(true){
            for(int j = left; j<=right; j++){
                res[up][j] = val++;
            }
            if(++up > down) break;
            for(int i = up; i <=down;++i){
                res[i][right] = val++;
            }
            if(--right <left) break;
            for(int j = right; j >=left;--j){
                res[down][j] = val++;
            }
            if(--down < up) break;
            for(int i = down; i >= up;i--){
                res[i][left] = val++;
            }
            if(++left > right) break;
        }
        return res;
    }
};

分別就是從左到右, 上到下, 右到左, 下在回上

在每次走完, 先去檢查是否超界了, 超界則跳出, 檢查超界同時還可以做一個移動, 這個動作可以彌補剛剛我們還特地要用表去紀錄是否有走過

很精簡, 但相對就要下比較多巧思