Pascal's Triangle II

Total Accepted: 42320 Total
Submissions: 143760

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?

此处有内存要求尽管採用第一种方法能够ac可是明显不符合要求

class Solution {

public:

    vector<int> getRow(int rowIndex) {

        vector<vector<int> >res;

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

        {

            vector<int>vec(i+1,1);

            if(i>1)

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

                    vec[j]=res[i-1][j-1]+res[i-1][j];

            res.push_back(vec);

            vector<int>().swap(vec);

        }

        return res[rowIndex];

    }

};

我们必须又一次设计算法。

class Solution {

public:

    vector<int> getRow(int rowIndex) {

        vector<int>res(rowIndex+1,1);

        if(rowIndex<2)

        return res;

       long long nth=1;

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

            nth*=i;

         long long rth=1,n_rth=nth;

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

        {

            n_rth/=(rowIndex-i+1);

            res[i]=nth/rth/n_rth;

                        rth*=(i+1);

        }

        return res;

    }

};

用来存储二项式系数的值非常easy在rowIndex=24时候就报错了

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvemhvdXllbGlodWE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

class Solution {

public:

    vector<int> getRow(int rowIndex) {

        vector<int>res(rowIndex+1,1);

        if(rowIndex<2)

        return res;

        int t1,t2;

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

    {

        t1=res[0];

        t2=res[1];

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

        {

            res[j]=t1+t2;

            t1=t2;

            t2=res[j+1];

        }

        res[i]=1;

    }

        return res;

    }

};