大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
废话不多说开始今天的解题Day~

66. Plus One

Question

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example

Example1

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example2

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example3

Input: digits = [0]
Output: [1]
Explanation: The array represents the integer 0.
Incrementing by one gives 0 + 1 = 1.
Thus, the result should be [1].

Example4

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0's.

解题

题目

首先先简单的翻译一下题目
给一个用digit阵列表示的整数(ex: 123 => [1, 2, 3])，每一个位址的数分别代表原来整数每个位数的数字，然後阵列所代表的整数不会是由0开头。
要做的事就是将整数加上1，同样用digit阵列方式表示(ex: 123+1 = 124 => [1, 2, 4])，并回传这个阵列。

Think

作法大致上是这样

• 阵列从右到左的顺序读回来，只有在第一个位址(也就是个位数)才加1，加完之後判断需不需要进位，需要的话flag_add设成True，在下一个位址的时候就会进位。
• 但是这样会有一个问题，就是在最高位是9的时候(也就是位址为0)(ex: 9 => [9] or 99 => [9, 9])，如果有进位或加1的情况会有问题，因为没有下一个位址可以进位了，所以要在额外插入一个1。

Code

Python

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        flag_add = False

        for i in range((len(digits)-1), -1, -1):
            if i == len(digits)-1:
                digits[i] += 1
            elif flag_add:
                digits[i] += 1
                
            if (digits[i]-9) > 0:
                digits[i] -= digits[i]
                flag_add = True
                if i == 0:
                    digits.insert(0, 1)
                    flag_add = False
            else:
                flag_add = False

        return digits
            
            

C

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize){
    int *result = (int*) malloc( sizeof(int) * (digitsSize+1));
    bzero(result , sizeof(int)*(digitsSize+1));

    int index_digits = 0;
    bool flag_add = false;
    
    for (int i=digitsSize-1 ; i>=0 ; i--){
        if (i == digitsSize-1){
            digits[i] += 1;
        } else if (flag_add){
            digits[i] += 1;
        }
            
        if ((digits[i]-9) > 0){
            digits[i] -= digits[i];
            flag_add = true;
            if (i == 0){
                for (int j=0 ; j<=digitsSize ; j++){
                    if (j == 0){
                        result[j] = 1;
                    } else {
                        result[j] = digits[index_digits];
                        index_digits++;
                    }
                }
                *returnSize = digitsSize+1;
                return result;
            }
                
        }else{
            flag_add = false;  
        }
            
    }
        
    result = digits;
    *returnSize = digitsSize;
    return result;
}

Result

• Python

  • 

• C

  • 

大家明天见