LeetCode #66 Plus One 加上一

Klook.com
文章觀看次數: 301

英文原文如下

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.

中文翻譯

給予一個用整數陣列 digits 表示的大整數，其中每個 digits[i] 是該整數的第 i 位數字。 這些數字按從最高位到最低位的左到右順序排列。 這個大整數不包含前導 0 (ex : 只能有 1234，不會有 01234)

將這個大整數增加一，並返回其結果陣列。

範例及題目限制

沒有甚麼特別的說明

只是可以看到 [9] +1後變成 10，所以陣列就要用兩位來顯示，有進位問題的要注意

解題思路

這一題中，很明顯要採用反向迴圈的方式 (也就是從陣列最後一位 – 個位數字開始)

在每一次遞迴中，要是加總等於10，代表要進位，就要繼續往前遞迴

而如果不到，則可以將遞迴停下，並將結果回傳

那有甚麼特殊狀況呢? 那出現在當陣列所有數字用完依然需要進位的時候

像是範例的 9 、999…等狀況，需要在原本的陣列最前方插入一個新的元素 1

C# 解決方案

方案1

public class Solution {
    public int[] PlusOne(int[] digits) {

        int len =  digits.Length;
        int num;
        int add = 1;

        for(int i = len-1;i>=0;i--)
        {
            num = digits[i]+add;
            if(num == 10)
            {
                digits[i] = 0;
            }
            else
            {
                digits[i] = num;
                return digits;
            }
        }

        int[] newDigits = new int[digits.Length + 1];

        newDigits[0] = 1;
        Array.Copy(digits, 0, newDigits, 1, digits.Length);

        return newDigits;

    }
}

若需要增加一個元素在最前面，用Array.copy方式重做一個陣列並回傳

Java解決方案

方案1

class Solution {
    public int[] plusOne(int[] digits) {
        int len =  digits.length;
        int num;
        int add = 1;

        for(int i = len-1;i>=0;i--)
        {
            num = digits[i]+add;
            if(num == 10)
            {
                digits[i] = 0;
            }
            else
            {
                digits[i] = num;
                return digits;
            }
        }

        int[] newDigits = new int[digits.length + 1];

        newDigits[0] = 1;
        System.arraycopy(digits, 0, newDigits, 1, digits.length);

        return newDigits;
    }
}

Python3 解決方案

方案1

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

        for i in range(len(digits)-1,-1,-1):
            num = digits[i]+add
            if(num == 10):
                digits[i] = 0
            else:
                digits[i] = num
                return digits
        
        digits.insert(0,1)
        return digits

Python 比較快樂，直接insert在List前面就好了

JavaScript 解決方案

方案1

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
        var len =  digits.length;
        var num;
        var add = 1;

        for(let i = len-1;i>=0;i--)
        {
            num = digits[i]+add;
            if(num == 10)
            {
                digits[i] = 0;
            }
            else
            {
                digits[i] = num;
                return digits;
            }
        }

        digits.unshift(1);
        return digits;
};

在JavaScript中，剛好可以用到不久前介紹到的語法 – unshift

詳細介紹可以看這裡 ➡ JavaScript 如何操作陣列第一個元素 – shift( ) 與 unshift( )

結論

算是一個蠻簡單的問題，但考驗了兩件事

第一是細心與否，雖然範例就有，但進位問題還是需要特別注意的

第二則是對各語言語法的熟悉度，需要知道如何在陣列最前方新增元素~

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Plus One – LeetCode

其他的LeetCode文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *