首页 > 代码库 > leetcode 【 Pascal's Triangle II 】python 实现
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
1 class Solution: 2 # @return a list of integers 3 def getRow(self, rowIndex): 4 if rowIndex == 0: 5 return [1] 6 if rowIndex == 1: 7 return [1,1] 8 pascal = [1,1] 9 for i in range(1,rowIndex):10 for j in range(len(pascal)-1):11 pascal[j] = pascal[j] + pascal[j+1]12 pascal.insert(0,1)13 return pascal
思路：
先把special case单列出来
每轮迭代从前向后更新数组的每个元素
最后再在第一位补上一个1
另，网上有很多题解是每轮从后往前遍历，这样的效率似乎更高一些。
后续又把遍历的顺序改为由后向前，结果如下
oj测试通过 Runtime: 37 ms
代码：
1 class Solution: 2 # @return a list of integers 3 def getRow(self, rowIndex): 4 if rowIndex == 0: 5 return [1] 6 if rowIndex == 1: 7 return [1,1] 8 pascal = [1,1] 9 10 # from start to end11 #for i in range(1,rowIndex):12 # for j in range(len(pascal)-1):13 # pascal[j] = pascal[j] + pascal[j+1]14 # pascal.insert(0,1)15 16 # from end to start17 for i in range(1, rowIndex):18 for j in range(len(pascal)-1, 0, -1):19 pascal[j] = pascal[j] + pascal[j-1]20 pascal.insert(len(pascal),1)21 return pascal
确实从后向前遍历比从前向后遍历要快很多。
小白对Python原理不懂，分析可能的原因如下：
1. 在数据起始位置insert，需要改变数组后续所有元素在内存中的位置，因此耗时长？
2. 在数组末尾insert，不需要改变数组之前所有元素在内存中的位置，只补上最后一个新增元素的位置就行了，因而速度快？
leetcode 【 Pascal's Triangle II 】python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。