题解 | #蛇形矩阵#
蛇形矩阵
http://www.nowcoder.com/practice/649b210ef44446e3b1cd1be6fa4cab5e
题意：
按照以下格式输出矩阵上三角形：
方法一：
直接模拟
思路：斜着遍历。
因为根据行下标和列下标之和，可以划分为不同斜线，
最后遍历每条斜线，即可得到结果。
#include <bits/stdc++.h>
using namespace std;
int a[105][105];
int main(){
int n;
while(cin >> n){
int num=1;
for(int i=0;i<n;i++){//下标总和
for(int j=0;j<=i;j++){//列下标
a[i-j][j]=num++;//行下标=下标总和-列下标
}
}
for(int i=0;i<n;i++){//遍历输出
for(int j=0;j<n-i;j++){
cout << a[i][j] << " ";
}
cout << endl;
}
}
return 0;
}
时间复杂度：
空间复杂度：
方法二：
找规律
思路：
规律：蛇形矩阵的每个数等于上一行右一列的数-1。
因此，先初始化第一行，第一行相邻数的间隔值分别为+2，+3，+4，+5......接着，遍历其他行，根据每个数等于上一行右一列的数-1，即可求解成功。
#include <bits/stdc++.h>
using namespace std;
int a[105][105];
int main(){
int n;
while(cin >> n){
int x=2;//第一行的相邻数的间隔
a[0][0]=1;
for(int i=1;i<n;i++){//初始化第一行
a[0][i]=a[0][i-1]+(x++);
}
for(int i=1;i<n;i++){//遍历其他行数
for(int j=0;j<n-i;j++){
a[i][j]=a[i-1][j+1]-1;//a[i][j]=上一行右一列的数-1
}
}
for(int i=0;i<n;i++){//遍历输出
for(int j=0;j<n-i;j++){
cout << a[i][j] << " ";
}
cout << endl;
}
}
return 0;
}
时间复杂度：空间复杂度：
查看23道真题和解析