# #66 Plus One
###### tags: `LeetCode` `Array`

:::info
:pushpin: Want to learn more? ➜ [HackMD Tutorials](https://hackmd.io/c/tutorials)
:::
---

[#66 Plus One 題目連結](https://leetcode.com/problems/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()，在陣列前端新增一個值
* 將大問題分成兩個部分：遍歷 + 檢查是否需要進位