iT邦幫忙

2021 iThome 鐵人賽

DAY 5
0
自我挑戰組

【用 JS 學演算法】前端工程師學徒系列 第 5

【Day 05】LeetCode:Plus One ( 用 JavaScript 學演算法 )

我們繼續透過 LeetCode #66 Plus One 來實際感受解決問題的過程 ( 題目連結 )

一、理解題目

  • 輸入:一個正整數組成,且從大到小排序好的陣列
  • 第一個數字不會是 0
  • 輸出:最後一個數字加 1

二、Edge Case

  • 本身是 0 的情況 [0]
  • 進位後,會需要增加陣列長度 ( [9,9,9] -> [1,0,0,0] )

三、題目思考

使用哪種資料結構:Array
(1) 使用迴圈遍歷 digits

  1. 先將 digits[digits.length-1] 加 1
  2. 設定 i=digits.length-1,也就是從個位數開始,逐個檢查。
  3. 如果 i < 0,結束
  4. 檢查 digits[i] 是否需要進位
  5. i = i-1
  6. 回到步驟 3

(2) 檢查 digits[i] 是否需要進位

  1. 如果 digits[i]+1 小於 9,return digits
  2. 如果 digits[i]+1 > 9
  3. 判斷 i = 0,digits[i] 設為 0,並在陣列前端新增一元素,值為 1,最後回傳 digits
  4. i != 0,digits[i] 設為 0,digits[i-1] 加一

邏輯:

let len be the length of digits

digits[len-1] += 1
for i ( len-1 to 0 by -1 ) do
  if ( digits[i] < 9 ) then
    return digits
  else
    if ( i != 0 ) then
      set digits[i] = 0
      digits[i-1] += 1
    end if
    if ( i = 0 ) then
      set digits[i] = 0
      add one element = 1 to the beginning of digits
      return digits
    end if
  end if
end for

return digits

程式碼實作:

  let len = digits.length
  digits[len-1] += 1
  
  for ( let i=len-1 ; i>=0 ; i-- ) {
    if (digits[i] <= 9) {
      return digits
    } else {
      
      if ( i !== 0) {
        digits[i] = 0
        digits[i-1] += 1
      } else {
        digits[i] = 0
        digits.unshift(1)
        return digits
      }
      
    }
  }
  
  return digits

四、學到什麼

  • 陣列方法:unshift(),在陣列前端新增一個值
  • 將大問題分成兩個部分:遍歷 + 檢查是否需要進位

原文連結:LeetCode:Plus One ( 用 JavaScript 學演算法 ) - Ted's Point 泰德觀點


上一篇
【Day 04】LeetCode:Fizz Buzz ( 用 JavaScript 學演算法 )
下一篇
【Day 06】LeetCode:Two Sum ( 用 JavaScript 學演算法 )
系列文
【用 JS 學演算法】前端工程師學徒9

尚未有邦友留言

立即登入留言