leetcode 【 Pascal's Triangle II 】python 实现

题目：

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?

代码：oj测试通过 Runtime: 48 ms

 class Solution:

     # @return a list of integers

     def getRow(self, rowIndex):

         if rowIndex == 0:

             return [1]

         if rowIndex == 1:

             return [1,1]

         pascal = [1,1]

         for i in range(1,rowIndex):

             for j in range(len(pascal)-1):

                 pascal[j] = pascal[j] + pascal[j+1]

             pascal.insert(0,1)

         return pascal

思路：

先把special case单列出来

每轮迭代从前向后更新数组的每个元素

最后再在第一位补上一个1

另，网上有很多题解是每轮从后往前遍历，这样的效率似乎更高一些。

后续又把遍历的顺序改为由后向前，结果如下

oj测试通过 Runtime: 37 ms

代码：

 class Solution:

     # @return a list of integers

     def getRow(self, rowIndex):

         if rowIndex == 0:

             return [1]

         if rowIndex == 1:

             return [1,1]

         pascal = [1,1]

         # from start to end

         #for i in range(1,rowIndex):

         #    for j in range(len(pascal)-1):

         #        pascal[j] = pascal[j] + pascal[j+1]

         #    pascal.insert(0,1)

         # from end to start

         for i in range(1, rowIndex):

             for j in range(len(pascal)-1, 0, -1):

                 pascal[j] = pascal[j] + pascal[j-1]

             pascal.insert(len(pascal),1)

         return pascal

确实从后向前遍历比从前向后遍历要快很多。

小白对Python原理不懂，分析可能的原因如下：

1. 在数据起始位置insert，需要改变数组后续所有元素在内存中的位置，因此耗时长？

2. 在数组末尾insert，不需要改变数组之前所有元素在内存中的位置，只补上最后一个新增元素的位置就行了，因而速度快？

巴特西

leetcode 【 Pascal's Triangle II 】python 实现

最新文章

热门文章