LeetCode --- 66.加一

LeetCode --- 字符串、数组
简书专栏：https://www.jianshu.com/nb/41796568
知乎专栏：https://zhuanlan.zhihu.com/c_174823416

一、题目描述

来源：力扣（LeetCode）
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 :

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

二、实现思路以及代码

2.1 思路一：暴力破解法（不通过）

可以将数组转换为整数，进行加一然后再转换成为数组。但是这样做有一个缺陷，就是如果数组中的数超过了整数的范围，那么进行转换时会报错。有考虑过使用bigInteger但是那样的话我觉得违背了题目想表达的含义。下面给出代码：

public static int[] plusOne(int[] digits) {
        int length = digits.length, temp = 0;
        for(int i = length - 1; i >= 0; i--) {
            temp += (digits[i] * Math.pow(10,length - i -1));
        }
        temp += 1;
        String str = String.valueOf(temp);
        String[] strs = str.split("");
        int[] result = new int[strs.length];
        for(int j = 0; j < str.length(); j++) {
            result[j] = Integer.valueOf(strs[j]);
        }
        return result;
    }

2.2 思路二：数组加一进位法（巧妙）

理解题意可以发现，如果直接从数组入手，当最后一位不为9时，可以直接在数组最后一位上+1，然后返回数组即可。所以要处理的就是当最后一位为9时的情况。
模拟进位操作，从数组最后一位向前开始遍历，若digits[i] + 1之后取余10等于0，则表明进位，继续向前遍历，进行加一操作，并判断取余10之后是否为0，一直到不为0时表明该位置的数字加一之后不进位，返回该数组
特殊情况是当出现9，99，999这类数字时，循环到底也不会返回，这是需要特殊处理一下，扩容一位，并令第一位为1即可

public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >=0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if(digits[i] != 0) return digits;
        }
        digits = new int[digits.length+1];
        digits[0] = 1;
        return digits;
    }

三、测试代码

        int[] nums1 = {6,5,4,3,2,1,0};
        int[] nums2 = {6,5,4,3,2,9,9};
        System.out.println(Arrays.toString(plusOne(nums1)));
        System.out.println(Arrays.toString(plusOne(nums2)));
    }

输出结果为：

[6, 5, 4, 3, 2, 1, 1]
[6, 5, 4, 3, 3, 0, 0]