LeetCode Js-119. Pascal’s Triangle II

    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
    };