[LeetCode]118.Pascal's Triangle

题目

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

思路

模拟

代码

    /**------------------------------------
    *   日期：2015-02-06
    *   作者：SJF0115
    *   题目: 118.Pascal's Triangle
    *   网址：https://oj.leetcode.com/problems/pascals-triangle/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        vector<vector<int> > generate(int numRows) {
            vector<int> row;
            vector<vector<int> > triangle;
            if(numRows >= 1){
                row.push_back(1);
                triangle.push_back(row);
            }//if
            if(numRows >= 2){
                row.push_back(1);
                triangle.push_back(row);
            }//if
            for(int i = 2;i < numRows;++i){
                row.clear();
                row.push_back(1);
                for(int j = 1;j < i;++j){
                    row.push_back(triangle[i-1][j-1]+triangle[i-1][j]);
                }//for
                row.push_back(1);
                triangle.push_back(row);
            }//for
            return triangle;
        }
    };

    int main(){
        Solution s;
        int n = 5;
        vector<vector<int> > result = s.generate(n);
        // 输出
        for(int i = 0;i < result.size();++i){
            for(int j = 0;j < result[i].size();j++){
                cout<<result[i][j]<<"  ";
            }//for
            cout<<endl;
        }//for
        return 0;
    }

运行时间

思路二

    /**------------------------------------
    *   日期：2015-02-06
    *   作者：SJF0115
    *   题目: 118.Pascal's Triangle
    *   网址：https://oj.leetcode.com/problems/pascals-triangle/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    class Solution {
    public:
        vector<vector<int> > generate(int numRows) {
            vector<vector<int>> triangle(numRows);
            for (int i = 0;i < numRows;++i) {
                triangle[i].resize(i + 1);
                triangle[i][0] = triangle[i][i] = 1;
                for (int j = 1;j < i;++j) {
                    triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
                }//for
            }//for
            return triangle;
        }
    };

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>