LeetCode——66 Java之加一

痛定思痛。 2022-10-03 00:59 171阅读 0赞

题目：

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

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

你可以假设除了整数 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;
        }
    }

转载于:https://www.cnblogs.com/xiayanjiao/p/10284646.html