LeetCode 59 Spiral Matrix II

Tag: 数组类题目 LeetCode Posted on 2022-02-12 20:51:54 Edited on 2022-02-12 20:54:42 Views: 143

概述

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

直接法

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

  1. 每次 for 循环结束后,r 或 c 会被多加或减一次,需要补回来;
  2. 每次 for 循环结束后,我们需要手动移动一次当前点位置;
  3. 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;
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/