118. 杨辉三角

🟢   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

Given an integer numRows, return the first numRows of Pascal 's triangle.

In Pascal 's triangle, each number is the sum of the two numbers directly above it as shown:

     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Example 1:

Input: numRows = 5

Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1

Output: [[1]]

Constraints:

• 1 <= numRows <= 30

题目大意

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

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

     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

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

解题思路

1. 构建基础结构：初始化一个大小为 n 的数组，来存储每一行的元素。
2. 逐行生成：第 i 行的第 j 个元素为上一行的第 j-1 和第 j 个元素之和，除了第一个和最后一个元素是 1。
3. 返回结果：构造完所有的行后，将完整的数组返回。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是行数。因为需要遍历每一行并更新每个元素的值。
• 空间复杂度：O(n^2)，用于存储整个 Pascal 三角形。

代码

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
	let res = [];

	// 生成每一行
	for (let i = 0; i < numRows; i++) {
		// 每一行的长度为i+1，并初始化为1
		let row = new Array(i + 1).fill(1);

		// 更新除第一个和最后一个元素之外的元素
		for (let j = 1; j < i; j++) {
			row[j] = res[i - 1][j - 1] + res[i - 1][j];
		}

		// 将当前行加入结果
		res.push(row);
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
119	杨辉三角 II		数组 动态规划