2efd19a9173975e358ad34421430c4fe
(难度Easy) Problem 119. Pascal's Triangle II(杨辉三角II)

Pascal's Triangle II

Difficulty

Easy

Description

Given a non-negative index _k_ where _k_ ≤ 33, return the _k_ th index row of
the Pascal's triangle.

Note that the row index starts from 0.


In Pascal's triangle, each number is the sum of the two numbers directly above
it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only _O_ ( _k_ ) extra space?

题意

和上题一样,也是求杨辉三角。但是不同的是,这题当中我们需要求的不是整个杨辉三角,而只是其中的一行。

题解

由于题目要的是杨辉三角当中的某一行,而不是整体。我们当然可以求出整个杨辉三角,然后返回这一行。只要在之前的代码基础上,稍作改动即可。但这明显不是最好的解法, 为了得出答案我们计算了冗余的行的信息。那有什么办法可以解决吗?

当然是有的,杨辉三角有一个特性,它其实代表了幂的系数。我们用$(x+1)^m$来举例,当次数m=0的时候,显然展开项是1。当m=1的时候,展开项就是x+1,也就是说一次项系数是1,常数项系数也是1。那么对应(1, 1)。

当m=2的时候,展开结果是$x^2+2x+1$,对应系数是(1, 2, 1)。这正是杨辉三角当中的第二行,也就是说杨辉三角当中的第n行,即代表了$(x+1)^n$的系数。

top Created with Sketch.