算法：大数加1

大数加1

• 题目描述
• 示例
• 算法实现

题目描述

给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。

将大整数加 1，并返回结果的数字数组。

示例

示例1： 输入：digits=[1,2,3]输出：[1,2,4]解释：输入数组表示数字123。 加1后得到123+1=124。 因此，结果应该是[1,2,4]。 示例2： 输入：digits=[4,3,2,1]输出：[4,3,2,2]解释：输入数组表示数字4321。 加1后得到4321+1=4322。 因此，结果应该是[4,3,2,2]。 示例3： 输入：digits=[9]输出：[1,0]解释：输入数组表示数字9。 加1得到了9+1=10。 因此，结果应该是[1,0]。 提示：1<=digits.length<=1000<=digits[i]<=9digits 不包含任何前导0。

算法实现

使用java实现的算法如下：

publicint[]plusOne(int[]digits){intindex=digits.length-1;while(index>=0){intsum=digits[index]+1;if(sum!=10){//说明不满足进1，则退出循环digits[index]=sum;break;}//如果==10 满足进1，则设置为0digits[index]=0;if(index-1<0){//判断数组是否越界break;}intpreIndex=index-1;//计算前一个数目digits[preIndex]+=1;//上一个+1，这个+1是进位导致if(digits[preIndex]!=10){//说明不满足进1，则退出循环break;}//满足进1，则设置为0digits[preIndex]=0;//计算preIndex的上一位index-=2;//注意是-2，不是-1}// end whileif(digits[0]==0){//说明原数组全部元素是9int[]result=newint[digits.length+1];result[0]=1;returnresult;}returndigits;}