Leetcode 题解|66. 加一

Tags: 数组

题目

加一

用一个由int类型正整数组成，且元素大于1的数组来表示一个非负整数。实现一个函数对这个非负整数加一。高位在前地位在后，数组中每个元素的范围0~9。且除了整数0以外 [0] ，这个整数不会以零开头。

Simple One:

输入: [2,3,4]
输出: [2,3,5]
解释: 输入数组表示数字 234。输出235。

Simple Two:

输入: [9,9,9,9]
输出: [1,0,0,0,0]
解释: 输入数组表示数字 9999。输出10000.

题目分析

1. 获取数组最后一位索引idx，反向遍历，也就是从代表的整数的个位开始判断。
2. 如果最个位数不等于9，就直接数组最后一个元素+1.跳出循环。
3. 如果个位等于9，个位0，继续循环，根据1的条件判断百位。
4. 重复2-3直到跳出循环或者循环结束。
5. 当循环结束后如果最高位为0，说明已经进位到高位了。那么需要再数组最前面插入一个元素为1. 例如 999 + 1 = 1000;

复杂度分析

• 时间复杂度：O(n)， 假设数组总共有 n 个元素，至多遍历 n 步。
• 空间复杂度：O(1)。

Java

class Solution {
    public int[] plusOne(int[] digits) {
        int idx = digits.length - 1;
            while (idx >= 0) {

                if (digits[idx] == 9) {
                    digits[idx] = 0;
                } else {
                    digits[idx] = digits[idx] + 1;
                    break;
                }
                idx --;
            }
            if (digits[0] == 0) { 
                digits = new int[digits.length + 1];
                digits[0] = 1;
            }
            return digits;
    }
}

Swift

class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        
        var idx = digits.count - 1
        var results = digits
            while (idx >= 0) {

                if (results[idx] == 9) {
                    results[idx] = 0
                } else {
                    results[idx] = results[idx] + 1
                    break
                }
                idx -= 1
            }
            if (results[0] == 0) { 
                    results = [Int](repeating: 0, count: digits.count + 1)
                    results[0] = 1
            }
            return results
    }
}

JavaScript

var plusOne = function(digits) {
    
    
    var idx = digits.length - 1;
        while (idx >= 0) {

            if (digits[idx] == 9) {
                digits[idx] = 0;
            } else {
                digits[idx] = digits[idx] + 1;
                break;
            }
            idx --;
        }
        if (digits[0] == 0) { 
            digits.unshift(1);
        }
        return digits;
    
};