python-leetcode/pascals-triangle.py at master · mindheist/python-leetcode · GitHub

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
61
62
63
64
65
66
67
68
69
# https://leetcode.com/problems/pascals-triangle/
#
# 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]
# ]

# solution video : https://www.youtube.com/watch?v=rlKGgxck7X0

import unittest
class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        return_list = []
        ns = xrange(numRows)
        for n in ns:
            nlist = []
            for k in xrange(n+1):
                nlist.append(self.nchoosek(n,k))
            return_list.append(nlist)
        return return_list

    def nchoosek(self,n,k):
        if k == 0 or k == n :
            return 1
        else:
            return self.factorial(n)/(self.factorial(k) * self.factorial(n-k))

    def factorial(self,n):
        if n==0:
            return 1
        else:
            return n*self.factorial(n-1)

class TestPascalsTriangle(unittest.TestCase):
    my_solution = Solution()

    def test_pascals_triangle_1(self):
        self.assertEqual(self.my_solution.generate(1),[[1]])

    def test_pascals_triangle_2(self):
        self.assertEqual(self.my_solution.generate(2),[[1], [1, 1]])

    def test_pascals_triangle_3(self):
        self.assertEqual(self.my_solution.generate(3),[[1], [1, 1], [1, 2, 1]])

    def test_pascals_triangle_4(self):
        self.assertEqual(self.my_solution.generate(4),[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]])

    def test_pascals_triangle_5(self):
        self.assertEqual(self.my_solution.generate(5),[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]])

if __name__ == "__main__":
    unittest.main()

# [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
# my_solution = Solution()
# print my_solution.generate(6)