119.杨辉三角II

链接：119.杨辉三角II
难度：Easy
标签：数组、动态规划
简介：给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

题解 1 - typescript

• 编辑时间：2021-02-12
• 执行用时：88ms
• 内存消耗：40.5MB
• 编程语言：typescript
• 解法介绍：优化题解 1。

const cache = [[1],[1,1],...]
      function getRow(rowIndex: number): number[] {
        return cache[rowIndex];
      }

题解 2 - typescript

• 编辑时间：2021-02-12
• 执行用时：88ms
• 内存消耗：40.5MB
• 编程语言：typescript
• 解法介绍：遍历所有值进行储存。

function getRow(rowIndex: number): number[] {
  const cache: number[][] = [[1], [1, 1]];
  for (let i = 2; i <= 33; i++) {
    const arr = [1];
    const prev = cache[i - 1];
    for (let j = 0, l = prev.length; j < l - 1; j++) {
      arr.push(prev[j] + prev[j + 1]);
    }
    arr.push(1);
    cache.push(arr);
  }
  return cache[rowIndex];
}

题解 3 - typescript

• 编辑时间：2021-02-12
• 执行用时：84ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：利用 1 个数组进行覆盖。

function getRow(rowIndex: number): number[] {
  if (rowIndex === 0) return [1];
  const arr = [1, 1];
  if (rowIndex === 1) return arr;
  for (let i = 2; i <= rowIndex; i++) {
    for (let j = 0, l = arr.length; j < l - 1; j++) {
      arr[j] = arr[j] + arr[j + 1];
    }
    arr.unshift(1);
    arr.splice(arr.length - 1, 1, 1);
  }
  return arr;
}

题解 4 - typescript

• 编辑时间：2021-09-04
• 执行用时：88ms
• 内存消耗：39.2MB
• 编程语言：typescript
• 解法介绍：动态规划。

function getRow(rowIndex: number): number[] {
  const list: number[][] = new Array(2).fill(0).map(_ => []);
  list[0].push(1);
  list[1].push(1, 1);
  for (let i = 2; i <= rowIndex; i++) {
    const idx = i % 2;
    const prevIdx = idx ^ 1;
    list[idx].length = 0;
    list[idx].push(1);
    for (let j = 1; j <= i - 1; j++) list[idx].push(list[prevIdx][j] + list[prevIdx][j - 1]);
    list[idx].push(1);
  }
  return list[rowIndex % 2];
}