得到杨辉三角某行数据算法优化

引导

注意：最佳方案在文章最后，中间为思考过程

最朴实的方法：

        我们将这些数据的第一行称作为杨辉三角的第0行，每行的第一个数据称作为第0个数据，以方便之后的算法

        根据杨辉三角的基础性质，即 第row 行 index个数据等于第row-1行第index 数据与 row-1 第index-1 两个数据的和 即 T[row][index]=T[row-1][index]+T[row-1][index-1]

        由此我们可以得到杨辉三角每一行的数据

        #杨辉三角 <-这题可由此方式解决

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);
        for(int i=0;i<numRows;i++){
            ans[i].resize(i+1);
            ans[i][0]=1;ans[i][i]=1;
            for(int j=1;j<i;j++){
                ans[i][j]=ans[i-1][j]+ans[i-1][j-1];
            }
        }
        return ans;
    }
};

但是若是只想要某一行的数据，这种方式就太过浪费时间

例如#杨辉三角II <-此题就要求在时间复杂度O(n)的情况下解决问题

        那么根据我们高中所学，杨辉三角中的每一项都可看作二项式系数的一项

        例如第m行第n个数据是C(m,n) 即(m*(m-1)*(m-2)*...(m-n+1))/(n!)

        其中C(m,n)中我们可用（factoriol是阶乘的意思）factoriol(m)/(factorial(m-n)*factorial(n))表示

由此写出代码

class Solution {
public:
    long long factorial(int n){
        long long ans=1;
        for(int i=2;i<=n;i++){
            ans*=i;
        }return ans;
    }
    long long c(int rows,int index){
        if(index>rows/2){return c(rows,rows-index);}
//此处利用排列组合的性质c(m,n)==c(m,m-n)以优化算法
        long long numerator=factorial(rows);//分子
        long long denominator=factorial(index)*factorial(rows-index);//分母
        return numerator/denominator;
    }
    vector<int> getRow(int rowIndex){
        vector<int> ans(rowIndex+1);
        ans[0]=1;ans[rowIndex]=1;
        for(int i=1;i<rowIndex;i++){
            ans[i]=c(rowIndex,i);
        }
        return ans;
    }
};

不过这个代码无法通过测试，原因是：

数据超出了long long 的范围因此报错

分析原因我们可以发现阶乘会使得数据大得多

因此我们回归C(m,n)最原本的计算方法即：C(m,n) ==(m*(m-1)*(m-2)*...(m-n+1))/(n!)

得出代码：

    long long c(int rows,int index){
        if(index>rows/2){return c(rows,rows-index);}
        long long numerator=1;
        long long denominator=factorial(index);
        for(int i=0;i<index;i++){
            numerator*=rows-i;
        }
        return numerator/denominator;
    }

但是运行出来后仍然会由数据溢出的报错，因此我们可以在计算过程中提前对分子与分母进行约分：因为分子分母都是连续的整数相乘，所以他们会有大量的2或者3 的公因数

    long long c(int rows,int index){
        if(index>rows/2){return c(rows,rows-index);}
        long long numerator=1;
        long long denominator=factorial(index);
        for(int i=0;i<index;i++){
            numerator*=rows-i;
            while(numerator%2==0&&denominator%2==0){
                numerator/=2;
                denominator/=2;
            }
        }
        return numerator/denominator;
    }

运行得出的结果完美

 再看一下官方题解

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;
        }
        return row;
    }
};

比我的简单的多。。

        看玩题解之后恍然大悟，我们可以根据前项推出后向的和，从而越过求阶乘的步骤，不仅简单，速度还更快，其递推公式是：C(m,n)=C(m,n-1)*((n-m+1)/n)

推理过程如下：C(m,n-1)==(m*(m-1)*(m-2)*...(m-n+2))/((n-1)!)

                         C(m,n) ==(m*(m-1)*(m-2)*...(m-n+2)*(m-n+1))/(n!)

                                     ==C(m,n-1)*(m-n+1)/n