突然想到解題也是一種創作吧==
就打開 Leet 來隨便抽一題 easy 看看
文組比較笨 只能 easy 勉強解一解
415. Add Strings
收兩個非負數字串 num1 與 num2
將兩個字串裡的數字加起來 回傳加總字串
不可以用內建的儲存大數字的方法 (如 BigInteger)
也不可以直接把字串轉成數字
如 "11", "123" => "134"
public class Solution {
public string AddStrings(string num1, string num2) {
// make sure num1 is always >= num2 length-wise
if (num1.Length < num2.Length)
(num1, num2) = (num2, num1);
Stack<char> chars = new Stack<char>();
bool holdingTen = false;
for (int i = 0; i < num1.Length; i++) {
int sum = num1[num1.Length - 1 - i] - '0';
if (holdingTen) {
sum += 1;
holdingTen = false;
}
if (num2.Length - 1 - i >= 0) {
sum += num2[num2.Length - 1 - i] - '0';
}
if (sum >= 10) {
holdingTen = true;
sum -= 10;
}
chars.Push((char)(sum + '0'));
}
if (holdingTen)
chars.Push('1');
return new String(chars.ToArray());
}
}
一開始覺得好像可以用 char[] 存結果
長度就是 num1 跟 num2 最長長度 + 1
但是實作過程中發現算 index 太過複雜
應該寫得出來，但寫的過程跟成品感覺會很噁心
於是決定改成用 StringBuilder
用 StringBuilder 解出來 AC 但發現時間排名很後面
看了一下前面的榜首是用 Stack
就改成用 Stack 寫，意外發現快很多
本來還以為 .ToArray() 會很慘
最快速度 128 毫秒左右，StringBuilder 就慢了 20~30 毫秒
總之學到ㄌ StringBuilder 雖然方便可是還是別亂用好
之前解題用它也是爆慢
成品 129ms 50.81% (榜首寫法copy下來跑 128ms)
37.5MB 74.27%