1. 118. 杨辉三角 简单

1. 题目详情

给定一个非负整数 numRows，生成「杨辉三角」的前 $numRows$ 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

1. 原题链接

LeetCode 118. 杨辉三角 简单

2. 题目要求

示例 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$

3. 基础框架

● Cpp代码框架

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
    }
};

2. 解题思路

1. 思路分析

$(1)$ 找到杨辉三角的规则：

1. 最左边位置上的数都是1；
2. 对角线位置上的数都是1；
3. 普通位置上的数 = 上一行且同一列位置的数 + 上一行且前一列位置的数；
4. 第n行的元素个数是n个；

$(2)$ 进行两层循环，外层循环对应生成n行序列；内层循环对应本次生成的序列，生成规则已知；

2. 时间复杂度

$O(N^2)$
两层循环，共生成$n$层，第$i$层生成的元素是$i$个，其中 $1<=i<=n$;
$1+2+3+...+i+...n=(n\ast (n+1))/2$

3. 代码实现

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        for(int i = 0; i < numRows; ++i){
            vector<int> tmp(i + 1);
            for(int j = 0; j <= i; ++j){
                if(j == 0 || j == i){
                    tmp[j] = 1;
                }
                else{
                    tmp[j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
            vv.push_back(tmp);
        }
        return vv;
    }
};

---

$The$ $End$