塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-119杨辉三角II

最初想法:
最初想法:

找规律$a_i=[1,i-1,]$

一1

二1 1

三1 2 1 ||12

四1 3 3 1

五1 4 6 4 1||23

六1 5 10 10 5 1

七1 6 15 20 15 6 1||45

八1 7 21 35 35 21 7 1

九1 8 28 56 70 56 28 8 1

如果是奇数行:$a_i= [1,i-1, ..(i-2)*4,]$

如果是偶数行,$a_i = [1, (i-1)1,(i-1)3,(i-1)*5]$

失败,没找到规律。

看题解:
杨辉三角有组合数的性质
mark

计算组合数,因为对称,计算一半就行.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def generate(numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
if numRows==1:
return [1]
templist = []
mid = numRows//2
#计算中间值左边的,包括中间值
for i in range(mid):
templist.append(combination(numRows-1,i))
#如果是奇数行,计算中间值
if numRows%2==1:
templist.append(combination(numRows -1 , mid))
#将左边复制到右边
templist.extend(templist[mid-1::-1])

return templist

def combination(m,n):
#计算组合,即从m里选n个的情况总数
if n==0:
return 1
temp=m
temp2=n
for i in range(n-1):
m -= 1
temp *= m
n -= 1
temp2 *= n
return int(temp/temp2)
if help:小手一抖点个广告 or 大手一挥资助一下