Plus One

#algorithms #csharp #leetcode #easy

#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].

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].

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].

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;
}

測試沒問題提交到 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;
}

我在寫這篇文章的時候覺得這樣的寫法不太好，於是我將迴圈內的第一個 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;
}