原题
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字123。
示例 2:
输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字4321。
解法
思想
根据加法规则进行计算,应注意进位的处理和全是9的特殊情况
代码
- 迭代
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;
}
}
- 递归
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/