Q119 Pascal's Triangle II

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?

解题思路:

题目参考见 Q118 Pascal's Triangle

要求空间复杂度为O(k),所以构造一半。最后根据奇、偶行构造完整的返回值。思路一样,即第k行的数是由第k-1行的数得到的,因此循环构造即可。

Python实现:
class Solution:
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex < 0:
            return []
        rlist = []
        rlist.append(1)
        i = 1
        while i <= rowIndex:
            j = len(rlist) - 1
            while j > 0:   # 构造下一个列表元素
                rlist[j] = rlist[j] + rlist[j-1]
                j -= 1
            if i % 2 == 1:   # 如果是奇数行,需要加一个元素
                rlist.append(rlist[-1])
            i += 1
        # 构造另一半
        if rowIndex % 2 == 1:   # 如将 [1,3,3] 变成 [1,3,3,1]
            rlist.extend(rlist[-3::-1])
        else:    # 如将 [1,4,6] 变成 [1,4,6,4,1]
            rlist.extend(rlist[-2::-1])  
        return rlist

a = 3
b = Solution()
print(b.getRow(a))  # [1,3,3,1]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏null的专栏

剑指Offer——编程题的Java实现

声明:我写这个的意图是我在看书的过程中,就我掌握的内容做一个笔记,没有抄袭的意图。再次说明一下,我找工作的过程中并不顺利,没有像那些牛人们拿到一大把的Offer...

7973
来自专栏闵开慧

曾经做过的40道程序设计课后习题总结(三)

曾经做过的40道程序设计课后习题总结(三) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询 7 求最...

3978
来自专栏数据之美

Python Tips, Tricks, and Hacks

一、快速技巧 1.1、4 种引号 '  '''  "  """  print """I wish that I'd never heard him say...

2705
来自专栏Golang语言社区

【Go 语言社区】JavaScript Date(日期)对象

日期对象用于处理日期和时间。 JavaScript Date(日期)对象 实例 返回当日的日期和时间 如何使用 Date() 方法获得当日的日期。 getTim...

33911
来自专栏菩提树下的杨过

Flash/Flex学习笔记(55):背面剔除与 3D 灯光

Animation in ActionScript3.0 这本书总算快学完了,今天继续:上一回Flash/Flex学习笔记(50):3D线条与填充 里,我们知道...

2438
来自专栏码匠的流水账

聊聊flink的SpoutWrapper

flink-storm_2.11-1.6.2-sources.jar!/org/apache/flink/storm/wrappers/SpoutWrapper...

1042
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第五章 Kotlin面向对象编程(OOP)一个OOP版本的HelloWorld构造函数传参Data Class定义接口&实现之写pojo bean定一个Rectangle对象封

We frequently create a class to do nothing but hold data. In such a class some s...

2104
来自专栏Java爬坑系列

【Java入门提高篇】Day33 Java容器类详解(十五)PriorityQueue详解

 今天要介绍的是基础容器类(为了与并发容器类区分开来而命名的名字)中的另一个成员——PriorityQueue,它的大名叫做优先级队列,想必即使没有用过也该有所...

1211
来自专栏编程札记

java之hashtable和hashmap

1746
来自专栏软件开发 -- 分享 互助 成长

C++ STL之排序算法

排序算法和查找算法差不多,也涉及到迭代器区间问题,关于该问题的注意事项就不在啰嗦了 一、全部排序sort、stable_sort sort是一种不稳定排序,使用...

2015

扫码关注云+社区

领取腾讯云代金券