首页 > 代码库 > [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 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。