题目描述:
给定非负索引k,其中k<=33,返回Pascal三角形的第k个索引
在Pascal三角形中,每个数字是它正上方的两个数字的总和
- 行索引从0开始
Example
Input: 3
Output: [1,3,3,1]
C++输入格式
class Solution {
public:
vector<int> getRow(int rowIndex) {
}
};
范例
子函数
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> A(rowIndex+1, 0); //定义一个数组长度为 rowIndex+1初始化全为0
A[0] = 1;
for(int i=1; i<rowIndex+1; i++)
{
cout<<"每次A的变化:"<<endl;
for(int j=i; j>=1; j--)
{
A[j] += A[j-1];
cout<<A[j]<<" ";
}
cout<<endl;
}
return A;
}
};
main
int main()
{
vector<int> myvector;
int i;
cout<<"Please input a number:"<<endl;
cin>>i;
Solution sol;
myvector = sol.getRow(i);
for(int j =0;j<myvector.size();j++)
{
cout<<myvector[j]<<" ";
}
cout<<endl;
return 0;
}
测试结果:
算法思想
因为在Pascal三角形中,每个数字是它正上方的两个数字的总和。所以在子函数中返回类型是动态数组,定义一个动态数组并初始化全为0,然后索引到哪一行就循环几次,每次循环都找到每个数字都是上一层两个数字的和即A[j] += A[j-1]
- i =1时 A[1]+=A[0] A[1] =A[1]+A[0]=1
- i =2 时 A[2]+=A[1] A[2] =A[1]+A[2]=1 A[1]+=A[0] A[1] =A[1]+A[0]=2
- i =3 时 A[3]+=A[2] A[3] =A[3]+A[2]=1 A[2]+=A[1] A[2] =A[1]+A[2]=3
A[1]+=A[0] A[1] =A[1]+A[0]=3 - i =4 时 A[4]+=A[3] A[4] =A[3]+A[4]=1 A[3]+=A[2] A[3] =A[3]+A[2]=4
A[2]+=A[1] A[2] =A[1]+A[2]=6 A[1]+=A[0] A[1] =A[1]+A[0]=4
范例二
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ans(rowIndex+1,1);
int small = rowIndex/2;
long comb = 1;
int j = 1;
for (int i=rowIndex; i>=small; i--)
{
comb *= i;
comb /= j;
j ++;
ans[i-1] = (int)comb;
cout<<"ans[i-1]:"<<ans[i-1]<<" ";
ans[j-1] = (int)comb;
cout<<"ans[j-1]:"<<ans[j-1]<<" ";
cout<<endl;
}
return ans;
}
};
测试结果
个人感觉这种方法比上一种方法更简单,事实证明这种方法执行时间也较短。因为输出的数据是对称的,这种方法只考虑了这一行的数据特征并没有涉及上一行的数据。但是这种系统过不去,很难受。