怒刷力扣(加一)

简介: 数字加一如果放到数组中会发生哪些奇奇怪怪得事情呢?那么接下来就一起看看数字放在数组中加一,怎么计算吧。

加一

WangScaler: 一个用心创作的作者。

声明:才疏学浅,如有错误,恳请指正。

题目

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

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

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

分析

这个题其实就是把一个正数拆分下来的每个数放进数组里给你,你把加一之后的数,再放进数组里。这只是简单的理解,如果你真这么写就麻烦了,首先你得把数组拼接回数字,需要遍历一遍,加一之后,再放回数组,再遍历一遍,这样无疑是很麻烦的一件事。上面的程序只是对题意得简单理解就是数字加一。

在数组里进行操作无疑是一件简单得事,那么我们怎么处理呢?

  • 数组的最后一位如果小于9,那么你需要把最后一位置加一。
  • 数组的最后一位是9,且数组的长度大于等于2,那么需要把最后一位置0,上一位加一。
  • 数组最后一位是9,前边加一也是9,直到没有最后一位进行加一,那么需要扩容,第一位为1,其他的为0。

把这三个条件实现,那么答案也就出来了。

答案

class Solution {
    public int[] plusOne(int[] digits) {
        int lastNum = digits[digits.length - 1];
        int i = 1;
        while (lastNum == 9  && digits.length > i) {
            digits[digits.length - i] = 0;
            ++i;
            lastNum = digits[digits.length - i];
        }
        if (i == digits.length && lastNum == 9) {
            int[] digitsNew = new int[digits.length + 1];
            digitsNew[0] = 1;
            digits = digitsNew;
        }else{
            digits[digits.length - i] = lastNum + 1;
        }
        return digits;
    }
}

复杂度

  • 时间复杂度:O(n),最差的情况就是遍历整个数组。
  • 空间复杂度:O(1),我们只需要几个变量记录我们的数据,比如前一个数字的大小,以及遍历的位置,以及为了扩容新创建的数组。

总结

这个题本质上就是数字加一,只不过把数字通过数组来呈现。最难处理的就是数组长度不够用的情况,其实new出来的数组的默认值就是0,所以我们直接把第一个位置修改为1即可,简单快捷,也没什么太大的难度。

都来了,点个赞再走呗!

关注WangScaler,祝你升职、加薪、不提桶!

目录
相关文章
|
存储 算法 索引
怒刷力扣(环形链表)
没想到曾经的寓言故事龟兔赛跑,还能应用在解循环的算法之中,今天是涨了见识了。
243 3
怒刷力扣(环形链表)
|
算法
怒刷力扣(出现一次的数字)
这个题不熟悉异或的同学可能找不到这个解题的方法。做了这么久的算法,发现很多算法题都能用到数学的方法进行计算,这样说可能不合适,算法本身就是数学的一种解题方法。还是感觉自身掌握的太少了。
155 4
怒刷力扣(出现一次的数字)
|
算法
怒刷力扣( 二叉树的最小深度)
这个题的坑就是没有左右子树的时候,这个节点才是叶子节点,这时候计算的结果才是根节点到叶子节点的深度。
184 4
怒刷力扣( 二叉树的最小深度)
|
程序员
怒刷力扣( 路径总和)
粗心大意往往是BUG诞生的条件,那么细心必是解决BUG的良药,做个细心的不写BUG的程序员,从避免粗心大意开始。
979 2
怒刷力扣( 路径总和)
|
算法
怒刷力扣( 相同的树)
解决这个问题题有两种,第一种思路深度遍历更加直观明了,不会第二种的就学会第一种。能都掌握自然是更好。
74 1
怒刷力扣( 相同的树)
|
算法
怒刷力扣(二叉树的中序遍历)
二叉树的中序遍历,前两种算法相对来说,比较容易理解,但是第三种,就需要自己思考思考了,想明白了其实也并不是很难。
117 1
怒刷力扣(二叉树的中序遍历)
怒刷力扣(删除排序链表中的重复元素)
单链表是我们在数据结构中非常常见的链表,那么最简单的删除链表元素你会吗?什么so easy?那下一篇?
144 1
怒刷力扣(删除排序链表中的重复元素)
|
存储 算法
怒刷力扣(最大子数组和)
动态规划法试图仅仅解决每个子问题一次,从而减少计算量,一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。
113 1
怒刷力扣(最大子数组和)
|
算法
怒刷力扣(买卖股票的最佳时机)
这个题本质就是分两步,第一步就是找到最低价即买入时机。找到买入时机之后则是对比利润找到卖出时机。解决这两步,答案就出来了。
108 1
|
算法
怒刷力扣(验证回文串)
双指针算法,不是第一次用了,这个题使用双指针算法能提高近一半的效率,看见字符串就习惯性的对字符串进行处理。
102 0
怒刷力扣(验证回文串)