118. Pascal's Triangle
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
Example:
Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
当i=0,nums[0][0]=1
当i>0,numrow-1>j>0 , nums[i][j]=nums[i-1][j-1]+nums[i-1][j]
当i>0,j=0或j=numrow-1,nums[i][j]=1
一共numrow行
每一行j从0到numrow-1
时间复杂度 1+2+····n~n^2/2 O(N^2)
空间复杂度 也是O(N^2)
这里要注意对空矩阵的赋值,不能直接用索引,而是要用append
discuss:
上一行后面加0,和0加上上一行 这两行相加就得到这一行~很机智
时间复杂度和空间复杂度也并没有改进。