题目描述

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:
Input: 3
Output: [1,3,3,1]

题目思路

代码 C++

• 思路一、常规方法，设置两个数组，依次循环使用，返回结果

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result;
        vector<int> a;
        vector<int> b;
        
        for(int i=0; i <= rowIndex; i++){
            if(i == 0){
                a.push_back(1);
                result = a;
            }
            else if(i == 1){
                b.push_back(1);
                b.push_back(1);
                result = b;
            }
            else{
                a.clear();
                a.push_back(1);
                for(int j=0; j < b.size()-1; j++){
                    a.push_back(b[j]+b[j+1]);
                }
                a.push_back(1);
                result = a;
                b = a;
            }
        }
        return result;
    }
};

• 思路二、高妙方法，充分利用了pascal形状的特性

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result(rowIndex + 1); // 初始化全为 0
        result[0] = 1;
        
        for(int i=0; i <= rowIndex; i++){
            for(int j=i; j > 0; j--){
                result[j] = result[j] + result[j-1];
            }
        }
        
        return result;
    }
};

总结展望