[LeetCode] 66. Plus One

問題描述

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

翻譯

給定一個非空存正整數位數的陣列，你要替這串數值加上一
最高有效數位存放在陣列初始位置，數值每個數字各依序別存在陣列裡頭
你能假定這串整數不以零開頭，除了本身為零

解題思維

1. 先替陣列最後一個數值加上一
2. 以迭代方式判斷是否大於 9，以此判斷是否要進位
3. 最後判斷進位的變數是否不等於零，若不為零，將進位數填入陣列第一個位置
   ，將計算後陣列依序填入新的陣列

解題報告

Level: Easy
Time Complexity: O(n)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One.
Memory Usage: 37.9 MB, less than 5.64% of Java online submissions for Plus One.

程式完整解題

class Solution {
    /** 數值陣列加一
    * @param 數值陣列
    * @return 加一後的數值陣列
    */
    public int[] plusOne(int[] digits) {
        digits[digits.length - 1 ] += 1;

        int carry = 0;
        for(int i = digits.length - 1 ; i >= 0 ; i--){
            digits[i] += carry;
            if(digits[i] > 9){
                digits[i] %= 10;
                carry = 1;
            } else{
                carry = 0;
            }
        }

        if(carry == 1){
            int[] answer = new int[digits.length + 1 ];
            answer[0] = carry;
            System.arraycopy(answer, 1, digits, 0, digits.length);
            return answer;
        }
         return digits;
    }
}