119. Pascal's Triangle II——array
题目分析:因为只能用k的空间,所以考虑递归。但是递归超过了时间,所以考虑特性,每个值是前liang两个值得和,倒序计算。
class Solution(object): def kthSmallest(self, rowIndex): # res = [0 for _ in range(rowIndex+1)] # res[0] = 1 # res[-1] = 1 # for i in range(1, (rowIndex+1)//2+(rowIndex+1)%2): # res[i] = self.s(rowIndex, i) # for j in range((rowIndex+1)//2+(rowIndex+1)%2, rowIndex+1): # res[j] = res[rowIndex-j] # return res # # def s(self, row, colum): # if colum == 0 or row == colum: # return 1 # else: # return self.s(row-1, colum-1)+self.s(row-1, colum) result = [1] if rowIndex == 0: return result result.append(1) if rowIndex == 1: return result for i in range(2, rowIndex + 1): result.append(1) n = len(result) # 逆序的原因是防止前面变了影响后面 for j in range(n - 2, 0, -1): if (j >= n // 2): result[j] = result[j] + result[j - 1] else: result[j] = result[n - 1 - j] return result