0119._pascal_triangle_II.md

Navigation

• Navigation
• Links:
• Solution 1
• Solution 2
• Solution 3
• 总结

Links:

1. https://leetcode.com/problems/pascals-triangle-ii/
2. https://leetcode-cn.com/problems/pascals-triangle-ii/

Solution 1

class Solution:
    def getRow(self, rowIndex):
        # j行的数据, 应该由j - 1行的数据计算出来.
        # 假设j - 1行为[1,3,3,1], 那么我们前面插入一个0(j行的数据会比j-1行多一个),
        # 然后执行相加[0+1,1+3,3+3,3+1,1] = [1,4,6,4,1], 最后一个1保留即可.
        res = [1]

        for i in range(1, rowIndex + 1):
            res.insert(0, 0)
            # 因为i行的数据长度为i+1, 所以j+1不会越界, 并且最后一个1不会被修改.
            for j in range(i):
                res[j] = res[j] + res[j + 1]
                
        return res

Solution 2

和118最后一个Solution非常相似。118返回的是整个traingle，而这里只返回traingle里面的一个row

class Solution:
    def getRow(self, rowIndex):
        triangle = []

        for i in range(rowIndex+1):
            row = [None for _ in range(i+1)]
            row[0], row[-1] = 1, 1

            for j in range(1, len(row)-1):
                row[j] = triangle[i-1][j-1] + triangle[i-1][j]

            triangle.append(row)

        return row

Solution 3

每计算一行，两边插1。只计算中间的。而Solution1 计算整行。

class Solution(object):
    def getRow(self, rowIndex):
        res = [1]

        for i in range(rowIndex):
            res = [1] + [res[x]+res[x+1] for x in range(len(res)-1)] + [1]
            
        return res

总结

Solution1和3的空间复杂度为O(rowIndex)。Solution2是O(rowIndex^2)。