LeetCode 59 Spiral Matrix II

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-02-12 20:51:54
    编辑于：2022-02-12 20:54:42
    浏览量：856

概述

https://leetcode.com/problems/spiral-matrix-ii/

直接法

真的是看着简单，实现时一堆要注意的地方：

每次 for 循环结束后，r 或 c 会被多加或减一次，需要补回来；
每次 for 循环结束后，我们需要手动移动一次当前点位置；
rowTopBound 需要初始化为 1；

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> m(n, vector<int>(n, 0));
        int d = 0;
        int s = 1;
        int r = 0, c = 0;
        int colLeftBound = 0, colRightBound = n - 1;
        int rowTopBound = 1, rowBottomBound = n - 1;
        int oldS = -1;
        while (s != oldS) {
            oldS = s;
            d = d % 4;
            if (d == 0) {  // go right
                for (; c <= colRightBound; c ++) {
                    cout << "d " << d << " r " << r << " c " << c << " s " << s << endl;
                    m[r][c] = s++;
                }
                r ++;
                c --;
                colRightBound --;
            } else if (d == 1) {  // go down
                for (; r <= rowBottomBound; r ++) {
                    m[r][c] = s++;
                }
                r --;
                c --;
                rowBottomBound --;
            } else if (d == 2) {  // go left
                for (; c >= colLeftBound; c --) {
                    m[r][c] = s++;
                }
                r --;
                c ++;
                colLeftBound ++;
            } else {  // go top
                for (; r >= rowTopBound; r --) {
                    m[r][c] = s++;
                }
                r ++;
                c ++;
                rowTopBound ++;
            }
            d ++;
        }
        return m;
    }
};

额，没必要通过 s 和 oldS 来判断是否该终止，我们明明知道要搞 n * n 次的好吧。

以下为 labuladong 的实现，漂亮多了：

int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n];
    int upper_bound = 0, lower_bound = n - 1;
    int left_bound = 0, right_bound = n - 1;
    // 需要填入矩阵的数字
    int num = 1;
    
    while (num <= n * n) {
        if (upper_bound <= lower_bound) {
            // 在顶部从左向右遍历
            for (int j = left_bound; j <= right_bound; j++) {
                matrix[upper_bound][j] = num++;
            }
            // 上边界下移
            upper_bound++;
        }
        
        if (left_bound <= right_bound) {
            // 在右侧从上向下遍历
            for (int i = upper_bound; i <= lower_bound; i++) {
                matrix[i][right_bound] = num++;
            }
            // 右边界左移
            right_bound--;
        }
        
        if (upper_bound <= lower_bound) {
            // 在底部从右向左遍历
            for (int j = right_bound; j >= left_bound; j--) {
                matrix[lower_bound][j] = num++;
            }
            // 下边界上移
            lower_bound--;
        }
        
        if (left_bound <= right_bound) {
            // 在左侧从下向上遍历
            for (int i = lower_bound; i >= upper_bound; i--) {
                matrix[i][left_bound] = num++;
            }
            // 左边界右移
            left_bound++;
        }
    }
    return matrix;
}

Links: leetcode-59-spiral-matrix-ii