1. 首页
  2. Leetcode经典148题

leetCode-66-Plus-One

题目描述(简单难度)

leetCode-66-Plus-One

数组代表一个数字,[ 1, 2, 3 ] 就代表 123,然后给它加上 1,输出新的数组。数组每个位置只保存 1 位,也就是 0 到 9。

解法一 递归

先用递归,好理解一些。

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

private int[] plusOneAtIndex(int[] digits, int index) {
    //说明每一位都是 9 
    if (index < 0) {
        //新建一个更大的数组,最高位赋值为 1
        int[] ans = new int[digits.length + 1];
        ans[0] = 1;
        //其他位赋值为 0,因为 java 里默认是 0,所以不需要管了 
        return ans;
    }
    //如果当前位小于 9,直接加 1 返回
    if (digits[index] < 9) {
        digits[index] += 1;
        return digits;
    }

    //否则的话当前位置为 0,
    digits[index] = 0;
    //考虑给前一位加 1
    return plusOneAtIndex(digits, index - 1);

}

时间复杂度:O(n)。

空间复杂度:

解法二 迭代

上边的递归,属于尾递归,完全没必要压栈,直接改成迭代的形式吧。

public int[] plusOne(int[] digits) {
    //从最低位遍历
    for (int i = digits.length - 1; i >= 0; i--) {
        //小于 9 的话,直接加 1,结束循环
        if (digits[i] < 9) {
            digits[i] += 1;
            break;
        } 
        //否则的话置为 0
        digits[i] = 0; 
    }
    //最高位如果置为 0 了,说明最高位产生了进位
    if (digits[0] == 0) {
        int[] ans = new int[digits.length + 1];
        ans[0] = 1; 
        digits = ans;
    }
    return digits;
}

时间复杂度:O(n)。

空间复杂度:

很简单的一道题,理解题意就可以了。有的编译器不进行尾递归优化,他遇到这种尾递归还是不停压栈压栈压栈,所以这种简单的我们直接用迭代就行。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-66-Plus-One

链接:https://www.javajike.com/article/3203.html

« leetCode-65-Valid-Number
leetCode-67-Add Binary»

相关推荐

QR code