Friday, December 28, 2012

[LeetCode] Pascal's Triangle II 解题报告


Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].


[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
Note:
Could you optimize your algorithm to use only O(k) extra space?
» Solve this problem

[解题报告]

把上面的例子变一下型就清楚了

[
 [1],
 [1,1],
 [1,2,1],
 [1,3,3,1],
 [1,4,6,4,1]
]
定义T[i][j]为该三角形i行,第j列的元素,所以可以获得递推函数为


   T[i][j] = T[i-1][j] + T[i-1][j-1] if i>0 && j>0
         Or
            =  1  if i=0
         Or
            =  T[i-1][j]  if j=0

滚动数组实现。注意Line11,要从后往前加,否则会产生冗余计算。

[Code]
1:    vector<int> getRow(int rowIndex) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<int> result;  
5:      result.resize(rowIndex+2);  
6:      for(int i =0; i< rowIndex+2; i++)  
7:        result[i] = 0;  
8:      result[1]=1;  
9:      for(int i =0; i< rowIndex; i++)  
10:      {  
11:        for(int j =rowIndex+1; j>0; j--)  
12:        {  
13:          result[j] = result[j-1] + result[j];  
14:        }  
15:      }  
16:      result.erase(result.begin());  
17:      return result;  
18:    }  

No comments: