118.杨辉三角

题目描述

在这里插入图片描述

原题链接

118.杨辉三角

思路点拨

观察杨辉三角，我们很容易发现以下三点：

1.杨辉三角每行的元素个数和当前行数相等。
2.每行的第一个和最后一个元素都是 1。
3.每行除第一个元素和最后一个元素外，其余的元素都是上一行左右两元素的和。

源码解析

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        //利用vector容器在堆区申请一个二维数组,用于存储杨辉三角
        vector<vector<int>> ret(numRows);
        for(int i=0;i<numRows;++i)
        {
            vector<int> rows(i+1);//申请i+1个空间的一维数组
            rows[0]=1;//每行第一个为1
            rows[i]=1;//每行最后一个为1
            for(int j=1;j<i;++j)//计算每行第一个到最后一个之间的数
            {
                rows[j]=ret[i-1][j-1]+ret[i-1][j];//由上一行数对应两者相加
            }
            ret[i]=rows;//每个一维数组赋给二维数组的对应行
        }
        return ret;
    }
};

119.杨辉三角2

题目描述

在这里插入图片描述

原题链接

杨辉三角2

思路点拨

方法一：写完上题再写这题的话，我们可以讨个巧，把上题代码复制过来，改一下参数，最后返回杨辉三角的最后一行便可。

方法二：首先我们如果知道杨辉三角某一行，我们便很容易根据这一行来得到下一行。由此，我们利用两个数组，一个数组存储杨辉三角当前行，另一个存储当前行的上一行。两个数组循环往复，可以得到杨辉三角的第n行。

源码解析

法一：

class Solution {   //这里没什么好说的，和上一题差别不大
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> ret(rowIndex+1);//rowIndex从0开始的，所以这里+1
        for(int i=0;i<rowIndex+1;++i)
        {
            vector<int> rows(i+1);
            rows[0]=1;
            rows[i]=1;
            for(int j=1;j<i;++j)
            {
                rows[j]=ret[i-1][j-1]+ret[i-1][j];
            }
            ret[i]=rows;
        }
        return ret[rowIndex];
    }
};

法二：

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row1;//用于存储杨辉三角上一行
        for(int i=0;i<rowIndex+1;++i)
        {
            vector<int> row2(i+1);//用于存储杨辉三角当前行
            row2[0]=row2[i]=1;//第一个元素和最后一个元素为1
            for(int j=1;j<i;++j)//i=0和i=1时，也就是杨辉三角前两行，不会执行这个循环
            {
                row2[j]=row1[j-1]+row1[j];//当前行的第j个元素是上一行的第j-1个元素和第j个元素的和
            }
            row1=row2;//把当前行赋给上一行
        }
        return row1;
    }
};