【LeetCode】118. 杨辉三角

题目链接

Python3

直觉解法：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1]]
        for _ in range(numRows-1):
            temp1 = []
            temp2 = [0] + ans[-1] + [0]
            for i in range(len(temp2)-1) :
                temp1.append(temp2[i]+temp2[i+1])
            ans.append(temp1)

        return ans 
1
2
3
4
5
6
7
8
9
10
11

版本1

以下的理论介绍 可以说和 本题的 代码实现 毫无关系。

这个版本 需要注意 列表的边界

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = []
        for i in range(numRows):
            row = []  # 第 i 行
            for j in range(i+1) : # 第 i 行 【0开始】 有 i+1 项
                if j == 0 or j == i: # 为 1 的位置下标 和 行下标 一致 
                    row.append(1) 
                else:
                    row.append(ans[i-1][j]+ans[i-1][j-1])
            ans.append(row)

        return ans 
1
2
3
4
5
6
7
8
9
10
11
12
13

⭐ 版本2

思路： 前一行 两端 补0 模拟。 结合 动图 理解

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1]]
        for _ in range(numRows-1):  # 因为 直接对前一行ans[-1]操作,这里要注意循环次数 第0次循环  获得了 第2行。因此只到 第 numRows-2 次循环
            row = []  # 存储 每行的数 
            temp = [0] + ans[-1] + [0]
            for i in range(len(temp)-1) :
                row.append(temp[i] + temp[i+1])
            ans.append(row)

        return ans 
1
2
3
4
5
6
7
8
9
10
11

C++

⭐ 版本

题目 说明至少 一行，可以跳过 第一行的处理

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;  // 这里没有限制长度
        ans.push_back(vector<int>(1, 1));   //  第 1 行
        for (int i = 1; i <= numRows-1; ++i){
            ans.push_back(vector<int>(i+1));  // C++ 不能随便 加元素，要提前说明
            ans[i][0] = ans[i][i] = 1;
            for(int j = 1; j <= i-1; ++j){
                ans[i][j] = ans[i-1][j] + ans[i-1][j-1];
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

官方版本

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);
        for (int i = 0; i <= numRows-1; ++i){
            ans[i].resize(i+1);  // C++ 不能随便 加长，要提前说明
            ans[i][0] = ans[i][i] = 1;
            for(int j = 1; j <= i-1; ++j){
                ans[i][j] = ans[i-1][j] + ans[i-1][j-1];
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14