这道题让我深深感觉数学才是算法的核心，不对，是爸爸。
简单说下题目，帕斯卡三角，如下图，从第三行开始，除了两边的1，其他元素都是上一行两个左右元素之后，比如第三行的中间的2，就是上面两个1之和。
如果第一行为0行，那么给出行数，返回该行所有元素，比如给出3，返回[1,3,3,1]
关于帕斯卡三角，还是很多有趣属性，可以搜索，最主要就是和二项式展开系数的关系。
如果不考虑算法复杂度，其实只要从第一行开始一行一行算下来即可，这样无论如何就要两次循环嵌套，复杂度是K(O^2)。
如果要K(O)一次循环的复杂度，就要思考下数学联系了，后面实在想不出搜索下。发现关系如下：
即第n行第i个（n，i 从 0 开始）是C（i，n），组合计算公式：
化简得 ： C（i，n） = n * ( n -1) * ... * ( n - i +1) / ( 1 * 2 * ... * i )
惭愧，我的代码基本就是他的python版本。
可能稍微优化地方是，这里先创建了一个行数加以长度的0值队列，这个也是帕斯卡三角的属性，每一行的元素数是行数加一；因为帕斯卡三角元素是前后对称，每次就计算前面一个，同时更新前后对称两个；当队列所有元素不为0时候，返回该队列即是答案。这样就只用遍历一半即可。
代码如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
rowList = [0 for x in range(rowIndex+1)]
m = 1
for i in range(len(rowList)):
if i == 0:
rowList[0] =1 rowList[rowIndex] = 1
elif rowList[i] != 0:
return rowList
else:
m = int(m*(rowIndex-i+1)/i)
rowList[i] = m
rowList[rowIndex - i] = m
return rowList
|