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行的数得到的,因此循环构造即可。
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]
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句