[LeetCode] 415. Add Strings

轉自 LeetCode

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

<Solution>
這題比較麻煩的是不能使用 atoi 這種函數來處理，必須自己來做轉換

最簡單的方法就是減掉字元 '0'，然後把差值用 int 存起來就可以

解題概念如下

• 每個字串都從最後開始

• 如果長度不夠，就補0

• 每次相加要記得進位的部分

• 最後回傳答案時，如果進位部分不是 0，那記得加個前綴 "1" (因為只有兩數相加，最多進位1)

code 如下

	class Solution {
	public:
	string addStrings(string num1, string num2) {
	int index_1 = num1.length() - 1;
	int index_2 = num2.length() - 1;
	int carry = 0;
	string ans;
	while(index_1 > -1 || index_2 > -1) {
	int digit_1 = (index_1 >= 0) ? num1[index_1--] - '0' : 0;
	int digit_2 = (index_2 >= 0) ? num2[index_2--] - '0' : 0;
	int sum = digit_1 + digit_2 + carry;
	//> put digit into string
	ans.insert(ans.begin(), (sum % 10) + '0');
	carry = (sum > 9) ? sum / 10 : 0;
	}
	return (carry != 0) ? "1" + ans : ans;
	}
	};

view raw addString.cpp hosted with ❤ by GitHub