LeetCode 119. Pascal's Triangle II

题目描述:

给定非负索引k，其中k<=33，返回Pascal三角形的第k个索引
在Pascal三角形中，每个数字是它正上方的两个数字的总和

行索引从0开始

Example

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

C++输入格式

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        
    }
};

范例

子函数

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> A(rowIndex+1, 0); //定义一个数组长度为 rowIndex+1初始化全为0 
        A[0] = 1;
        for(int i=1; i<rowIndex+1; i++)
        {
            cout<<"每次A的变化:"<<endl;
            for(int j=i; j>=1; j--)
            {
                A[j] += A[j-1];
                
                cout<<A[j]<<" ";
            }
            
            cout<<endl;  
            
        }
            
        return A;
    }
};

main

int main()
{
    vector<int>  myvector;
    int i;
    cout<<"Please input a number:"<<endl;
    cin>>i;
    Solution sol;
    myvector = sol.getRow(i);   
    for(int j =0;j<myvector.size();j++)
    {   
        cout<<myvector[j]<<" ";
    }
    cout<<endl;
    return 0;
}

测试结果:

image.png

算法思想

因为在Pascal三角形中，每个数字是它正上方的两个数字的总和。所以在子函数中返回类型是动态数组，定义一个动态数组并初始化全为0，然后索引到哪一行就循环几次，每次循环都找到每个数字都是上一层两个数字的和即A[j] += A[j-1]

i =1时 A[1]+=A[0] A[1] =A[1]+A[0]=1
i =2 时 A[2]+=A[1] A[2] =A[1]+A[2]=1 A[1]+=A[0] A[1] =A[1]+A[0]=2
i =3 时 A[3]+=A[2] A[3] =A[3]+A[2]=1 A[2]+=A[1] A[2] =A[1]+A[2]=3
A[1]+=A[0] A[1] =A[1]+A[0]=3
i =4 时 A[4]+=A[3] A[4] =A[3]+A[4]=1 A[3]+=A[2] A[3] =A[3]+A[2]=4
A[2]+=A[1] A[2] =A[1]+A[2]=6 A[1]+=A[0] A[1] =A[1]+A[0]=4

范例二

class Solution {
public:
    vector<int> getRow(int rowIndex) {
    vector<int> ans(rowIndex+1,1);
    int small = rowIndex/2;
    long comb = 1;
    int j = 1;
    for (int i=rowIndex; i>=small; i--)
    {
        comb *= i;
        comb /= j;
        j ++;
        ans[i-1] = (int)comb;
        cout<<"ans[i-1]:"<<ans[i-1]<<" ";
        ans[j-1] = (int)comb;
        cout<<"ans[j-1]:"<<ans[j-1]<<" ";
        cout<<endl;
    }
    return ans;
}
};

测试结果