118. 杨辉三角｜刷题打卡

闲时要有吃紧的心思，忙时要有悠闲的趣味

• 题目描述
• 思路分析
• AC 代码
• 总结

题目描述

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

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

示例:

输入: 5
输出: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

思路分析

思路一：动态规划(双层循环)

 在杨辉三角中，每个数是它左上方和右上方的数的和，所以对于存储杨辉三角的二维数组 A 来说，除去边界情形，有如下关系成立：

 所以我们可以用双层循环迭代实现。

思路二：递归

 总而言之就是抓住三点：

1. 找整个递归的终止条件
2. 找返回值
3. 一次递归需要如何操作

找整个递归的终止条件

 分析一下题目，递归到 numRows = 0 时或者 numRows = 1 时都可以终止，因为第一行比较特殊，只有一个 1,所以我们可以将其当成整个递归的终止条件，当 numRows = 1 时，我们就可以终止递归向下返回值了。

找返回值

 找返回值，也需要分析下，题目要求的是整个杨辉三角的所有数，那最后递归得到的应该就是 List<List> (题目给定)，也就是每递归完一层，我们就更新完 List 并返回即可，最后递归完成就是我们要的答案。

一次递归需要如何操作

 递归的难点就在这里，很多童靴刚学递归时，总是在这里搞晕，其实我们只需要关注一次递归即可，因为每一层递归的过程都是一样的，我们只需要找到最上层的递归的规律，就可以了。

AC 代码

题解一：双层循环

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  let result = []
  let rowArr = []
  if (numRows <= 0) {
    return result
  }
  for (let i = 0; i < numRows; i++) {
    rowArr = []
    for (let j = 0; j <= i; j++) {
      if (j > 0 && j < i) {
        rowArr.push(result[i - 1][j - 1] + result[i - 1][j])
      } else {
        rowArr.push(1)
      }
    }
    result.push(rowArr)
  }
  return result
}

题解二：递归

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  //存储要返回的杨辉三角
  let dg = []
  //若0行，则返回空
  if (numRows === 0) return dg
  //递归出口，如果是1行，返回
  if (numRows === 1) {
    dg = [[1]]
    return dg
  }
  //递归，注意返回值！！！这是第二步
  dg = generate(numRows - 1)
  //一级递归要做啥，我们可以看第二行到第三行需要做啥
  //首先是要申请一个list来存储第三行，然后通过第二行得到第三行
  //第三行的首尾为1是确定了的，然后就是中间的数如何得到
  //通过观察很容易拿到for循环里面的式子
  //最后别忘了返回值！！！
  let prev = dg[numRows - 2]
  let row = [1]
  for (let j = 1; j < numRows - 1; j++) {
    row.push(prev[j - 1] + prev[j])
  }
  row.push(1)
  dg.push(row)
  return dg
}

附上大佬另一个递归写法

• 作者：huang-shan-he

/**
 * @param {number} numRows
 * @return {number[][]}
 */
const generate = function(numRows) {
  if (numRows === 0) return []
  if (numRows === 1) return [[1]]

  const ans = generate(numRows - 1)
  const prev = ans[ans.length - 1]
  const item = []
  for (let i = 0; i < prev.length + 1; i++) {
    item[i] = (prev[i - 1] || 0) + (prev[i] || 0)
  }
  return ans.concat([item])
}

总结

 三月你好，春暖花开。加油！

 本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情

后记：Hello 小伙伴们，如果觉得本文还不错，记得点个赞或者给个 star，你们的赞和 star 是我编写更多更丰富文章的动力！GitHub 地址

文档协议