LeetCode 118. 杨辉三角(及119)

118. 杨辉三角

题目：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
链接 https://leetcode.cn/problems/pascals-triangle/

个人思路

1. 直接循环，按定义左上方和右上方的数的和计算下一行相应位置的值。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 1:
            return [[1]]
        if numRows == 2:
            return [[1],[1,1]]
        ans = [[1],[1,1]]
        for i in range(3,numRows+1):       
            temp = [1] * i    
            for j in range(1,i-1):
                temp[j] = ans[-1][j-1] + ans[-1][j]
            ans.append(temp)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

官方写法：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ret = list()
        for i in range(numRows):
            row = list()
            for j in range(0, i + 1):
                if j == 0 or j == i:
                    row.append(1)
                else:
                    row.append(ret[i - 1][j] + ret[i - 1][j - 1])
            ret.append(row)
        return ret
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析
时间复杂度：O(numRows ^ 2 )。
空间复杂度：O(1)。不考虑返回值的空间占用。

其他思路

1. 观察一下规律，发现当前一行只比上一行多了一个元素，最最关键的一点：本行元素等于上一行元素往后错一位再逐个相加；因此我们只要对最后一行单独处理：最后一行首、尾分别添加一个零然后对应位置求和就可以得到新的一行

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0: return []
        res = [[1]]
        while len(res) < numRows:
            newRow = [a+b for a, b in zip([0]+res[-1], res[-1]+[0])]
            res.append(newRow)      
        return res
1
2
3
4
5
6
7
8

作者：A_C_W_lu_cheng
链接：https://leetcode.cn/problems/pascals-triangle/solution/qu-qiao-jie-fa-cuo-yi-wei-zai-zhu-ge-xiang-jia-28m/

118. 杨辉三角II

题目：给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。行数从0开始。
https://leetcode.cn/problems/pascals-triangle-ii/
进阶：你可以优化你的算法到 O(rowIndex) 空间复杂度吗？

个人思路

1. 直接按上面的修改一下，返回最后一个元素即可，当然，因为是返回第 rowIndex 行，我们也不用保留全部元素，修改代码如下:

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]
        if rowIndex == 1:
            return [1,1]
        ans = [1,1]
        for i in range(3,rowIndex+2):       
            temp = [1] * i    
            for j in range(1,i-1):
                temp[j] = ans[j-1] + ans[j]
            ans = temp
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<Integer>();
        row.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
            row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));
        }
        return row;
    }
}
1
2
3
4
5
6
7
8
9
10