资讯专栏INFORMATION COLUMN

[Leetcode] Plus One 加一

shmily / 3375人阅读

摘要:不过这里有个小技巧,因为我们只要加,所以不用完全模拟加法的所有规则一个数如果不是,那加以后不会对其他位产生影响。

Plus One

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

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

遇九置零法 复杂度

时间 O(N) 空间 O(1)

思路

简单的加法运算。这里需要注意的是,数字的最高位的下标是0,最低位下标是length-1,所以我们要从后向前模拟加法。不过这里有个小技巧,因为我们只要加1,所以不用完全模拟加法的所有规则:一个数如果不是9,那加1以后不会对其他位产生影响。根据这个思路,我们先把末尾所有连续的9置0,然后对从后往前第一个不是9的数加1就行了。如果越界的话,说明原数全是9,那就要建个新数组存放结果。

注意

System.arraycopy(src, 0, dst, 0, length) 可以用来高效拷贝数组

代码
public class Solution {
    public int[] plusOne(int[] digits) {
        int i = digits.length - 1;
        // 从后向前把所有连续9置0,直到不是9
        while(i >= 0 && digits[i] == 9){
            digits[i] = 0;
            i--;
        }
        // 如果越界,则拷贝一个新数组并在最前面置1
        if(i < 0){
            int[] res = new int[digits.length + 1];
            System.arraycopy(digits, 0, res, 1, digits.length);
            res[0] = 1;
            return res;
        } else {
        // 否则,将第一个不是9的数字加1就行了
            digits[i] += 1;
            return digits;
        }
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/64583.html

相关文章

  • Leetcode加一 (java、python3)

    摘要:加一给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。示例输入输出解释输入数组表示数字。思路指针从最后往前移动,若值为逐个加一,并赋值。不等于则退出循环。首位如果为是则证明需要进一。只需首位赋值即可。 加一 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。 你可以假设除了整数 0 之外,这个...

    沈建明 评论0 收藏0
  • Leetcode加一 (java、python3)

    摘要:加一给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。示例输入输出解释输入数组表示数字。思路指针从最后往前移动,若值为逐个加一,并赋值。不等于则退出循环。首位如果为是则证明需要进一。只需首位赋值即可。 加一 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。 你可以假设除了整数 0 之外,这个...

    Apollo 评论0 收藏0
  • leetcode66 将数组表示的非负整数加一

    摘要:题目要求一个非负整数被表示为一个数组,数组中每一个元素代表该整数的一个位。数组的下标越小,代表的位数越高。现在对该数组做加一运算,请返回结果数组。 题目要求:一个非负整数被表示为一个数组,数组中每一个元素代表该整数的一个位。数组的下标越小,代表的位数越高。现在对该数组做加一运算,请返回结果数组。 /** * @author rale * * Given a non-negativ...

    QLQ 评论0 收藏0
  • leetcode 66 Plus One

    摘要:题目详情题目的意思是,给你一个用数组表示的一个非负整数。你需要返回这个整数加后,所对应的数组。解法一主要需要关注的点就在于,当末尾数字为的时候的进位情况。如果不需要进位了,则代表循环可以结束了。 题目详情 Given a non-negative integer represented as a non-empty array of digits, plus one to the in...

    ytwman 评论0 收藏0
  • [LeetCode/LintCode] Plus One

    Problem Given a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. Example Given [1,2...

    sunsmell 评论0 收藏0

发表评论

0条评论

shmily

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<