我们继续透过 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 泰德观点