Pascals Triangle

118. 杨辉三角

分析

杨辉三角的特点是：

第 i 行有 i 个元素
每行的首尾元素为 1
中间的每个元素为其上一行相邻两个元素的和

公式：f[i][j] = f[i-1][j-1] + f[i-1][j]

初始化数据结构：
- 使用一个二维数组 f 存储结果
逐行构造杨辉三角：
- 第 i 行初始化一个大小为 i + 1 的数组
- 设置首尾元素为 1
- 遍历中间位置，根据公式计算值并填充
返回结果：
- 将每一行加入结果数组并返

时间复杂度

外层循环运行 n 次；
内层循环最多运行 n - 2 次

总体复杂度为：O(1 + 2 + 3 + ... + n) = O(n^2)

空间复杂度

空间复杂度为 O(n^2)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution
{
public:
    vector<vector<int>> generate(int numRows)
    {
        std::vector<std::vector<int>> f;
        for (int i = 0; i < numRows; ++ i)  // 遍历每一行
        {
            std::vector<int> line(i + 1);  // 初始化当前行，长度为 i+1
            line[0] = line[i] = 1;         // 每行的首尾元素为 1

            for (int j = 1; j < i; ++ j)   // 中间元素由上一行相邻元素之和计算得出
                line[j] = f[i - 1][j - 1] + f[i - 1][j];

            f.push_back(line);             // 将当前行加入结果数组
        }
        return f;
    }
};