写点什么

算法之“杨辉三角”题解

作者:掘金安东尼
  • 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));};
复制代码



OK,以上便是本篇分享~


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

发布于: 刚刚阅读数: 5
用户头像

安东尼陪你度过漫长编程岁月~ 2022.07.14 加入

社会我瓜哥,人狠话不多😎 微信 anthony1453,加我交个朋友😎 正联合【机械工业出版社】出版《程序员成长手册》,敬请期待😎 真正的大师,永远怀着一颗学徒的心(易)😎

评论

发布
暂无评论
算法之“杨辉三角”题解_算法_掘金安东尼_InfoQ写作社区