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?
Solution:
这题的思路是抓住上一行是如何转化为下一行的：
- 先在上一行的最左边插入一个1
- 然后在此时的上一行中除了头尾两个数之外，每个数 [i] = [i] + [i + 1]，得到新的一行。
将Pascal's Triangle按如下形状整理可更加直观地表现以上思路：
1
11
121
1331
14641
code:
public class Solution
{
public List<Integer> getRow(int rowIndex)
{
if(rowIndex < 0)
return new ArrayList<>();
List<Integer> row = new ArrayList<>();
for(int i = 0; i <= rowIndex; i ++)
{
row.add(0, 1);
//for (int j = 1; j < row.size() - 1; j ++)
for(int j = 1; j < i; j ++)
row.set(j, row.get(j) + row.get(j + 1));
}
return row;
}
}
