iT邦幫忙

2022 iThome 鐵人賽

DAY 16
0
自我挑戰組

JavaScript - 30天 - 自學挑戰系列 第 16

LeetCode Js-119. Pascal's Triangle II

  • 分享至 

  • xImage
  •  

LeetCode Js-119. Pascal's Triangle II

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]

Example 1:

Input: rowIndex = 3
Output: [1,3,3,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:

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]

上一篇
LeetCode Js-169. Majority Element
下一篇
LeetCode Js-217. Contains Duplicate
系列文
JavaScript - 30天 - 自學挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言