[LeetCode]Pascal's Triangle II

最新推荐文章于 2019-06-24 19:31:47 发布

风啸葛溪

最新推荐文章于 2019-06-24 19:31:47 发布

阅读量537

点赞数

分类专栏： LeetCode解题

本文链接：https://blog.csdn.net/Roger__King/article/details/37968529

版权

LeetCode解题专栏收录该内容

28 篇文章

订阅专栏

题目：

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?

来源：https://oj.leetcode.com/problems/pascals-triangle-ii/

思路：

杨辉三角的应用，和之前的类似

C++ AC代码：

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> tmp, result; 
        
		if(rowIndex < 0)
            return result;
       
        result.push_back(1);
		
        for(int i=1;i<=rowIndex;i++)
        {
            tmp.push_back(1);           //每行的头数字
            
            for(int j=1;j<i;j++)
                tmp.push_back(result[j-1] + result[j]);   //每行中间的数字
            
            tmp.push_back(1);         //每行的尾数字
			result = tmp;
			tmp.clear();
        }
        return result;		
    }
};

运行时间 4ms

另一种网上的方法：

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> myvector, tmpvector; 
        if(rowIndex<0)  
            return myvector;  
        myvector.push_back(1);  
        for(int i=1;i<=rowIndex;i++)  
        {   
            tmpvector.push_back(1);  
            for(int j=1;j<i;j++)  
                tmpvector.push_back(myvector[j-1]+myvector[j]);  
            tmpvector.push_back(1);  
            myvector = tmpvector;  
            tmpvector.clear();  
        }                 
        return myvector;  
    }
};

运行时间28ms