leetCode#119. Pascal's Triangle II

本文主要是介绍leetCode#119. Pascal's Triangle II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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?

Code

class Solution(object):def getRow(self, rowIndex):""":type rowIndex: int:rtype: List[int]"""res = []for i in range(0, rowIndex + 1):res += [self.calVal(i, rowIndex)]return resdef calVal(self, k, n):numerator, denominator = 1, 1#分子，分母for i in range(0, k):numerator *= nn -= 1while k > 1:denominator *= kk -= 1return numerator // denominator

我采取的算法是直接套用公式， C(k-1, n-1)。看了下别人的算法，是一层层算的，我还没理解过来

class Solution:# @return a list of integersdef getRow(self, rowIndex):array = [1]*(rowIndex+1)for i in range(1,rowIndex+1):for j in range(i-1,0,-1):array[j] += array[j-1]return array

很简洁，但是还没理解，有空理解理解吧

这篇关于leetCode#119. Pascal's Triangle II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---