[Leetcode]119 : Pascal’s Triangle II

Link : https://leetcode.com/problems/pascals-triangle-ii/

Problem :
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

圖來自leetcode

Thoughts :
1. 只 return 該行的結果。
2. 先計算該行會有幾個數字。
(Note : rowIndex從0開始)
3. 每一行的結果都是上一行的兩個數字、兩個數字加起來的。並且每一行的第一個數字都是1。
ex:
第二行為 0, 1, 1, 0
第三行為 0+1, 1+1, 0+1 = 1, 2, 1
(Note:從後面開始加,第四位跟第三位開始加,第三位跟第二位,第二位跟第一位)
如果從前面開始加會變成:
第二行為 0, 1, 1, 0
第三行為 0+1, 1+1, (1+1)+1 = 1, 2, 3 ->會出現問題,所以從後面開始加3. 4. return 結果。

Solution :

time complexity = O(n²)?, space complexity

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store