59. 螺旋矩阵()

59. 螺旋矩阵 II

给你一个正整数 ，生成一个包含 到 所有元素，且元素按顺时针顺序螺旋排列的 正方形矩阵 。

n
1
n2
n x n
matrix

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

题解：

坚持循环不变量原则，模拟顺时针画矩阵的过程

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

本题的边界条件非常多，需要找到固定的规则来进行遍历，否则，根本就遍历不明白，我们按照左闭右开的原则来进行遍历

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        // 定义每循环一个圈的起始位置
        int startx = 0, starty = 0;
        // 每个圈循环几次，例如 n 为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int loop = n / 2;
        // 矩阵中间的位置，例如：n 为 3， 中间的位置就是（1，1），n为5，中间的位置(2, 2)
        int mid = n / 2;
        // 用来给矩阵中每一个空格复制
        int count = 1;
        // 需要控制每条边遍历的长度，每次循环右边界收缩一位
        int offset = 1;
        int i, j;
        while (loop--) {
            i = startx;
            j = starty;

            //模拟填充上行 从左到右 （左闭右开）
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            //模拟填充右列 从上到下 （左闭右开）
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行 从右到左 （左闭右开）
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列 从下到上 （左闭右开）
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始，起始位置要各自加1，
            startx++;
            starty++;

            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }

        return res;
    }
};
————————

59. 螺旋矩阵 II

给你一个正整数 ，生成一个包含 到 所有元素，且元素按顺时针顺序螺旋排列的 正方形矩阵 。

n
1
n2
n x n
matrix

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

题解：

坚持循环不变量原则，模拟顺时针画矩阵的过程

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

本题的边界条件非常多，需要找到固定的规则来进行遍历，否则，根本就遍历不明白，我们按照左闭右开的原则来进行遍历

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        // 定义每循环一个圈的起始位置
        int startx = 0, starty = 0;
        // 每个圈循环几次，例如 n 为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int loop = n / 2;
        // 矩阵中间的位置，例如：n 为 3， 中间的位置就是（1，1），n为5，中间的位置(2, 2)
        int mid = n / 2;
        // 用来给矩阵中每一个空格复制
        int count = 1;
        // 需要控制每条边遍历的长度，每次循环右边界收缩一位
        int offset = 1;
        int i, j;
        while (loop--) {
            i = startx;
            j = starty;

            //模拟填充上行 从左到右 （左闭右开）
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            //模拟填充右列 从上到下 （左闭右开）
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行 从右到左 （左闭右开）
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列 从下到上 （左闭右开）
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始，起始位置要各自加1，
            startx++;
            starty++;

            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }

        return res;
    }
};