1. 题目
  2. 解题思路

118 Pascal's Triangle

leetcode

题目

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

PascalTriangleAnimated2.gif

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

Example:

1
2
3
4
5
6
7
8
9
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

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

解题思路

据观察可知:
1 行号即所在行元素的个数, 例如第 2 行有 2 个值,第 3 行有 3 个值.
2 行首和行尾的值均为 1.
3第 n 行的第 i 个元素值等于第 n - 1 行的第 i - 1 个值和第 i 个值相加.

从上往下逐行计算, 下一行直接取上一行的对应值相加即可.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function generate(numRows) {
  if (numRows === 0) {
    return [];
  }
  const triangle = [];
  for (let i = 1; i <= numRows; i++) {
    // 当前行
    const row = [];
    for (let j = 1; j <= i; j++) {
      // 行首和行尾的值均为 1
      if (j === 1 || j === i) {
        row.push(1);
      } else {
        // 上获取一行的值
        const previousRow = triangle[i - 2];
        // row[i] 等于上一行的 row[i - 1] + row[i]
        row.push(previousRow[j - 2] + previousRow[j - 1]);
      }
    }
    triangle.push(row);
  }
  return triangle;
}