【刷题打卡】118. 杨辉三角-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述：

118. 杨辉三角 – 力扣（LeetCode） (leetcode-cn.com)

给定一个非负整数 numRows， 生成「杨辉三角」的前 numRows 行。

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

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
复制代码

示例 2:

输入: numRows = 1
输出: [[1]]
复制代码

提示:

1 <= numRows <= 30

二、思路分析：

考察第i行的填充方法.

第一个数固定是1,

第二个数开始, 每个位置j的值 = 上一行j-1位置的值 + 上一行j位置的值

除去最后一个数是1外,其它都符合这个公式.

例如:

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
复制代码

考虑最后一行,

下标1处的值 4 = 上一行下标0处的值 + 上一行下标1处的值 = 1 + 3.

下标1处的值 6 = 上一行下标1处的值 + 上一行下标2处的值 = 3 + 3.

下标1处的值 4 = 上一行下标2处的值 + 上一行下标3处的值 = 3 + 1.

三、AC 代码：

    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        for(int i=0;i<numRows; ++i){
            ans.push_back(vector<int>());
            vector<int>& cols=ans[i];
            cols.push_back(1);
            for(int j=1;j<i;++j) cols.push_back(ans[i-1][j-1] + ans[i-1][j]);
            if(cols.size() < i+1) cols.push_back(1);
        }
        
        return ans;
    }
复制代码