Leetcode59

螺旋矩阵

Leetcode59

题目描述

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

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

示例 2：

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

思路

螺旋矩阵，仔细观察其规律，就可以发现，变化规律为画4条边：

1. 行不变，列从左到右，
2. 列不变，行从上到下
3. 行不变，列从左到右
4. 列不变，行从下到上

尤其注意边界条件，不能填充已填充过的位置，每一圈都要画4条边，每画一条边都要坚持一致的左闭右开，或者左开又闭的原则，这样这一圈才能按照统一的规则画下来。

整理一下思路：

• 先确定循环次数，这里的循环，指绕几个大圈，一个圈画4条边
• 求得矩阵中间位置，可能会在n为奇数使用到
• 记录每一次循环开始位置，即绕完一圈后的开始位置
• 每次绕完一圈，下一次绕圈，每条边长变短

代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0)); // 使用vector定义一个二维数组
        int starx = 0, stary=0; //开始位置
        int loop = n/2;  //循环次数
        int mid = n/2; //中间位置
        int count = 1; // n
        int offset = 1; //for步长
        int i, j;
        while(loop--){
            i = starx;
            j = stary;

            for(j=stary;j<starx+n-offset;j++){  //从左到右
                res[starx][j] = count;
                count++;
            }
            for(i=starx;i<stary+n-offset;i++){ //从下到上
                res[i][j] = count++;
    
            }
            for(;j>stary;j--){  //从右到左
                res[i][j] = count++;
            }
            for(;i>starx;i--){ //从下到上
                res[i][j] = count++;
            }
            starx++; //改变起始位置
            stary++;
            offset+=2; //步长减小2，因为左边右边、上边下边各1
        }
        if(n%2 != 0) res[mid][mid] = n*n; //奇数时，填充中间位置
        return res;
    }
};

参考

代码随想录