首页 > 编程语言 > 详细

每日一道 LeetCode (14):数组加一

时间:2020-08-11 14:18:08      阅读:70      评论:0      收藏:0      [点我收藏+]

技术分享图片

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:数组加一

题目来源:https://leetcode-cn.com/problems/plus-one/

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

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

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

示例?1:

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

示例?2:

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

解题思路

这道题看完以后,感觉好像很简单的样子, LeetCode 最近几天的题让我一下感觉自己智商又在线了,甚至有了能暴打 LeetCode 的幻觉。

先说下我的思路,整个数组取到最后一位,直接 +1 返回,这不完了么?

感觉自己又能小母牛倒立了。

技术分享图片

结果我第一次代码写完,这个世界充满了恶意,把我的脸又一次的按在了地上摩擦。

最开始的代码是这个样子的:

public int[] plusOne(int[] digits) {
    digits[digits.length - 1] += 1;
    return digits;
}

上面的代码没有问题,可惜没有考虑 9 , 99 , 999 这种进位的情况。

这就很尴尬了,因为传入的结构是数组,传出的结构也是数组,总所周知,数组是不能动态扩容的,这就意味着如果产生了进位我们需要一个新的数组。

而且我们还需要在计算的时候进行判断,判断当前的计算是否产生了进位。

判断进位在前面的文章中介绍过,很简单,我们直接取余数判断余数是否为 0 就可以了,如果余数为0 那么一定产生了进位。

如果整个数组的余数全都变成了 0 ,如 0 , 00 , 000 ,那么传入的数组一定是 9 , 99 , 999 这种,这时候我们搞个新的数组,直接把开头赋值成 1 ,剩余位数全是 0 ,返回就可以了。

代码实现

上面已经把思路说的很清晰了,下面是我写的代码:

public int[] plusOne(int[] digits) {
    // 从末尾开始循环
    for (int i = digits.length - 1; i >= 0; i--) {
        // 先 +1
        digits[i]++;
        // 取余数, 10 的余数为 0
        digits[i] = digits[i] % 10;
        // 判断余数是否为 0 ,如果为 0 则再循环一次,产生了进位,不为 0 则可以直接返回
        if (digits[i] != 0) return digits;
    }
    // 如果在上面的循环未返回,则整体产生进位,类似于 9 , 99 , 999 , 9999 这种数组
    digits = new int[digits.length + 1];
    digits[0] = 1;
    return digits;
}

技术分享图片

注释标记的很明确了,稍微有点反人类的就是这个循环是倒序循环,从最后一位开始往前循环。好像最近的题使用到的都是倒序循环。

数组操作的效率是极其高效的,而且我发现,但凡是使用数组操作,在 LeetCode 上基本耗时都是 0ms 。

每日一道 LeetCode (14):数组加一

原文:https://www.cnblogs.com/babycomeon/p/13474816.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!