FilesExpand file tree

master

/

pascals-triangle.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (54 loc) · 1.43 KB

master

/

pascals-triangle.py

Copy path

Top

File metadata and controls

• Code
• Blame

60 lines (54 loc) · 1.43 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

# Time: O(n^2)

# Space: O(1)

#

# Given numRows, generate the first numRows of Pascal's triangle.

#

# For example, given numRows = 5,

# Return

#

# [

# [1],

# [1,1],

# [1,2,1],

# [1,3,3,1],

# [1,4,6,4,1]

# ]

#

class Solution:

# @return a list of lists of integers

def generate(self, numRows):

result = []

for i in xrange(numRows):

result.append([])

for j in xrange(i + 1):

if j in (0, i):

result[i].append(1)

else:

result[i].append(result[i - 1][j - 1] + result[i - 1][j])

return result

def generate2(self, numRows):

if not numRows: return []

res = [[1]]

for i in range(1, numRows):

res += [map(lambda x, y: x + y, res[-1] + [0], [0] + res[-1])]

return res[:numRows]

def generate3(self, numRows):

"""

:type numRows: int

:rtype: List[List[int]]

"""

if numRows == 0: return []

if numRows == 1: return [[1]]

res = [[1], [1, 1]]

def add(nums):

res = nums[:1]

for i, j in enumerate(nums):

if i < len(nums) - 1:

res += [nums[i] + nums[i + 1]]

res += nums[:1]

return res

while len(res) < numRows:

res.extend([add(res[-1])])

return res

if __name__ == "__main__":

print Solution().generate(5)