DEV Community

Cover image for Plus One
FakeStandard
FakeStandard

Posted on

Plus One

#66.Plus One

Problem statement

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 1

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].
Enter fullscreen mode Exit fullscreen mode

Example 2

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].
Enter fullscreen mode Exit fullscreen mode

Example 3

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].
Enter fullscreen mode Exit fullscreen mode

Explanation

給定一個整數並以陣列形式表示, 其整數依照常理數字規則開頭不為 0,返回該整數加一後的陣列結果

Solution

題目好理解,需要考量的地方是進位,其實也很簡單,就是一般數學的加法,先把陣列中的整數轉換成字串,再將字串合併轉換成整數,使用加法運算讓整數直接加一得到結果,最後將字串的結果轉換成整數陣列返回

public int[] PlusOne(int[] digits)
{
    string str = "";

    for (int i = 0; i < digits.Length; i++)
        str += digits[i];

    int tmp = int.Parse(str) + 1;

    str = tmp.ToString();

    int[] res = new int[str.Length];

    for (int i = 0; i < str.Length; i++)
        res[i] = int.Parse(str[i].ToString());

    return res;
}
Enter fullscreen mode Exit fullscreen mode

測試沒問題提交到 LeetCode 上,結果噴出一個錯誤 System.OverflowException: Value was either too large or small for a UInt64 ,看起來是在字串轉換成數值時大小不夠,即便換成 long 型態也會不夠,考量到這一點,我想應該要換個做法

這次我不用數值相加的運算子來做,我想要直接對陣列進行迭代,並在迭代過程中進行單一位數值的相加,以避免上述的錯誤

首先建立一個 List<int> 集合用以儲存結果,以及一個 bool 表示是否有進位,透過迴圈走訪陣列,起始值從陣列的最後一個索引開始,因為要從個位數加一,之後在往前判斷是否要進位,第一個 if 是用來判斷是否為個位數,如果成立執行相加,else 則是個位數以外的位數,else 內第一個 if else 用來判斷有沒有需要進位,其餘的地方就不加以解釋,純粹只是將結果添加到 List<int> 集合中以及紀錄需不需要進位

迴圈結束後還需要在判斷一次有沒有進位,如果有就直接添加 1,舉例 99+1=100,如果沒有這個判斷,list 裡的結果會只有 00,而不是 100

最後將 list 轉換成陣列,透過原生陣列的反轉方法將其反轉就是答案了

public int[] PlusOne(int[] digits)
{
    if (digits.Length == 0) return null;

    List<int> list = new List<int>();
    bool carry = false;

    for (int i = digits.Length - 1; i >= 0; i--)
    {
        if (i == digits.Length - 1)
        {
            if (digits[i] + 1 == 10)
            {
                list.Add(0);
                carry = true;
            }
            else
                list.Add(digits[i] + 1);
        }
        else
        {
            if (carry)
            {
                if (digits[i] + 1 == 10)
                {
                    list.Add(0);
                    carry = true;
                }
                else
                {
                    list.Add(digits[i] + 1);
                    carry = false;
                }
            }
            else
                list.Add(digits[i]);

        }
    }

    if (carry)
        list.Add(1);

    var res = list.ToArray();

    Array.Reverse(res);

    return res;
}
Enter fullscreen mode Exit fullscreen mode

我在寫這篇文章的時候覺得這樣的寫法不太好,於是我將迴圈內的第一個 if 判斷拿到迴圈外面執行,才不會每次進到迴圈都需要判斷,這樣的話迴圈的起始值要改成倒數第二個索引開始,其餘的部分沒有什麼差異

public int[] PlusOne(int[] digits)
{
    List<int> list = new List<int>();
    bool carry = false;

    int len = digits.Length - 1;

    if (digits[len] + 1 == 10)
    {
        list.Add(0);
        carry = true;
    }
    else list.Add(digits[len] + 1);

    for (int i = len - 1; i >= 0; i--)
    {
        if (carry)
        {
            if (digits[i] + 1 == 10)
                list.Add(0);
            else
            {
                list.Add(digits[i] + 1);
                carry = false;
            }
        }
        else list.Add(digits[i]);
    }

    if (carry) list.Add(1);

    var res = list.ToArray();
    Array.Reverse(res);

    return res;
}
Enter fullscreen mode Exit fullscreen mode

Reference

LeetCode Solution

GitHub Repository


Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub
or buy me a coffee ⬇️ I'd appreciate it.

Buy-me-a-coffee


Top comments (1)

Collapse
 
i386net profile image
i386net

when someone had no energy to continue writing messages in English