大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
廢話不多說開始今天的解題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

  • 

大家明天見