当前位置：首页 > article >正文

代码随想录刷题day05|（数组篇）59.螺旋矩阵 II

article 2025/1/13 4:49:02

一、数组理论基础

二、循环不变量原则

三、相关算法题目

四、总结

没想到的点：

有疑问的地方：

五、待解决问题

一、数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

代码随想录 (programmercarl.com)

特点：

1.下标从0开始，内存中地址空间是连续的

2.查询快，增删慢

3.二维数组中，行为第一索引，列为第二索引

4.一旦创建以后，长度不能发生变化

5.元素无法删除，只能被覆盖

二、循环不变量原则

该题没有涉及到任何算法，主要是模拟矩阵转圈遍历的过程，关键点在于边界的处理，考虑使用循环不变量原则。

如果处理每一条边的时候，对每个结点的处理规则不一样，在循环时就很容易绕晕，此题在处理每一条边时，坚持循环不变量原则，即坚持一个规则来处理每一条边：左闭右开（前面的点是闭，后面的点是开），只处理前一个结点，后一个结点留给下一条边。

图源：代码随想录

三、相关算法题目

59.螺旋矩阵 II

59. 螺旋矩阵 II - 力扣（LeetCode）

两种方法（遍历时边界处理不一致）

法1（边界处理：左闭右开）

class Solution {
    public int[][] generateMatrix(int n) {
        //循环不变量原则 以 n=4为例 左闭右开
        int startX = 0; //每一圈的起始点
        int startY = 0;
        int offset = 1;
        int count = 1; //矩阵中需要填充的元素值
        int i, j; // i代表行 j代表列
        int loop = 1;//记录当前圈数
        int[][] nums = new int[n][n]; //定义二维数组并动态初始化
        while(loop <= n / 2){//循环的圈数 
            for(j = startY;j < n - offset;j++){//这里不是j < n -1 外层是 但是第二圈循环就不是了 所以要用一个变量offset
                nums[startX][j] = count++;//startX 能换成i吗？不能
            }//此时j = n - offset
            for(i = startX;i < n - offset;i++){ //右边那条边
                nums[i][j] = count++;
            } //此时 i = n - offset
            for(;j > startY;j--){//下面那条边
                nums[i][j] = count++;
            }//此时 j = startY = 0
            for(;i > startX;i--){ //左边那条边
                nums[i][startY] = count++;
                //nums[i][j] = count++;  可以写j吗？？？不可以
            }//此时 i = startX = 0
            startY++;
            startX++;
            offset++;
            loop++; //不要忘记
        }
        if(n % 2 == 1){ //如果n是奇数
           nums[startX][startY] = count; //? 两者有什么区别？
           //nums[i][j] = count; 运行会报错
           // i 和 j 最后退出循环时 等于start 但是startX、Y 最后又加1了 也就是又开始一圈 所以后者才是正确的
        }
        return nums;
    }
}

法2（题解中参考别人的）

class Solution {
    public int[][] generateMatrix(int n) {
        //四个指针 转圈遍历
        int t, b ,l, r;
        t = 0;
        b = n - 1;
        l = 0;
        r = n - 1;
        int[][] array = new int[n][n];
        int num = 1;
        int tar = n*n;
        while(num <= tar){
            for(int i = l; i <= r;i++){
                array[t][i] = num++;
            }
            t++;
            for(int i = t;i <= b;i++){
                array[i][r] = num++;
            }
            r--;
            for(int i = r;i >= l;i--){
                array[b][i] = num++;
            }
            b--;
            for(int i = b;i >= t;i--){
                array[i][l] = num++;
            }
            l++;
        }
        return array;
    }
}

其他相关题目：

54. 螺旋矩阵 - 力扣（LeetCode）（待做ing。。。）