这些题目是高精度加法和高精度乘法相关的，复习了一下就做了，没想到难住自己的是C++里面string的用法。
原题地址：
415 Add Strings：https://leetcode.com/problems/add-strings/description/
67 Add Binary： https://leetcode.com/problems/add-binary/description/
43 Multiply Strings：https://leetcode.com/problems/multiply-strings/description/
题目&解法：
1.Add String
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
- The length of both
num1andnum2is < 5100. - Both
num1andnum2contains only digits0-9. - Both
num1andnum2does not contain any leading zero. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
高精度加法其实很简单，先把传入的string颠倒一下，然后相加，遇到大于10的进位。自己的写法有点复杂，多了许多无谓的if判断条件，因此在网上找到了一份非常简洁的代码，不得不说从中学到了许多，比如len1和len2的使用，while处||，循环里面再判断i是否分别小于len1,len2，比我原来的代码不知道高到哪儿去了；还有用了flag来储存进位，还有val变量的使用：
class Solution {
public:
string reverse(string num) {
int len = num.size();
for (int i = ; i <= (len - ) / ; i++) {
char temp = num[i];
num[i] = num[len - i - ];
num[len - i - ] = temp;
}
return num;
}
string addStrings(string num1, string num2) {
string ans;
num1 = reverse(num1);
num2 = reverse(num2);
int i = , len1 = num1.size(), len2 = num2.size(), flag = ;
while (i < len1 || i < len2) {
int val = ;
if (i < len1) val += num1[i] - '';
if (i < len2) val += num2[i] - '';
ans += (val + flag) % + '';
flag = (val + flag) / ;
i++;
}
if (flag) ans += '';
ans = reverse(ans);
return ans;
}
};
值得注意的是，其实reverse函数是不需要自己写的，可以直接调用：
void reverse(s.begin(), s.end());
2.Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
这里其实用的就是高精度加法的思想，直接把上面的代码中的10改为2就行了。
3.Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
- The length of both
num1andnum2is < 110. - Both
num1andnum2contains only digits0-9. - Both
num1andnum2does not contain any leading zero. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
这题就是高精度乘法了，具体的原理省略掉，说一些我认为以后复习时，比较容易让我重新记起的点：
（1）要先对传入的字符串进行颠倒（这个高精度加法和乘法都一样的）
（2）要明白，num1[i]与num2[j]相乘，影响的肯定是结果的i+j位（先不管进位）（都从第0位算起）
（3）进位要先处理当前位的下一位，再处理当前位，像这样：
a[i + j + ] += a[i + j] / ;
a[i + j] %= ;
（4）我们不知道结果究竟有几位，因此要进行判断，以前我的做法是先循环一遍，遇到为0的就break；现在想到一种简单一点的方法：
int flag = a[num1.size() + num2.size() - ];
int len = flag == ? num1.size() + num2.size() - : num1.size() + num2.size();
for (int i = len - ; i >= ; i--) {
ans += a[i] + '';
}
完整代码如下：
class Solution {
public:
string reverse(string num) {
int len = num.size();
for (int i = ; i <= (len - ) / ; i++) {
char temp = num[i];
num[i] = num[len - i - ];
num[len - i - ] = temp;
}
return num;
}
string multiply(string num1, string num2) {
string ans = "";
if (num1 == "" || num2 == "") {
return "";
}
int a[] = {};
num1 = reverse(num1);
num2 = reverse(num2);
for (int i = ; i < num1.size(); i++) {
for (int j = ; j < num2.size(); j++) {
a[i + j] += (num1[i] - '') * (num2[j] - '');
a[i + j + ] += a[i + j] / ;
a[i + j] %= ;
}
}
int flag = a[num1.size() + num2.size() - ];
int len = flag == ? num1.size() + num2.size() - : num1.size() + num2.size();
for (int i = len - ; i >= ; i--) {
ans += a[i] + '';
}
return ans;
}
};
这里最重要的是那个双层循环的地方，实在不能理解这个算法的话，记住那个地方吧。。。。。。