我們繼續透過 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 泰德觀點