leetcode66-加一

原题

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

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

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

示例 1:

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

示例 2:

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

解法

思想

根据加法规则进行计算,应注意进位的处理和全是9的特殊情况

代码

  1. 迭代
class Solution {
    public int[] plusOne(int[] digits) {
        for(int i = digits.length-1;i>=0;i--){
            if(digits[i]!=9) {//不需进位
                digits[i] += 1;
                break;//什么时候不需进位即可退出
            }else {
                if (i == 0) {//首位需进位的特殊情况,需分配一个大一位的数组
                    int[] ret = new int[digits.length+1];
                    ret[0] = 1;
                    return ret;
                }
                digits[i] = 0;//不是首位,需进位
            }
        }
        return digits;
    }
}
  1. 递归
class Solution {
    public int[] plusOne(int[] digits) {
        return addOneAtPos(digits, digits.length-1);
    }

    private int[] addOneAtPos(int[] num, int pos){//在pos位上加一
        if(num[pos]!=9){//不需进位
            num[pos]+=1;
            return num;//什么时候不需进位即可返回
        } else if(pos>0){//不是首位,需进位
            num[pos]=0;
            return addOneAtPos(num, pos-1);
        } else {//首位需进位的特殊情况,需分配一个大一位的数组
            int length = num.length;
            int[] newNum = new int[length+1];
            newNum[0]=1;
            return newNum;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode66-%e5%8a%a0%e4%b8%80/

发表回复

登录后才能评论