跳至主要內容

119. 杨辉三角 II


119. 杨辉三角 II

🟢   🔖  数组 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal 's triangle.

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

Example 1:

Input: rowIndex = 3

Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0

Output: [1]

Example 3:

Input: rowIndex = 1

Output: [1,1]

Constraints:

  • 0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

题目大意

给定一个非负索引 rowIndex,返回「杨辉三角」的第 rowIndex 行。

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

示例 1:

输入: rowIndex = 3

输出: [1,3,3,1]

示例 2:

输入: rowIndex = 0

输出: [1]

示例 3:

输入: rowIndex = 1

输出: [1,1]

提示:

  • 0 <= rowIndex <= 33

进阶:

你可以优化你的算法到 O(rowIndex) 空间复杂度吗?

解题思路

杨辉三角的性质:

  • 杨辉三角第 i 行的第 j 个元素可以通过 前一行 的第 j-1 和第 j 个元素相加得到。
    • arr[j] = arr[j] + arr[j-1]
  • 每一行的第一个和最后一个元素永远是 1
  • k 行有 k+1 个元素,索引从 0 开始。
  1. 初始化数组 创建一个长度为 rowIndex + 1 的数组 arr,并将所有元素初始化为 1(因为每行的两端元素始终为 1)。

  2. 遍历行数 从第 2 行开始(i = 2),因为第 0 行和第 1 行的元素都是 1

  3. 动态更新当前行 从索引 i - 11,逐步更新数组元素。从右向左更新数组,避免当前元素被覆盖,影响后续计算。

  4. 返回结果 遍历完成后,arr 就是第 rowIndex 行的结果。

复杂度分析

  • 时间复杂度O(rowIndex^2),需要两层遍历。
  • 空间复杂度O(rowIndex),使用了一个数组 arr 来保存计算过程和结果。

代码

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
	// 初始化一个长度为 rowIndex + 1 的数组,所有元素为 1
	let arr = new Array(rowIndex + 1).fill(1);

	// 从第 2 行开始遍历,计算每一行的中间元素
	for (let i = 2; i <= rowIndex; i++) {
		// 从右向左更新数组,避免当前元素被覆盖
		for (let j = i - 1; j > 0; j--) {
			arr[j] += arr[j - 1];
		}
	}

	// 返回第 rowIndex 行
	return arr;
};

相关题目

题号标题题解标签难度力扣
118杨辉三角[✓]数组 动态规划🟢🀄️open in new window 🔗open in new window
2221数组的三角和数组 数学 组合数学 1+🟠🀄️open in new window 🔗open in new window