首页 > 代码库 > [LeetCode]Pascal's Triangle

[LeetCode]Pascal's Triangle

Description:

 

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]]

 

中文描述:

给出numRows,生成Pascal三角形的前numRows行。

比如给出numRows= 5, 那么返回:

 

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

 

解答:

刚开始看到这道题目,觉得有简便方法可循,但是无法找出规律= =

于是只好brute force。

按照定义:

第一行只有一个数:1;

第二行有两个数:1,1;

从第三行开始的第n行中,共有n个数。首尾两个数为1,而第i个数( 1 < i < n )的值,则为第n-1行中第i-1个数与第i个数相加的和,用数学公式表达为:

N[i] = N[i-1] + N[i]。

注意,这里的i指的是个数,从1开始计数;不要和数组的下标弄混了。

这个算法的时间为O(n2)

 

 

 1 class Solution { 2 public: 3     vector<vector<int> > generate(int numRows) { 4          5         if( numRows <= 0 ) { 6             vector<vector<int>> r; 7             return r; 8         } 9         10         vector<vector<int>> result;11         vector<int> last;12         if( numRows == 1 ) {13             last.push_back( 1 );14             result.push_back( last );15             return result;16         }17         18         for( int i = 1; i <= numRows; i++ ) {19             vector<int> row;20             21             row.push_back( 1 );22             if( i == 1 ) {23                 result.push_back( row );24                 continue;25             }26             27             if( i == 2 ) {28                 row.push_back( 1 );29                 last = row;30                 result.push_back( row );31                 continue;32             }33             34             if( i >= 3 ) {35                 for( int j = 1; j < i -1; j++ ) {36                     int tmp = last[j-1] + last[j];37                     row.push_back( tmp );38                 }39                 40                 row.push_back( 1 );41             }42             43             last = row;44             result.push_back( row );45         }46         47         return result;48     }49 };