題目描述
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
思路
得到第k+1行的一整列的值姥份。
解法1得到前k+1行的值郭脂，將最后一行的return就可以。
解法2澈歉，只用一個(gè)一維數(shù)組展鸡，前一行的數(shù)變成后一行時(shí)：
- 直接在后面添加一個(gè)1
- 從倒數(shù)第二個(gè)開始等于倒數(shù)第二個(gè)+倒數(shù)第三個(gè)，也就是相鄰的兩個(gè)相加埃难，形成新的行的值娱颊，又不會(huì)破壞還未算的數(shù)。
例如：1 2 2 1 首先添加個(gè)1凯砍，變?yōu)? 2 2 1 1 然后從倒數(shù)第二個(gè)開始變化箱硕，相鄰兩個(gè)相加。
第一次：1 2 2 3 1
第二次：1 2 4 3 1
第三次：1 3 4 3 1
這樣就得到了下一行的數(shù)悟衩，每次都是一樣的方法剧罩。
代碼
解法1：
class Solution {
public:
vector<int> getRow(int numRows) {
vector< vector<int> > res(numRows+1);
vector<int> t;
int i, j;
for(i = 0; i < numRows+1; i++)
{
res[i].resize(i+1);//第i行分配i個(gè)列 不可一下子分配n行n列
res[i][0] = 1;
res[i][res[i].size()-1] = 1;
for(j = 1; j < i; j++)
{
res[i][j] = res[i-1][j-1] + res[i-1][j];
}
}
for(j = 0; j < numRows+1; j++)
{
t.push_back(res[numRows][j]);
}
return t;
}
};
解法2：
class Solution {
public:
vector<int> getRow(int numRows) {
vector<int> t;
int i, j;
t.push_back(1);
if(numRows == 0)
return t;
t.push_back(1);//numRows = 1時(shí) 結(jié)果是1 1
for(i = 2; i <= numRows; i++)
{
t.push_back(1);//先寫入1
for(j = i - 1; j > 0; j--)
{
t[j] = t[j] + t[j-1];//形成新的數(shù)
}
}
return t;
}
};
