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 条评论
登录 后参与评论

相关文章

  • Q118 Pascal's Triangle

    Given numRows, generate the first numRows of Pascal's triangle. For example, giv...

    echobingo
  • 三个数的和小于等于k

    给一个数组以及一个数K, 从这个数组里面选择三个数,使得三个数的和小于等于K, 有多少种选择的方法?(不包括重复的情况) Example: Input: nu...

    echobingo
  • 吴恩达 —— 深度学习 Course 1 笔记

    Course1:神经网络和深度学习,包括: ---- [1] Week1:深度学习概述 [2] Week2:神经网络基础 [3] Week3:浅层神经网络 ...

    echobingo
  • C#:DataTable映射成Model

    这是数据库开发中经常遇到的问题,当然,这可以用现成的ORM框架来解决,但有些时候,如果DataSet/DataTable是第三方接口返回的,ORM就不方便了,还...

    菩提树下的杨过
  • 2017-03-02学习笔记

    知识点 一、static public class Spike { public static void main(String[] args) ...

    Zephery
  • VXLAN篇之终章:Multi-Site

    作者简介:张磊,思科原厂8年多technical consulting engineer,精通思科数据中心/园区网产品及技术;精通SAN网络架构及产品;熟悉广域...

    SDNLAB
  • mysql 语句传参数 -- prepare语句的用法

    mysql默认在语句是不能传参数的,例如 select * from a limit @a,@b;这样是会报错的,那怎么样才能传参数呢?

    仙士可
  • RecyclerView 分页功能

    code_horse
  • 基于 RxJava2+Retrofit2 精心打造的 Android 基础框架 XSnow

    XSnow ? 基于RxJava2+Retrofit2精心打造的Android基础框架,包含网络、上传、下载、缓存、事件总线、权限管理、数据库、图片加载、UI模...

    非著名程序员
  • 面试题:如何理解 Linux 的零拷贝技术?

    本文讲解 Linux 的零拷贝技术,云计算是一门很庞大的技术学科,融合了很多技术,Linux 算是比较基础的技术,所以,学好 Linux 对于云计算的学习会有比...

    老钱

扫码关注云+社区

领取腾讯云代金券