#66 Plus One

tags: LeetCode Array

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Want to learn more? ➜ HackMD Tutorials


#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(),在陣列前端新增一個值
  • 將大問題分成兩個部分:遍歷 + 檢查是否需要進位