[数据结构与算法]【leetcode】题解 66. 加一

题目链接? ??力扣https://leetcode-cn.com/problems/plus-one/

?题目描述的含义是将原本int类型的数组加1后输出，阅读题目有两个思路解题：

1.将数组转数字加1再转数组，但是这样转换有整数溢出的情况

2.数组按位加一处理，得出结果

个人解法：

class Solution {
     public int[] plusOne(int[] digits) {boolean flag = true;
        List<Integer> list = new ArrayList<>();
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] == 9 && flag) {
                list.add(0);
                flag = true;
                if(i == 0){
                    list.add(1);
                }
            } else {
                if (flag) {
                    list.add(digits[i] + 1);
                } else {
                    list.add(digits[i]);
                }
                flag = false;
            }
        }
        int result[] = new int[list.size()];
        for(int i=0;i< list.size();i++){
            result[list.size() - i - 1] =  list.get(i);
        }
        return result;

    }
}

官方解法：

官方的主要思路是判断尾数是否为9，是9则不需要考虑进位问题

class Solution {
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) {
                ++digits[i];
                for (int j = i + 1; j < n; ++j) {
                    digits[j] = 0;
                }
                return digits;
            }
        }

        // digits 中所有的元素均为 9
        int[] ans = new int[n + 1];
        ans[0] = 1;
        return ans;
    }
}
 

复杂度分析

时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{digits}digits 的长度。

空间复杂度：O(1)O(1)。返回值不计入空间复杂度

?也看到了其他人比较好的解法，直接考虑加一后的结果是不是有进位，思路与官方类似

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