解题过程

:::info 题目链接
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和
image.png :::

  1. /**
  2.  * @link https://leetcode.cn/problems/pascals-triangle-ii/
  3.  * @title 119. 杨辉三角 II
  4.  * @description 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
  5.  * 在「杨辉三角」中，每个数是它左上方和右上方的数的和
  6.  * @param {number} rowIndex
  7.  * @return {number[]}
  8.  */
  9. // 解法一：
  10. // 思路：最简单的思路就是根据做过的118题的代码改一下，最终数组返回最后一个元素就可以了，注意之前参数是行数，现在是索引行，也就是相对之前遍历一维数组时临界值要+1
  11. // var getRow = function (rowIndex) {
  12. //   const resultNums = []
  14. //   for (let i = 0; i <= rowIndex; i++) {
  15. //     const nums = []
  16. //     for (let j = 0; j <= i; j++) {
  17. //       // 获取上一行的值
  18. //       const preNums = i === 0 ? [] : resultNums[i - 1]
  19. //       // 当前元素索引值与上一行数组元素索引值关系相加得出
  20. //       const pre = j - 1 >= 0 ? preNums[j - 1] : 0
  21. //       const cur = j < preNums.length ? preNums[j] : 0
  22. //       const currNum = pre === 0 && cur === 0 ? 1 : pre + cur
  23. //       nums.push(currNum)
  24. //     }
  26. //     resultNums.push(nums)
  27. //   }
  29. //   return resultNums.pop()
  30. // }
  32. // 解法二：
  33. // 思路：递归方式，可以通过计算当前值为计算上一行的值推算出来进行累加，其实就是通过改上面的代码从for循环遍历改为递归
  34. // 缺点：像斐波那契数列，数值越大计算时间越久，官方测试用例rowIndex=24的时候就已经超出最大时间限制了
  35. // 所以该方法虽然可行，但并不是最优解，还可以再优化
  36. // 输入值24已经超出时间限制了
  37. // var getRow = function (rowIndex) {
  38. //   const nums = []
  39. //   const calc = (row, index) => {
  40. //     console.log('row', row, index)
  41. //     if (row === 0) {
  42. //       return index < 0 || index > 0 ? 0 : 1
  43. //     } else {
  44. //       return calc(row - 1, index - 1) + calc(row - 1, index)
  45. //     }
  46. //   }
  48. //   for (let i = 0; i <= rowIndex; i++) {
  49. //     const j = calc(rowIndex, i)
  50. //     console.log('j', j)
  51. //     nums.push(j)
  52. //   }
  54. //   return nums
  55. // }
  57. // 优化递归版
  58. // 输入值11已经超出时间限制了
  59. // var getRow = function (rowIndex) {
  60. //   const calc = (row, index) => {
  61. //     const nums = []
  62. //     // 当前行开头为1
  63. //     nums.push(1)
  65. //     if (row === 0) { return nums }
  67. //     if (row > 1) {
  68. //       for (let i = 1; i <= row - 1; i++) {
  69. //         const j = calc(row - 1)[i - 1] + calc(row - 1)[i]
  70. //         nums.push(j)
  71. //       }
  72. //     }
  74. //     // 当前行结尾为1
  75. //     nums.push(1)
  76. //     return nums
  77. //   }
  79. //   return calc(rowIndex)
  80. // }
  82. // 解法三：
  83. // 思路：网上看到很不错的解题方案，其实就是我上面想破天也没想到的递归数组版
  84. var getRow = function (rowIndex) {
  85.   const res = []
  87.   for(let i = 1; i <= rowIndex + 1; i++) {
  88.     // 当前行数的数组元素初始值都为1
  89.     res[i - 1] = 1
  90.     // 重置数组首尾之外元素位置的值
  91.     for (let j = i - 2; j > 0; j--) {
  92.       // 这一步理解起来确实有一定的难度，但也很巧妙利用当前值与上一轮计算的值关系
  93.       res[j] = res[j - 1] + res[j]
  94.     }
  95.   }
  97.   return res
  98. }
  100. const result = getRow(3)
  101. // const result = getRow(0)
  102. // const result = getRow(1)
  103. // const result = getRow(10)
  104. // const result = getRow(20)
  105. console.log(result)

解题感受

跟昨天做的118题一样的题目，只不过换了返回值，直接根据昨天的改就很简单做出来，尝试了其他解法，首先想到了递归，但是递归写的两版跟斐波那契数列一样，导致传参数值大的时候执行时间很长，不算好，理解思路即可，第三种解法是参考别人题解的，感觉还不错的解题思路，就是我一直在想的数组递归法，但是时间有限下没想出来，挺不错的解题思路，简单

参考题解

https://leetcode.cn/problems/pascals-triangle-ii/solution/javascriptban-jie-ti-si-lu-by-ityou-o-4jqr/