环形矩阵(螺旋矩阵)&&蛇形矩阵

简介: 环形矩阵(螺旋矩阵)&&蛇形矩阵

4.2.png


先说一下环形矩阵(螺旋矩阵)&&蛇形矩阵的区别
4.1.png

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


LeetCode 59. 螺旋矩阵 II - 力扣(LeetCode)


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


y总的视频讲解AcWing 756. 蛇形矩阵(寒假每日一题) - AcWing


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

4.2.png题目4.3.png

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;
     }
};

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

4.4.png

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

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

4.5.png4.6.png

4.7.png

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;
}

外加一个题

这两个题在细节上有差别4.8.png

注意 行 列 的表示方式4.9.png

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)

4.10.png

#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;
}
相关文章
|
6月前
|
算法 测试技术 C#
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
|
算法 测试技术 C++
C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]
C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]
|
1月前
lanqiao OJ 246 矩阵计数
lanqiao OJ 246 矩阵计数
11 0
|
5月前
力扣随机一题 6/28 数组/矩阵
力扣随机一题 6/28 数组/矩阵
41 0
|
6月前
矩阵 螺旋矩阵
矩阵 螺旋矩阵
48 2
|
6月前
|
Java
每日一题《剑指offer》数组篇之顺时针打印矩阵
每日一题《剑指offer》数组篇之顺时针打印矩阵
57 0
每日一题《剑指offer》数组篇之顺时针打印矩阵
|
6月前
|
Java
【剑指offer】-顺时针打印矩阵-19/67
【剑指offer】-顺时针打印矩阵-19/67
剑指offer 28. 顺时针打印矩阵
剑指offer 28. 顺时针打印矩阵
53 0
|
算法 C++
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
|
人工智能
Leetcode53/152—最大子数组和/最大子数组乘积(状态转移方程/不熟)
Leetcode53/152—最大子数组和/最大子数组乘积(状态转移方程/不熟)
109 0