算法之“杨辉三角”题解

2022 年 8 月 24 日
广东
本文字数：1020 字
阅读完需：约 3 分钟

什么是“杨辉三角”，想必大家并不陌生~~

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

本篇带来两道“杨辉三角”题，小冲一波~~

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

示例 1:
输入: numRows = 5输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1输出: [[1]]

复制代码

解题思路

思路简单，把握杨辉三角特点：第 0 行 1 个元素，第 1 行 2 个元素，第 2 行 3 个元素；依此例推

下一行元素和上一行元素的关系是（0 计数开始）以第 2 行第 1 列的元素 2 举例，等于上面 1+1（上一行同一列加上一行前一列元素）

JavaScript 实现

/** * @param {number} numRows * @return {number[][]} */var generate = function (numRows) {  const res = [];  /**   let egg=[    [1],     [1, 1],     [1, 2, 1],     [1, 3, 3, 1],     [1, 4, 6, 4, 1]  ]  */  for (let i = 0; i < numRows; i++) {    // 看上面的例子数组，第0行1个元素，第1行2个元素，第2行3个元素....    const row = new Array(i + 1).fill(1);    // 这里j从1开始到row.length-2结束  是因为每一行的第一个和最后一个其实是不需要算的，因为已经默认为1了，只有中间的才需要算    for (let j = 1; j < row.length - 1; j++) {      // 看上面的例子数组，以（0计数开始）2行1列的元素2举例，等于上面1+1（上一行同一列及上一行前一列元素）      row[j] = res[i - 1][j] + res[i - 1][j - 1];    }    res.push(row);  }  return res;};

复制代码

题 2：给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex **行。

示例 1:
输入: rowIndex = 3输出: [1,3,3,1]示例 2:
输入: rowIndex = 0输出: [1]示例 3:
输入: rowIndex = 1输出: [1,1]

复制代码

解题思路

巧用递归：

i 表示层级（rowIndex），第 i 层存在 i+1 个元素
j 表示当前层级的元素的位置
f[i][j] = (f[i - 1][j - 1] || 0) + (f[i - 1][j] || 0)

/** * @param {number} rowIndex * @return {number[]} */const getRow = function(rowIndex) {  /**   * 递归方程：f[i][j] = (f[i - 1][j - 1] || 0) + (f[i - 1][j] || 0)   */
  if (rowIndex === 0) {    return [1];  }
  const arr = getRow(rowIndex - 1);
  return Array.from({length: rowIndex + 1})    .map((_, index) => (arr[index - 1] || 0) + (arr[index] || 0));};