加一

2018-06-06

加一

给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。

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

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

示例 1:

1
2
3

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

示例 2:

1
2
3

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

思路：一开始想到了将数组转换成10进制数加1后在转换成数组，但是在数组长度较长时此时的整数过大，不方便计算，但是也不失为一种思路，贴上代码如下。

/**
	 * 这是借助十进制数来做运算，再转为数组的方法，在数组较大时不够用了
	 * @param digits
	 * @return
	 */
	public static int[] plusOne(int[] digits) {
		  int len=digits.length;
	      long number=0;
	        for(int i=0;i<len;i++){
	            number+=digits[i]*Math.pow(10,len-1-i);
	        }
	        number+=1;
	        int count=0;
	        long temp=number;
	        while(temp>0){
	            temp=temp/10;
	            count++;
	        }
	        int [] res=new int[count];
	        for(int j=count-1;j>=0;j--){
	            int t=(int)(number%10);
	            number=number/10;
	            res[j]=t;
	        }
	        
	        return res;
    }

后来发现上面的思路局限性很大，所以索性另寻他法，就从最基本的加法来模拟，当前元素为9，且有进位，就将当前元素置0，前一位加一，循环直到首位。为了方便循环的建立，我们将进一位用10来表示，可以有效控制循环不出错，且省略进位变量，代码如下:

class Solution {
    public int[] plusOne(int[] digits) {
      int len=digits.length;
	        int i=len-1;    
	        if(digits[i]<9){
	            digits[i]+=1;
	            return digits;
	        }
	        //当数组为单个元素9时的特殊情况
	        if(len==1 && digits[0]==9) {
	        	int [] tmp=new int[2];
	        	tmp[0]=1;
	        	return tmp;
	        }
	        /**
	         * 当数组长度大于1时
	         */
	        //将最后一位为9的数加一进入循环判断
	        if(digits[i]==9) {
	        	digits[i]++;
	        }
	        //只有当当前的数组元素值为10的元素才会进位做循环加法
	        while(digits[i]==10 && i>=0){
	        	if(i==0) {
	        		int [] res=new int[len+1];
		     	    res[0]=1;
		     	    return res;
	        	}
	        	if(i>0) {
		        	digits[i]=0;
	            	digits[i-1]+=1;
	            	i--;
	            }
	        }
	       
	        return digits;
    }
}