20200708-118.pascals-triangle.md

#118.pascals-triangle

题目链接：https://leetcode-cn.com/problems/pascals-triangle/

题目

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

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

示例：

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

解题

思路[1]遍历

• 外圈遍历遍历第几行，内圈遍历遍历第几个
• 每一行的第一位和第i位都是1
• 其他位数是由前一行的相加之和

代码

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

思路[2]递归

• 递归的终止，当求第二行杨辉三角的时候，返回固定[1,1]。
• 递归的处理，拿到前一行的值，然后求出当前的值，将其记录在数组中然后返回出去

代码

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generateFunc = function(numIndex, arr){
  if(numIndex === 1){
    arr[1] = [1, 1]
    return [1, 1]
  }
  let prev = generateFunc(numIndex - 1, arr);
  let next = [1];
  for(let i = 0; i < prev.length - 1; i++){
    next[i + 1] = prev[i] + prev[i + 1]
  }
  next.push(1);
  arr[numIndex] = next;
  return next
}

var generate = function(numRows) {
  if(numRows === 0){
    return []
  }
  if(numRows === 1){
    return [[1]]
  }
  var arr = [[1]];
  generateFunc(numRows - 1, arr);
  return arr
};

思考

• 简单的遍历问题
• 这道题目用递归略显麻烦