杨辉三角 II（leetcode.119）
原创
1.数学方法
图片来自互联网
我们只需计算所求行的值就可以了
Cnk=n!/(k!(n−k)!)=(n∗(n−1)∗(n−2)∗...(n−k+1))/k!
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> result;
for(int i = 0;i <= rowIndex;i++){
result.push_back(C(rowIndex, i));
}
return result;
}
int C(int n, int k){
long res = 1;
for(int i = 1;i <= k;i++){
res = res * (n - k + i)/i;
}
return (int)res;
}
};2.常规方法
因为只需要返回第k行的数组，所以只需要两个数组pre和res；
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> pre;
vector<int> res;
for(int i = 0;i <= rowIndex;i++){
res.clear();
for(int j = 0;j <= i;j++){
if(j == 0||j == i)
res.push_back(1);
else
res.push_back(pre[j] + pre[j-1]);
}
pre = res;
}
return res;
}
};3.大佬的做法（✪ ω ✪）
膜拜~
可以看作是方法二的提升版本
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> result;
for(int i = 0; i <= rowIndex; ++i){
result.push_back(1);
for(int j = i - 1; j > 0; --j){
result[j] += result[j - 1];
}
}
return result;
}
};原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
腾讯云开发者
