LeetCode Js-119. Pascal’s Triangle II

    AllenLi
    LeetCode Js-Array

    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:

    給予一個整數 rowIndex，回傳 Pascal 三角形的第 rowIndex-th行。
ex.在 Pascal 三角形中，每個數字都是正上方的兩個數字之和。

- rowIndex = 5
- array-1th =     [1]
- array-2th =    [1,1]
- array-3th =   [1,2,1]
- array-4th =  [1,3,3,1]
- array-5th = [1,4,6,4,1]

    119. Pascal's Triangle II-1
    119. Pascal's Triangle II-2

    Example 1:

    Input: rowIndex = 3
Output: [1,3,3,1]

    Example 2:

    Input: rowIndex = 0
Output: [1]

    Example 3:

    Input: rowIndex = 1
Output: [1,1]

    Solution:
    1. 如果 rowIndex === 0，則回傳 [1]。
    2. 如果 rowIndex === 1，則回傳 [1,1]。
    3. 宣告 array = [1]
    4. 執行題目要求的第 i 行，為執行 i 次的 for 迴圈。
    5. 宣告 previous 為當前陣列 i 的前一個位置數值。(array[i – 1]
    6. 執行題目要求的第 i – 1 行，為執行 j 次的 for 迴圈。
    7. 宣告 current 為 array[j]，如不存在則返回 0。
    8. 變更 array[j] 更新為上一行的數值總和。
    9. 將 previous 變更為當前的數值，進入輪 j 迴圈。
    10. 運用array.push(1)來完成陣列最後一個值為 1。
    11. 回傳 array。

    i = V
previous = O
current = #
                #
array-2th =  [1,1]  ->j
array-3th = [1,2,1] ->i
             O V

    Code 1:

    var getRow = function(rowIndex) {
  if (rowIndex === 0) return [1]
  if (rowIndex === 1) return [1,1]

  let array = [1]

  for (let i = 1; i <= rowIndex; i++) {
    let previous = array[i - 1]

    for (let j = 1; j < i; j++) {
      let current = array[j] ? array[j] : 0

      array[j] = previous + current
      previous = current
    }
    array.push(1)
  }
  return array
};

    FlowChart:
    Example 1

    Input: rowIndex = 3
let array = [1]

step.1
i = 1, j = 1
previous = array[1-1] = array[0] = 1

array.push(1) = [1] => [1,1]

step.2
i = 2, j = 1
previous = array[2-1] = array[1] = 1

step.2-1
i = 2, j = 1
current = array[1] ? array[1] : 0 => 1 //array[1] = 1
array[1] = previous + current = 1 + 1 //2
previous = current //1

array.push(1) = [1] => [1,2,1]

step.3
i = 3, j = 1
previous = array[3-1] = array[2] = 1

step.3-1
i = 3, j = 1
current = array[1] ? array[1] : 0 => 2 //array[1] = 2
array[1] = previous + current = 1 + 2 //3
previous = current //1

step.3-2
i = 3, j = 2(j < 3)
current = array[2] ? array[2] : 0 => 2 //array[2] = 2
array[2] = previous + current = 1 + 2 //3
previous = current //1
array.push(1) = [1] => [1,3,3,1]

return array //[1,3,3,1]

    Example 2

    Input: rowIndex = 0
if (rowIndex === 0) return [1]

    Example 3

    Input: rowIndex = 1
if (rowIndex === 1) return [1, 1]

    Code 2:

    var getRow = function(rowIndex) {
  let ans = new Array(rowIndex + 1)

  ans[0] = ans[rowIndex] = 1
  for (i = 1, up = rowIndex; i < rowIndex; i++ , up--)
    ans[i] = ans[i - 1] * up / i
  return ans
};

    Related Posts