【力扣100题】42.杨辉三角

题目描述

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

示例 1：

输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 杨辉三角： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

示例 2：

输入: numRows = 1 输出: [[1]]

提示：

• 1 <= numRows <= 30

解题思路总览

核心原理：杨辉三角的第 i 行第 j 个元素 = 第 i-1 行第 j-1 个元素 + 第 i-1 行第 j 个元素（j 从 1 开始）

模拟构造（推荐）

思路

根据杨辉三角的性质直接模拟：

1. 第 i 行有 i 个元素（行号从 0 开始）
2. 每行的第一个和最后一个元素都是 1
3. 中间的元素triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]

完整代码

classSolution{public:vector<vector<int>>generate(intnumRows){vector<vector<int>>ans;for(inti=0;i<numRows;i++){vector<int>temp;if(i==0){ans.push_back({1});continue;}for(intj=0;j<=i;j++){if(j==0||j==i){temp.push_back(1);// 首尾元素为 1}else{// 中间元素 = 左上方 + 右上方temp.push_back(ans[i-1][j-1]+ans[i-1][j]);}}ans.emplace_back(temp);}returnans;}};

算法流程图

以 numRows = 5 为例：

构建过程： i = 0: temp = [1] ans = [[1]] i = 1: j = 0: j==0 → temp=[1] j = 1: j==i → temp=[1,1] ans = [[1], [1,1]] i = 2: j = 0: j==0 → temp=[1] j = 1: j!=0 && j!=i → temp=[1, 1+1=2] j = 2: j==i → temp=[1,2,1] ans = [[1], [1,1], [1,2,1]] i = 3: j = 0: → temp=[1] j = 1: → temp=[1, 1+2=3] j = 2: → temp=[1,3, 2+1=3] j = 3: → temp=[1,3,3,1] ans = [[1], [1,1], [1,2,1], [1,3,3,1]] i = 4: j = 0: → temp=[1] j = 1: → temp=[1, 1+3=4] j = 2: → temp=[1,4, 3+3=6] j = 3: → temp=[1,4,6, 3+1=4] j = 4: → temp=[1,4,6,4,1] ans = [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]] 最终返回 ans

逐行解析

vector<vector<int>>ans;

• 二维向量，存储杨辉三角的所有行。

for(inti=0;i<numRows;i++){vector<int>temp;if(i==0){ans.push_back({1});continue;}

• 外层循环遍历每一行。
• 第 0 行特殊处理，直接添加[1]。

for(intj=0;j<=i;j++){if(j==0||j==i){temp.push_back(1);// 首尾元素为 1}else{temp.push_back(ans[i-1][j-1]+ans[i-1][j]);}}

• 内层循环遍历当前行的每个元素。
• j == 0 || j == i：首尾元素，直接添加 1。
• 否则：ans[i-1][j-1] + ans[i-1][j]，当前元素等于上一行的左上方 + 右上方。

ans.emplace_back(temp);

• 将当前行添加到结果中。

复杂度分析

优点：思路直接，代码清晰
缺点：无

杨辉三角的性质

杨辉三角中的组合数： C(0,0) = 1 C(1,0)=1, C(1,1)=1 C(2,0)=1, C(2,1)=2, C(2,2)=1 C(3,0)=1, C(3,1)=3, C(3,2)=3, C(3,3)=1 ...

面试追问 FAQ

相关题目

总结