算法---LeetCode 66. 加一

1. 题目

原题链接
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

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

示例 2：

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

示例 3：

输入：digits = [0]
输出：[1]

提示：

1 <= digits.length <= 100
0 <= digits[i] <= 9

Related Topics 数组
???? 665 ???? 0

2. 题解

2.1 解法1: 数学方法

加一后的两种情况:

1. 不为 9 ,无进位
2. 为9, 有进位

巧妙的处理方法:

3. 从后向前遍历, 每位加一, 若加后不为0, 则直接返回
4. 若循环结束, 说明全是9 ,增加数组一位, 首元素赋值1, 后面默认全0

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

参考:Java 数学解题

2.2 解法2: 暴力法 (会因为数字超界不能ac)

1. 先遍历一遍数组, 将其转化为 数字
2. 然后加1, 再转为数组

    class Solution {
        public int[] plusOne(int[] digits) {
            long sum = 0;
            for (int i = 0; i < digits.length; i++) {
                sum = sum * 10 + digits[i];
            }
            sum++;
            LinkedList<Integer> list = new LinkedList<>();
            while (sum != 0) {
                int temp = (int) (sum % 10);
                list.addFirst(temp);
                sum = sum / 10;
            }
            int[] ans = new int[list.size()];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = list.get(i);
            }
            return ans;
        }
    }