【LeetCode】119. Pascal’s Triangle II

LeetCode-119

Links:https://leetcode.com/problems/pascals-triangle-ii/

Given an index k, return the k^th 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?

大意：求出杨辉三角中的第k行，只能用k个空间。

解法如下：

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int>nums;
        nums.push_back(1);
        for(int i=0;i<rowIndex;i++)
        {
            nums.push_back(1);
            for(int j=i;j>0;j--)
            {
                nums[j] = nums[j-1] + nums[j];
            }
        }
        return move(nums);
    }
};

class Solution {

public:

vector<int> getRow(int rowIndex) {

vector<int>nums;

nums.push_back(1);

for(int i=0;i<rowIndex;i++)

{

nums.push_back(1);

for(int j=i;j>0;j--)

{

nums[j] = nums[j-1] + nums[j];

}

return move(nums);

}

};

PS.我记得以前有一个公式可以求出某一项的值.如果找得到的话，可以直接求这一行的，就不需要再一行一行的计算了…

好吧，找到了代码如下：用的是杨辉三角公式C(n,m)即第n行第m个数据.

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int>nums;
        long long num = 1;
        int n = rowIndex;
        nums.push_back(1);
        for(int i=1;i<=rowIndex;i++)
        {
            num = num*(n-i+1)/i;
            nums.push_back((int)num);
        }
        return nums;
    }
};

class Solution {

public:

vector<int> getRow(int rowIndex) {

vector<int>nums;

long long num = 1;

int n = rowIndex;

nums.push_back(1);

for(int i=1;i<=rowIndex;i++)

{

num = num*(n-i+1)/i;

nums.push_back((int)num);

}

return nums;

}

};

【LeetCode】119. Pascal’s Triangle II

Tagged on: LeetCode