Leetcode Pascal's Triangle II - c++编程基础

Pascal's Triangle II

Total Accepted: 4253 Total Submissions: 14495My Submissions

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

下面程序空间效率O(k)，使用了两个vector 交替使用，因为只利用上一行就能填写下一行了。

vector
  
    getRow(int rowIndex) 
	{
		vector
   
     pre; if (rowIndex < 0) return pre; vector
    
      rs(1,1); for (int i = 0; i < rowIndex; i++) { pre.clear(); rs.swap(pre); rs.push_back(1); for (int j = 0; j < i; j++) { rs.push_back(pre[j]+pre[j+1]); } rs.push_back(1); } return rs; }

因为只利用当前行两个数值的信息覆盖新填写的数列格也是可以的，所以只利用一个vector 也是可以的。

Leetcode上总有人写出更加简洁的程序的：

vector
   
     getRow(int rowIndex) 
	{
		vector
    
      array; for (int i = 0; i <= rowIndex; i++) { for (int j = i-1; j > 0; j--) { array[j] = array[j-1] + array[j]; } array.push_back(1); } return array; }