Q119 Pascal's Triangle II

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?

解题思路：

题目参考见 Q118 Pascal's Triangle

要求空间复杂度为O(k)，所以构造一半。最后根据奇、偶行构造完整的返回值。思路一样，即第k行的数是由第k-1行的数得到的，因此循环构造即可。

Python实现：

class Solution:
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex < 0:
            return []
        rlist = []
        rlist.append(1)
        i = 1
        while i <= rowIndex:
            j = len(rlist) - 1
            while j > 0:   # 构造下一个列表元素
                rlist[j] = rlist[j] + rlist[j-1]
                j -= 1
            if i % 2 == 1:   # 如果是奇数行，需要加一个元素
                rlist.append(rlist[-1])
            i += 1
        # 构造另一半
        if rowIndex % 2 == 1:   # 如将 [1,3,3] 变成 [1,3,3,1]
            rlist.extend(rlist[-3::-1])
        else:    # 如将 [1,4,6] 变成 [1,4,6,4,1]
            rlist.extend(rlist[-2::-1])  
        return rlist

a = 3
b = Solution()
print(b.getRow(a))  # [1,3,3,1]