什么是“杨辉三角”，想必大家并不陌生~~
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
本篇带来两道“杨辉三角”题，小冲一波~~
题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，以上便是本篇分享~
