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

[LeetCode]Pascal's Triangle

2024-07-08 03:56:39   229人阅读

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 };

 


联系
我们