LeetCode——66 Java之加一

题目：

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

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

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

示例1:

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

示例2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
思路：
首先思考它分为哪几种情况，一种是输入长度等于输出长度，另一种是因为加一之后进位的产生，导致输出长度大于输入长度。刚开始我的想法是分为最后一位是否为9，从而思考
是不是产生了进位，可是每一次进位并不一定导致数组空间长度发生变化。后来，我又想是不是可以把数组变为一个字符串，再把这个字符串变为整数后加1，对加1之后的结果进
行操作，最后变为数组。就当我得意的写出代码之后，输入一些数据没有问题之后在提交时出现了问题，原来我这种想法忽略了一种情况，就是输入的数组转变为整数之后，这个
整数超界了，这样就出错了。我就立马把它全转化为了long类型，结果输入又给了一个超出long类型的长度的数(例如：[7,2,8,5,0,9,1,2,9,5,3,6,6,7,3,2,8,4,3,7,9,5,7,7,4,7,4,9,4,7,0,1,1,1,7,4,0,0,6])，
妈呀，我意识到这种方法是不行的，自己在那瞎折腾了半天。不
过我还是把自己的错误代码先贴出来吧，给自己一个提醒。好了，接下来换思路吧，后附正确代码。
错误代码示例：（主要原因，数组转变为String类型，之后再转换为int,long类型都会出现超界的问题。）

class Solution1 {
    public int[] plusOne(int[] digits) {
        StringBuffer buf=new StringBuffer();
        long temp=0l;
        long temp1=0l;
        int n=0;   
        for(int i=0;i<digits.length;i++){
            buf.append(String.valueOf(digits[i]));    
         }
        try{
             temp=Long.parseLong(buf.toString())+1;
             System.out.println(temp);
        }catch(NumberFormatException e){
           e.printStackTrace();
        }       
             temp1=temp;
             while(temp1>0){
                temp1/=10;
                n++;
             }
              int num[]=new int[n];
              for(int j=n-1;j>=0;j--){
                  long pop=temp%10;
                  temp/=10;
                  num[j]=(int)pop;
              }
             return num;                           
    }
}

正确思路：转换为字符串成不行的话，那就硬着头皮来，想想进位或者不进位过程吧。首先确定的是数组最后一位要加1，而这个加1引起了后续一系列变化。如果加完1

之后这个数小于10，就很好办，顺利输出就行，如果大于10，那这一位就要变为0，它的前一位就要加上1，那它的前1位加1势必会和刚刚最后一位加1引起一样的变化，

考虑的方面是一样的，所以呢，这里面是需要一个索引变动，来依次考虑数字的变化。最后，需要考虑的位数都考虑完了，那就要输出了，如果第0位被进位了，那输出

的结果是一个1，后面一堆0，此时，输出的数组长度也会比输入数组长度多1。用到的数组复制方法：System.arraycopy(src,srcPos,dest,destPos,length)。

正确代码：

class Solution {
    public int[] plusOne(int[] digits) {
      digits[digits.length-1]+=1;
         for(int i=digits.length-1;i>=0;i--){
             if(digits[i]<10){
                 return digits;
             }else{
                 digits[i]=0;
                 if(i!=0)
                 digits[i-1]+=1;
             }
         }
        int[] res=new int[digits.length+1];
        res[0]=1;
        System.arraycopy(digits,0,res,1,digits.length);
        return res;
    }
}

优质内容筛选与推荐>>
1、多对多的属性对应表如何做按照类别的多属性匹配搜索
2、PyCharm Professional 2016.1 破解激活
3、TFS中查看我的所有签入迁出记录 TFS 怎么查看所有的修改
4、Cocos2dx相关辅助宏
5、[spacemacs]anaconda自动补全不工作

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看