iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

30天 Leetcode解題之路系列 第 8

Day 8 - Plus One

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

大家明天見/images/emoticon/emoticon29.gif


上一篇
Day 7 - Maximum Subarray
下一篇
Day 9 - Container With Most Water
系列文
30天 Leetcode解題之路30

尚未有邦友留言

立即登入留言