InterviewBit – Pascal Triangle

Source: Pascal Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

Pascal’s triangle : To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R – 1.

Example:

Given numRows = 5,

Return

[
     [1],
     [1,1],
     [1,2,1],
     [1,3,3,1],
     [1,4,6,4,1]
]

---

解題：

1. 從釋例的表達可能看不太出來，但基本上下一層的數字就是上一層的左右兩邊數字相加或是1（如上一層並非左右兩邊皆有數字）：
   • [   [1],

   •    [1,1],

   •   [1,2,1],

   •  [1,3,3,1],

   • [1,4,6,4,1]
]
2. 故僅需找出相加的index邏輯並執行即可。

Code:

class Solution:
    # @param A : integer
    # @return a list of list of integers
    def generate(self, A):
        if A == 0: return []
        output = []
        for i in range(1, A+1):
            appending = [0] * i
            output.append(appending)
        #set all left and right borders to be 1
        for i in range(len(output)):
            output[i][0] = 1
            output[i][-1] = 1
        #return if no inside contents needed to be updated
        if len(output) <= 2: return output

        #fill out contents inside
        row = 2 #start at third row
        while row < len(output):
            for i in range(1, len(output[row]) - 1):
            #exclude indice 0 and -1 in every row
                output[row][i] = output[row-1][i-1]+output[row-1][i]
            row += 1
        return output

GitHub: InterviewBit – Pascal Triangle