[数据结构与算法]leetcode刷题 (5.6) 数组

1. 螺旋矩阵 II

59

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

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

思路：
不要去想着数学计算出第一行、第二行…的规律。直接每圈分成四块（上行，右行，下行，左行）按顺序分别赋值，然后只需知道要转几圈，每圈的长度，中心点要不要单独处理即可（这才是需要数学找规律的）。

笔记：
C++：
offset的处理很妙，初始1因为数组起始0，第二圈圈+2是因为每圈加了左右两列。
用count++赋值也很妙，简洁。
注意不要忘记第二圈起始位置要加1。

Python:
二维数组初始化模板

res = [[0] * n for _ in range(n)]

注：由于python的for循环中没有保留之前的i,j，所以不能像C++那样直接拿上一次for完的i或者j来用，可直接用range()的左右区间，反正抓住中心实现左闭右开即可。

C++也可以像python那样用offset做循环判断条件，是一样的。

C++：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));  //定义输出的二维数组
        int startx = 0, starty = 0;  //x, y轴坐标
        int loop = n / 2;   //转几圈
        int mid = n / 2;    //矩阵中心坐标
        int count = 1;      //赋值用
        int offset = 1;     //偏移量：每圈长度控制
        int i,j;

        while(loop--){
            i = startx;
            j = starty;

            //上行：从左到右转(左闭右开)
            for(j = starty; j < starty + n - offset; j++){
                res[i][j] = count++;
            }

            //右行：从上到下转(左闭右开)
            for(i = startx; i < startx + 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 += 2;
        }
        //若n为奇数，则最中间位置单独赋值
        if(n % 2){
            res[mid][mid] = count;
        }
        return res;
    }
};

Python：

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0] * n for _ in range(n)]
        startx, starty = 0, 0
        loop, mid = n // 2, n // 2
        count = 1

        for offset in range(1, loop + 1):
            for i in range(starty, n - offset):
                res[startx][i] = count
                count += 1
            for i in range(startx, n - offset):
                res[i][n-offset] = count 
                count += 1
            for i in range(n - offset, starty, -1):
                res[n-offset][i] = count
                count += 1
            for i in range(n - offset, startx, -1):
                res[i][starty] = count
                count += 1
            startx += 1
            starty += 1

        if n % 2 != 0:
            res[mid][mid] = count
        return res

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖