首页 / PYTHON / leetcode 【 Pascal's Triangle II 】python 实现

leetcode 【 Pascal's Triangle II 】python 实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 【 Pascal's Triangle II 】python 实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1398字，纯文字阅读大概需要2分钟。

内容图文

题目：

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:
 5return [1]
 6if rowIndex == 1:
 7return [1,1]
 8         pascal = [1,1]
 9for i in range(1,rowIndex):
10for j in range(len(pascal)-1):
11                 pascal[j] = pascal[j] + pascal[j+1]
12             pascal.insert(0,1)
13return 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:
 5return [1]
 6if rowIndex == 1:
 7return [1,1]
 8         pascal = [1,1]
 910# 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)1516# from end to start17for i in range(1, rowIndex):
18for j in range(len(pascal)-1, 0, -1):
19                 pascal[j] = pascal[j] + pascal[j-1]
20             pascal.insert(len(pascal),1)
21return pascal

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

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

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

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

】python 实现' ref='nofollow'>leetcode 【 Pascal's Triangle II 】python 实现

原文：http://www.cnblogs.com/xbf9xbf/p/4232335.html

内容总结

以上是互联网集市为您收集整理的leetcode 【 Pascal's Triangle II 】python 实现全部内容，希望文章能够帮你解决leetcode 【 Pascal's Triangle II 】python 实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1288475.html

来源：【匿名】