环形矩阵（螺旋矩阵）&&蛇形矩阵

先说一下环形矩阵（螺旋矩阵）&&蛇形矩阵的区别

🏳️‍🌈🏳️‍🌈🏳️‍🌈 环形矩阵

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

林小鹿的题解螺旋矩阵 II | 模拟解法，代码简洁易懂 【c++/java版本】 – 螺旋矩阵 II – 力扣（LeetCode）

y总的视频讲解AcWing 756. 蛇形矩阵（寒假每日一题） – AcWing

讲vector数组的好文章http://t.csdn.cn/CC4m9

题目

LeetCode代码

时间复杂度分析： 矩阵中的每个数都被遍历一次，因此时间复杂度为O(n^2)，n是给定的正整数。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>>res(n, vector<int>(n, 0));//使用vector定义一个二维数组
            int dx[]={-1,0,1,0},dy[]={0,1,0,-1};/方向偏移数组
            int x=0,y=0,d=1;//当前位置
            for(int i=1;i<=n*n;i++)
            {
                res[x][y]=i;
                int a=x+dx[d],b=y+dy[d];
                if(a<0||a>=n||b<0||b>=n||res[a][b])//出界或者该位置已经被走过
                {
                    d=(d+1)%4;//更改方向
                    a=x+dx[d],b=y+dy[d];//更改方向后要走的地方
                }
                x=a,y=b;
            }
            return res;
     }
};

必须要重新定义一个二维数组

⭐其中  后面的res(n,vestor<int>(n))

⭐ 初始化一个vector类型的数组，容量为n，初始值是0

AcWing代码

#include <iostream>
using namespace std;
int res[100][100];
int main()
{
    int n, m;
    cin >> n >> m;

    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

    for (int x = 0, y = 0, d = 0, k = 1; k <= n * m; k ++ )
    {
        res[x][y] = k;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || res[a][b])
        {
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }

    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ ) cout << res[i][j] << ' ';
        cout << endl;
    }

    return 0;
}

外加一个题

这两个题在细节上有差别

 注意 行 列 的表示方式

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

        int row = matrix.size();//matrix的行
        int col = matrix[0].size();//matrix的列

        int x = 0, y = 0, mark = 0, n = row*col;
        for (int i = 0; i < n; i++)
        {
            ans.push_back(matrix[x][y]);//从vector最后加入matrix[x][y]
            matrix[x][y] = 1;//表示已经走过

            int a = x + dx[mark], b = y + dy[mark];
            if (a < 0 || b < 0 || a >= row || b >= col || matrix[a][b] == 1){
                mark = (mark + 1) % 4;
                a = x + dx[mark], b = y + dy[mark];
            }
            x = a, y =b;
        }
        return ans;
    }
};

🏳️‍🌈🏳️‍🌈🏳️‍🌈蛇形矩阵

这种矩阵得找规律

1027-蛇形矩阵_牛客竞赛语法入门班数组字符串习题 (nowcoder.com) 

#include<iostream>
using namespace std;
int main()
{
    int n,a[1001][1001]={1},i=0,j=0;
    scanf("%d",&n);
    int k=1;//1向右，2斜向下，3向下，4斜向上
    while(i!=n&&j!=n)
    {
        if(k==1)
        {
            a[i][j+1]=a[i][j]+1;
            j++;
            if(i==0)//判断i的值，从而得到后面要走的方向
                k=2;
            else if(i==n-1)
                k=4;
        }
        if(k==2)
        {
            a[i+1][j-1]=a[i][j]+1;
            i++;j--;
            if(i==n-1)
                k=1;
            else if(j==0&&i!=n-1)
                k=3;
            else k=2;
        }
        if(k==3)
        {
            a[i+1][j]=a[i][j]+1;
            i++;
            if(j==0)
                k=4;
            else k=2;
        }
        if(k==4)
        {
            a[i-1][j+1]=a[i][j]+1;
            i--;j++;
            if(i==0&&j!=n-1)
                k=1;
            else if(j==n-1)
                k=3;
            else k=4;
        }
    }        
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("%d ",a[i][j]);
        }
            printf("\n");
    }
    return 0;
}