Day04 | 数组螺旋矩阵II和I&&146.螺旋遍历二维数组&&数组总结

代码随想录 | Day04 | 数组：螺旋矩阵II和I&&146.螺旋遍历二维数组&&数组总结

主要学习内容：

螺旋遍历二维数组

59.螺旋矩阵II

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

解法一：找规律（代码随想录的方法，使用左闭右开）

思路：

选定一条边每次遍历多少，选定左开右闭（每次不遍历一条边第一个），选定左闭右开（每次不遍历一条边最后一个），两种思路都可以完成遍历。

找规律就是会发现：

1.每次转的一共的圈数是n/2

2.每条边每次转圈会有不需要遍历的块，交给下一条边来完成，这个数量把它叫做偏移量offset，初始化为1，表示转第一圈每条边都不需要遍历最后一个块（左闭右开）

3.每一圈的起始位置相比上一圈的横纵坐标都会+1

4.n为奇数的话最后一圈只有一个数且是n/2+1圈，故可以拿出来单独处理

下图就是左闭右开

20220922102236

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) 
    {
        int num=1;
        int offset=1;//偏移量，主要用作循环条件
        int startx=0,starty=0,i=0,j=0;//起始位置的x,y和运行时的x，y
        int x=n/2;//一共需要转圈的圈数
        vector<vector<int>> res(n,vector<int>(n));
        while(x--)
        {
            i = startx;//i,j赋值为起始位置
            j = starty;
            for(;j<n-offset;j++)//往左
                res[i][j]=num++;
            for(;i<n-offset;i++)//往下
                res[i][j]=num++;
            for(;j>starty;j--)//往右
                res[i][j]=num++;
            for(;i>startx;i--)//往上
                res[i][j]=num++;
            startx++;//下一圈的起始位置的x，y比上一圈+1
            starty++;
            offset++;//下一圈每条边要处理的量会减1
        }
        if(n*n%2!=0)//n为奇数的处理
            res[n/2][n/2]=n*n;
        return res;
    }
};

//细心的同学可能发现offset和startx，starty的关系，没错就是一直相差1而已
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) 
    {
        int count=1;
        int num=1;
        vector<vector<int>> res(n, vector<int>(n));
        int x=n/2;
        int i=0,j=0;
        while(x--)
        {
            for(;j<n-count;j++)
                res[i][j]=num++;
            for(;i<n-count;i++)
                res[i][j]=num++;
            for(;j>count-1;j--)
                res[i][j]=num++;
            for(;i>count-1;i--)
                res[i][j]=num++;
            i++;
            j++;
            count++;
        }
        if(n*n%2!=0)
        {
            res[n/2][n/2]=n*n;
        }
        return res;
    }
};

解法二：直观的去想（使用左开右闭）（给大家也算是提供一个新思路？）

思路：

就把它当做是一个绕圈游戏，一个人一直跑，然后会拐弯，拐弯的条件要么是前面没路了（到了数组边界），要么就是前面他已经跑过了（前面是不为0的一个正整数）

圈数还是一样的n/2，最后对奇数的情况进行处理

不同点：

1.num从2开始

2.res[0][0]初始化为1

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) 
    {
        int num=2;
        int i=0,j=0;
        int x=n/2;
        vector<vector<int>> res(n,vector<int>(n,0));
        res[0][0] = 1;
        while(x--)
        {
            while(j<n-1&&!res[i][j+1])//往右跑
            {
                res[i][j+1]=num++;
                j++;
            }
            while(i<n-1&&!res[i+1][j])//往下跑
            {
                res[i+1][j]=num++;
                i++;
            }
            while(j>0&&!res[i][j-1])//往左跑
            {
                res[i][j-1]=num++;
                j--;
            }
            while(i>0&&!res[i-1][j])//往上跑
            {
                res[i-1][j]=num++;
                i--;
            }
        }
        if(n*n%2!=0)//对奇数的处理
            res[n/2][n/2]=n*n;
        return res;
    }
};

注：当时写出来发现是左开右闭，不知道左闭右开可不可以实现，大家可以试试。

54.螺旋矩阵

54. 螺旋矩阵 - 力扣（LeetCode）

解法：上题的解法一

规律基本相同，下面只列出不同点

1.x即转的圈数变为在m/2和n/2中的最小值

2.循环变量中原来都用n现在行用m列用n各用各的

3.n和m不相等的时候呢会多出来一行或者一列（不是完整的一行或一列但是剩下的数量都大于等于1）

当行比列多（m>n）时，转完圈后多一列

当列比行多（n>m）时，转完圈后多一行

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int x = min(m / 2, n / 2);//循环圈数
        int offset = 1;//控制每条边所要处理的个数
        int startx = 0, starty = 0, i = 0, j = 0;//每一圈的起始位置和转圈时的下标
        vector<int> res;
        while(x--)
        {
            i=startx;
            j=starty;
            for (; j < n - offset; j++)//往右
                res.push_back(matrix[i][j]);
            for (; i < m - offset; i++)//往下
                res.push_back(matrix[i][j]);
            for (; j > startx; j--)//往左
                res.push_back(matrix[i][j]);
            for (; i > starty; i--)//往上
                res.push_back(matrix[i][j]);
            startx++;
            starty++;
            offset++;
        }
        if (res.size() < n * m && n > m)//对多出来的行的处理
        {
            for (int i = starty; i < n - offset+1; i++)
                res.push_back(matrix[startx][i]);
        }
        else if (res.size() < n * m && n < m)//对多出来的列的处理
        {
            for (int i = startx; i < m - offset + 1; i++)//注意是m-offset+1而不是n-offset+1，不要想当然
                res.push_back(matrix[i][starty]);
        }
        else if(n==m&&n%2!=0)//和上一题一样处理n为奇数的情况，就是补全中心少的那个数
            res.push_back(matrix[n/2][n/2]);
        return res;
    }
};

146.螺旋遍历二维数组

LCR 146. 螺旋遍历二维数组 - 力扣（LeetCode）

和54题一模一样，不过可以array可以为空，要单独处理一下

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        vector<int> res;
        if(array.size()==0)
            return res;
        int m = array.size();
        int n = array[0].size();
        int x = min(m / 2, n / 2);//循环圈数
        int offset = 1;//控制每条边所要处理的个数
        int startx = 0, starty = 0, i = 0, j = 0;//每一圈的起始位置和转圈时的下标
        
        while(x--)
        {
            i=startx;
            j=starty;
            for (; j < n - offset; j++)//往右
                res.push_back(array[i][j]);
            for (; i < m - offset; i++)//往下
                res.push_back(array[i][j]);
            for (; j > startx; j--)//往左
                res.push_back(array[i][j]);
            for (; i > starty; i--)//往上
                res.push_back(array[i][j]);
            startx++;
            starty++;
            offset++;
        }
        if (res.size() < n * m && n > m)//对多出来的行的处理
        {
            for (int i = starty; i < n - offset+1; i++)
                res.push_back(array[startx][i]);
        }
        else if (res.size() < n * m && n < m)//对多出来的列的处理
        {
            for (int i = startx; i < m - offset + 1; i++)//注意是m-offset+1而不是n-offset+1，不要想当然
                res.push_back(array[i][starty]);
        }
        else if(n==m&&n%2!=0)//和上一题一样处理n为奇数的情况，就是补全中心少的那个数
            res.push_back(array[n/2][n/2]);
        return res;
    }
};