Given an index k, return the kth row of the Pascal‘s triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
1. 通过一维数组来模拟杨辉三角逐渐变换的情况
class Solution {
public:
vector<int> getRow(int numRows) {
vector<int>result(numRows+1,0);
result[0] = 1;
for (int i=1; i <= numRows; i++)
{
for (int j=i; j >= 1 ;j--)
{
result[j] += result[j-1];
}
}
return result;
}
};
;
2.数学公式
class Solution {
public:
vector<int> getRow(int numRows) {
vector<int>result(numRows+1,0);
result[0] = result[numRows] = 1;
for (int i=1; i < (numRows+2)/2 ; i++)
{
result[i] = result[numRows-i] = result[i-1] * (numRows - i + 1) /i;
}
return result;
}
};
3.关于杨辉三角的规律
leetcode 119 Pascal's Triangle II
原文：http://www.cnblogs.com/sxy-798013203/p/7635841.html