119. Pascal's Triangle II

时间：2017-06-12 21:29:19 阅读：223 评论：0 收藏：0 [点我收藏+]

https://leetcode.com/problems/pascals-triangle-ii/#/solutions

Given an index k, return the kth row of the Pascal‘s triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Sol:

Elegent!

Let i be the ith row. Alawys append 1 to the end of the row before moving on the the next row.

For each line, the jth element equals to the sum of jth element in the previous row and the (j-1)th element in the previous row.

We do not need to create a tuple to keep track of (i th row, j th element). Before value of j th element in ith row -- res[j] -- is updated, variable res[j] stores the value of j th element in (i-1) th row. And the res[j-1] stores the value of (j-1) th element in (i-1) th row.

Thus, we simply add them together to get the j th element in i th row.

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        
        # O(k) space, O(n^2) time
        
        res = []
        for i in range(rowIndex+1):
            res.append(1)
            
            #range(start,end,step)
            for j in range(i,0,-1):
                if j == i:
                    res[j] = 1
                else:
                    res[j] += res[j-1]
        return res

Note:

1 When the index j th element j equals to the row numer i, it means the j th element is the last element in the row.

119. Pascal's Triangle II

原文：http://www.cnblogs.com/prmlab/p/6995055.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)