力扣119-杨辉三角II-C++

一、题目

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:

输入: rowIndex = 0
输出: [1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pascals-triangle-ii

二、思路

第一种思路很简单，和118题杨辉三角的思路基本一致，只是最后返回的是杨辉三角的最后一行，二不是整个三，具体思路和代码可以参考我的另一篇博客：https://blog.csdn.net/LJH132465/article/details/123141706

 第二种思路是在第一种思路的基础上进行空间优化，由杨辉三角每个元素的计算公式可以知道，每一行元素的生成都只和上一行元素相关（第一行除外），因此只需要借助一个一维数组 ret 来保存上一行的元素。每计算出一个新的元素，就覆盖上一行中下标相同的元素，但由于该元素需要参与下一个元素的计算，所以该位置的元素在被覆盖之前，需要用一个变量 pre 来保存，而每计算一个元素，pre 中的值也跟着改变，每行最左和最右的元素直接设置为1，不需要经过计算。

当计算完最后一行时，ret 中保存的就是最后一行的元素值，返回即可。

三、代码

class Solution {public: vector getRow(int rowIndex) { vector ret(rowIndex+1); int pre; //记录前一行的列坐标减1的元素 for(int i=0; i<=rowIndex; i++){ //逐行生成元素 for(int j=0; j<=i; j++){ if(j == 0 || j == i){ ret[j] = 1; pre = 1; continue; } int tmp = ret[j] + pre; pre = ret[j]; //保存上一行当前下标的值，用于下一位置的计算 ret[j] = tmp; } } return ret; }};

四、运行结果