LeetCode: 119.杨辉三角II

需要注意的是，输入3，其实想得到第4行。

思路有四个：

1. 最简单的就是用上一层的结果求下一层，所以为了得到第k行，要从第1层开始慢慢算。

2. 使用组合公式算。杨辉三角的位置可以通过的方式算，N是行数，i是第N行的第i的位置。

3. 上一层第i和i+1的元素相加，得到下一层第i+2的元素，所以，可以利用在上一层的开头insert 0，使用diff，连续向后加得到下一层。

4. 由组合公式可以推出相邻元素呈现的倍数。而且计算量比直接排列组合小，因为没有重复运算。

我仅介绍第2和3种方法。第一种等于上一题的解法。

第二种如下

class Solution:def getRow(self, rowIndex: int) -> List[int]:def c_n_i(n, i):res = 1for j in range(1, i+1):res *= (n - i + j) / jreturn resres = [1] * (rowIndex + 1)for i in range(1, rowIndex):res[i] = round(c_n_i(rowIndex, i))return res

第三种：

        res = [1]for i in range(1, rowIndex + 1):res.insert(0, 0)for j in range(i):res[j] = res[j] + res[j+1]return res

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！