LeetCode 119. 杨辉三角II（ Pascal ‘s Triangle II）

问题描述：

给定一个非负整数k，k小于等于33，返回杨辉三角中下标为k的行的内容。

注:

空间复杂度要求为O(k)。

示例：

C语言实现：

关于杨辉三角，我们在 中遇到过，其实两道题大同小异。

关于实现，我们今天换一种，我们用递归方法来实现。

题目中k作为杨辉三角的下标，起始值是0，为了方便描述，我定义一个变量n = k+1，那么n就表示为杨辉三角的第n层。

我们回顾一下，n+1层的推导如下：

第n+1层值的是从最顶层一层一层用这样相同的方法推导过来的，所以很适合用递归。

由于题目限定，空间复杂度要满足O(k)，所以我们不方便在 递归函数 中申请空间。我们的做法是在getRow函数中就分配好，然后传递给递归函数直接使用。

由于杨辉三角的特性，第n层的数组长度就是n，即k+1，所以我们可以一次性就分配好。

我们还需要确保分配的数组必须全部用0填充。因为在递归的过程中要不断的错位相加，所以要避免未正确初始化导致的数组值异常。

详细代码如下：

Java语言实现：

Java 的实现和C语言的实现一致。

递归函数不建议用ArraysList来实现，因为ArraysList内部是对数组封装，没有直接对int[]操作效率高。实际测试结果也是这样ArraysList要慢一些。

另外关于int[]转换成List的方法，不要用java8的Arrays.stream特性，这个方法很慢。直接遍历int[]是比较快的。

代码如下：

Python语言实现：

Python实现，我们用zip加列表生成器实现，这和 python的实现是类似的。

代码如下：

谢谢大家一直以来的关注和支持！

我一直在努力的写好每一篇文章，画好每一份插图。但是作为一个996从业人员，时间精力十分有限。所以针对评论部分，以后 只回答粉丝的问题和私信 。希望仅仅是路过的朋友能够体谅， 希望更多人关注《 》， 谢谢！