日拱算法：解两道“杨辉三角”题

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

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

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

题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));
};

OK，以上便是本篇分享~

我是掘金安东尼，输出暴露输入，技术洞见生活，再会~~