118.杨辉三角

链接：118.杨辉三角
难度：Easy
标签：数组、动态规划
简介：给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

题解 1 - typescript

• 编辑时间：2020-12-06
• 执行用时：88ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：迭代遍历。

function generate(numRows: number): number[][] {
  if (numRows === 0) return [];
  const ans: number[][] = [[1]];
  for (let i = 2; i <= numRows; i++) {
    const last = ans[ans.length - 1];
    const arr = [];
    for (let j = 0, l = last.length - 1; j < l; j++) {
      arr.push(last[j] + last[j + 1]);
    }
    arr.unshift(1);
    arr.push(1);
    ans.push(arr);
  }
  return ans;
}

题解 2 - cpp

• 编辑时间：2021-12-21
• 内存消耗：6.3MB
• 编程语言：cpp
• 解法介绍：从后往前遍历。

class Solution {
   public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows, vector<int>());
        ans[0].push_back(1);
        for (int i = 1; i < numRows; i++) {
            ans[i].push_back(1);
            for (int j = 1; j < i; j++) {
                ans[i].push_back(ans[i - 1][j] + ans[i - 1][j - 1]);
            }
            ans[i].push_back(1);
        }
        return ans;
    }
};