66. Plus One

╰半夏微凉° 2022-06-12 23:37 133阅读 0赞

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

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

The digits are stored such that the most significant digit is at the head of the list.

问题描述：给定一个非负整数，该整数按位存储于一个int数组中，即整数的每一位是数组的一个元素，排列顺序为：最高位在digits\[0\]，对该整数进行+1操作。除了0本身，数组digits\[0\]不为0，即最高位不为0。

分析：从数组的最后一位开始加1，需要考虑是否有进位。如果有进位的话令变量m=1表示有进位；如果到digits\[0\]为仍然有进位（这种情况下该整数的每一位都为9，都有进位），则数组长度加1，digits\[0\]=1，其余均为0。

有进位的情况：digits\[i\]不为0，且(digits\[i\]+m)%10==0，m记录的是当前位置i的后一位i++（即整数的较低一位）是否有进位。有进位时m=1；否则m=0。

public class Solution {
        public int[] plusOne(int[] digits) {
            if(digits == null || digits.length == 0)
                return digits;
            int m = 1;
            for(int i = digits.length-1;i >= 0;i--){
                if(digits[i] != 0 && (digits[i]+m)%10 == 0){
                    digits[i] = 0;
                    m = 1;
                }else{
                    digits[i] += m;
                     m = 0;
                }
            }
            if(digits[0] == 0){
                int newDigits[] = new int[digits.length+1];
                newDigits[0] = 1;
                for(int i = 1;i < digits.length-1;i++){
                    newDigits[i] = 0;
                }
                return newDigits;
            }else
                return digits;
        }
    }