https://leetcode.com/problems/pascals-triangle/
118. Pascal’s Triangle
- Total Accepted: 103611
- Total Submissions: 290013
- Difficulty: Easy
- Contributors: Admin
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] ]
Code
class Solution(object): def generate(self, numRows): """ :type numRows: int :rtype: List[List[int]] """ if numRows == 0: return [] res = [[1]] for i in xrange(2, numRows+1): new_row = [0] * i for j in xrange(i): if j == 0: new_row[j] = 1 elif j == i-1: new_row[j] = 1 else: new_row[j] = res[-1][j-1] + res[-1][j] res.append(new_row) return res
Idea
Each element is the sum of adjacent elements in the above line. That’s how Pascal’s Triangle is defined: https://en.wikipedia.org/wiki/Pascal%27s_triangle