（Java）leetcode-66 Plus One

向右看齐 2022-03-02 01:11 140阅读 0赞

# 题目 #

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
    Output: [1,2,4]

Explanation: The array represents the integer 123.  
Example 2:

Input: [4,3,2,1]
    Output: [4,3,2,2]

Explanation: The array represents the integer 4321.

# 思路 #

这道题应该考察的是进位问题，给的例子不太好，应该给一个输入为`[1,9,9]`的例子才比较容易get到它的意思。  
（如果企图将数组转换为int，这样的方法在输入“表示”的数字超出int的范围时会失效）  
那么要做的就是把最后一个数字+1后处理进位的问题。  
还有一种比较特殊的情况是每一位都是9，这样需要在最后扩充数组的长度，这里用的是新建一个数组的方法。  
时间复杂度O(n)

# 代码 #

class Solution { 
        public int[] plusOne(int[] digits) { 
    
        	digits[digits.length-1]++;
        	
        	for(int i = digits.length-1;i >0; i--){ //处理进位
        		
        		if(digits[i] == 10){ 
        			digits[i] = 0;
        			digits[i-1]++;
        		}
        	}
    
        	if(digits[0] == 10){ //最高位需要进位
        		int res[] = new int[digits.length+1];//扩展数组长度
        		res[0] = 1;
        		return res;
    
        	}
        	return digits;
    	}
    }

## 提交结果 ##

Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One.  
Memory Usage: 35 MB, less than 68.72% of Java online submissions for Plus One.

# 代码2 #

讨论区里的一个解法，大同小异。不过在for循环中可以提前return。

public int[] plusOne(int[] digits) { 
            
        int n = digits.length;
        for(int i=n-1; i>=0; i--) { 
            if(digits[i] < 9) { 
                digits[i]++;
                return digits;
            }
            
            digits[i] = 0;
        }
        
        int[] newNumber = new int [n+1];
        newNumber[0] = 1;
        
        return newNumber;
    }

## 提交结果 ##

Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One.  
Memory Usage: 34.9 MB, less than 75.11% of Java online submissions for Plus One.