Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,

Return

[     [1],    [1,1],   [1,2,1],  [1,3,3,1], [1,4,6,4,1]]

 

思路：杨辉三角，直接按规律生成即可

vector
     
      
        > generate(int numRows) {        vector
       
        
         > ans;        for(int i = 0; i < numRows; i++)        {            vector
         
           v(i + 1, 1);            for(int j = 1; j < i; j++)            {                v[j] = ans[i - 1][j - 1] + ans[i - 1][j];            }            ans.push_back(v);        }        return ans;    }
         
        
       
      
     

 

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?

思路：

要靠数学公式了，设杨辉三角的最顶层为第0行，每行的第一个数字是第0个，则

第 i 行第 j 个元素的计算为：C(i, j) =  (i)! / (j)! * (i - j)! 

那么第 i 行第 j 个元素和它前一个元素的关系是  ans[i][j] = ans[i][j - 1] * (i - j + 1) / j; //这里要注意不要越界

vector
     
       getRow(int rowIndex) {        vector
      
        ans(rowIndex + 1, 1);        ans[rowIndex - 1] = ans[1] = rowIndex;        for(int i = 2; i < rowIndex / 2 + 1; i++)        {            ans[rowIndex - i] = ans[i] = (long long)ans[i - 1] * (rowIndex - i + 1) / i; //用long long防止越界 同时利用杨辉三角的对称性减少一半的计算量        }        return ans;    }