[LeetCode]119.Pascal's Triangle II

题目

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?

思路

无

代码

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

    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> row(rowIndex+1);
            vector<int> tmp = row;
            for (int i = 0;i < rowIndex+1;++i) {
                tmp[0] = tmp[i] = 1;
                for (int j = 1;j < i;++j) {
                    tmp[j] = row[j-1] + row[j];
                }//for
                row = tmp;
            }//for
            return row;
        }
    };

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

运行时间