算法导论总结（四）字符串运算

刷了150多道题，再来一发总结。再LeetCode中有一类题目，要求直接使用数字字符串进行运算，这类题目掌握技巧之后不容易出错，也比较简单，那么这篇博客将对这类题目进行总结，希望有所帮助。

小总结

这类题目需要注意两点：一点是进位检查，尤其是整个循环结束后，额外进行的进位检查，二是按位使用小整数运算，来直接操作字符串。

如果还有什么要注意的，就是某些情况下，在乘法时会出现开头为 ‘0’ 的数字字符串，这个时候增加一道过滤就可以了。

字符串加法

可以反序从最开始逐个相加，最后将结果反序，也可以直接从最末尾反向遍历进行操作。使用除法和取余操作来获取局部操作的结果。

字符串乘法

按照小学学的连乘法进行，这里需要注意一些技巧，如最后给出的代码中所指示的，可以一开始进行反序操作。

字符串乘法给了两份代码，第一份非常推荐，一开始就是直接产生N1+N2长度的字符串，在最后抹去最前面多余的0，这样操作效率很高。在按照连乘法进行连续的乘法加法，可以看走将一个 string x string 转化成了 char x char ，两个个位数乘法。分两层循环，在乘法过程中，每次乘法最多改变两位结果，高位采取进位模式保留。

代码

代码中有乘法和加法的操作。第一份代码为乘法，第二份代码其中调用了单独的加法子函数。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
	string multiply(string num1, string num2) {
		int N1 = num1.size();
		int N2 = num2.size();
		if (N1 == 0 || N2 == 0) return "";

		reverse(num1.begin(), num1.end());
		reverse(num2.begin(), num2.end());

		string ret(N1 + N2, '0');

		for (int i = 0; i<N1; i++) {
			int carry = 0;
			int val = num1[i] - '0';
			for (int j = 0; j<N2; j++) {
				carry += val * (num2[j] - '0') + (ret[i + j] - '0');
				ret[i + j] = carry % 10 + '0';
				carry = carry / 10;
			}
			if (carry != 0)
				ret[i + N2] = carry + '0';
		}

		reverse(ret.begin(), ret.end());

		int count = 0;
		while (count<(N1 + N2 - 1) && ret[count] == '0') {
			count++;
		}
		ret.erase(0, count);

		return ret;
	}

	string multiplyMy(string num1, string num2) {
		const int n1 = num1.size();
		const int n2 = num2.size();
		if (n1 == 0 || n2 == 0){
			return string("");
		}
		string res = "0";
		string pot = "";
		for (int i = n2 - 1; i >= 0; --i){
			string tmp;
			tmp = mpy(num1, num2[i]);
			tmp = tmp + pot;
			res = add(res, tmp);
			pot += "0";
		}
		return res;
	}

private:
	string mpy(string num, char s){
		string res;
		const int n = num.size();
		int t = s - '0';
		if (t == 0){
			return string("0");
		}
		int en = 0;
		char str[] = "0";
		for (int i = n - 1; i >= 0; --i){
			int tmp = num[i] - '0';
			tmp = tmp * t + en;
			en = tmp / 10;
			str[0] = tmp % 10 + '0';
			res = string(str) + res;
		}
		if (en){
			str[0] = en + '0';
			res = string(str) + res;
		}
		return res;
	}

	string add(string& num1, string& num2){
		const int n1 = num1.size();
		const int n2 = num2.size();
		int i = n1, j = n2;
		int k = 0;
		string res;
		char str[] = "0";
		while (i > 0 || j > 0) {
			i--;
			j--;
			if (i >= 0){
				k += (num1[i] - '0');
			}
			if (j >= 0){
				k += (num2[j] - '0');
			}
			str[0] = (k % 10 + '0');
			res = string(str) + res;
			k = k / 10;
		}
		if (k){
			str[0] = (k + '0');
			res = string(str) + res;
		}
		res = res.erase(0, res.find_first_not_of("0"));
		if (res.empty()){
			return string("0");
		}
		return res;
	}
};

int main(int argc, char *argv[]){
	Solution s;
	cout << s.multiply("0", "52") << endl;
	system("pause");
	return 0;
}