DEV Community

Cover image for Plus One
FakeStandard
FakeStandard

Posted on • Edited on

1

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 ⭐ I'd appreciate it.


AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (1)

Collapse
 
i386net profile image
i386net

when someone had no energy to continue writing messages in English

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay