先说一下环形矩阵(螺旋矩阵)&&蛇形矩阵的区别
🏳️🌈🏳️🌈🏳️🌈 环形矩阵
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; }