#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;
}
Reference
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.
Top comments (1)
when someone had no energy to continue writing messages in English