X

LEETCODE 66. Plus One 解题思路分析

题目大意:

加一

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

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

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

示例 1:

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

示例 2:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=66

解题思路分析:

加法题目我们之前介绍过不少。解题时关键在于使用一个carry变量来代表进位。本题是一个数字(用数组表示)加1,因此,我们可以从数组最后一位(数字最低位)向前循环,carry默认为1。对于每一位上的数字,我们首先使用当前位上的数字加上进位carry得到一个和sum,sum与10的余数为当前位上相加计算后的数字,sum与10的商则是carry。

注意全部循环结束之后,如果carry仍为1,别忘了将这个1放到数字的最高位去(最终数字比原数字多一位)。

实现代码:

public int[] plusOne(int[] digits) {
    int carry=1;
    for(int i=digits.length-1;i>=0;i--){
        int sum=carry+digits[i];
        carry=sum/10;
        digits[i]=sum%10;
        // 之后不会再出现进位,高位上的数字都会保持不变
        if(carry==0) return digits;
    }
    int[] res = new int[digits.length+1];
    res[0]=1;
    for(int i=1;i<res.length;i++){
        res[i]=digits[i-1];
    }
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One.

Memory Usage: 37.8 MB, less than 5.64% of Java online submissions for Plus One.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-66-plus-one-解题思路分析/
Categories: leetcode
kwantong: