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.

---

实现字符串加法，按照小学老师教的，从低到高一位一位加，注意保留进位。这题仔细一点，然后调试两次就差不多能AC了。 代码中需要注意运算符优先级，加法优先级高于三目运算符，所以三目运算符要加括号。 完整代码如下： [cpp] class Solution { public: string addStrings(string num1, string num2) { string ans = ""; int i = num1.size() – 1, j = num2.size() – 1; bool carry = false; while (i >= 0 || j >= 0) { int sum = 0; if (i < 0)sum = (num2[j] – ‘0’) + (carry ? 1 : 0); else if (j < 0)sum = (num1[i] – ‘0’) + (carry ? 1 : 0); else sum = (num1[i] – ‘0’) + (num2[j] – ‘0’) + (carry ? 1 : 0); //注意运算符优先级，要加括号 if (sum >= 10) { carry = true; sum -= 10; } else { carry = false; } char c = ‘0’ + sum; ans = c + ans; i–; j–; } if (carry)return ‘1’ + ans; else return ans; } }; [/cpp] 本代码提交AC，用时12MS。]]>

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

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

---

把两个以字符串形式存储的非负整数相乘起来，输出字符串结果。很考验基本功的一个题目，使用小学学过的乘法来做，一位一位相乘，然后把每一位相乘的结果加起来得到最终结果。 比如35*423，先调个位置423*35，确保num2长度短于num1，然后我们循环num2的每一位，比如首先5*423=2115，然后3*423=1269，但是加起来的时候要注意，1269要往前缩进一位成12690。最终结果为2115+12690=14805。 所以整个过程需要实现两个辅助函数，两个字符串相加，以及一个字符和字符串相乘的函数。完整代码如下：

class Solution {
public:
    string add(string num1, string num2)
    {
        int i = num1.size() – 1, j = num2.size() – 1;
        string ans = "";
        bool carry = false;
        while (i >= 0 || j >= 0) {
            int sum = (i >= 0 ? (num1[i] – ‘0’) : 0) + (j >= 0 ? (num2[j] – ‘0’) : 0);
            sum += carry ? 1 : 0;
            if (sum >= 10) {
                ans.push_back(sum – 10 + ‘0’);
                carry = true;
            }
            else {
                ans.push_back(sum + ‘0’);
                carry = false;
            }
            i–;
            j–;
        }
        if (carry)
            ans.push_back(‘1’);
        reverse(ans.begin(), ans.end());
        return ans;
    }
    string multiply(string num1, char c)
    {
        if (c == ‘0’)
            return "0";
        if (c == ‘1’)
            return num1;
        string ans = "";
        int i = num1.size() – 1;
        int carry = 0;
        while (i >= 0) {
            int prod = (num1[i] – ‘0’) * (c – ‘0’);
            prod += carry;
            if (prod >= 10) {
                ans.push_back(prod % 10 + ‘0’);
                carry = prod / 10;
            }
            else {
                ans.push_back(prod + ‘0’);
                carry = 0;
            }
            i–;
        }
        if (carry > 0)
            ans.push_back(carry + ‘0’);
        reverse(ans.begin(), ans.end());
        return ans;
    }
    string multiply(string num1, string num2)
    {
        if (num1.size() < num2.size()) { // 确保num1长于num2 string tmp = num2; num2 = num1; num1 = tmp; } string ans = "0"; int j = num2.size() – 1, k = 0; // k:缩进的位数 while (j >= 0) { string p = multiply(num1, num2[j]); for (int i = 0; i < k; i++) p.push_back(‘0’); ans = add(ans, p); j–; k++; } return ans; } };

本代码提交AC，用时26MS。

二刷。上述解法不够简洁，讨论区有一种很漂亮的解法：https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation/60，图片解释如下：

也就是可以算出来两个digit相乘的结果在最终结果中的下标位置，比如上图中123*45，num1的2乘以num2的4的结果是8，对应的下标分别是num1的i=1和num2的j=0，两个digit相乘结果最多可以占两位，这两位在最终结果中的下标是i+j和i+j+1，这个例子就是i+j=1,j+j+1=2，相乘结果08正好叠加在最终结果的第1和2位。
完整代码如下：

class Solution {
public:
    string multiply(string num1, string num2)
    {
        int n1 = num1.size(), n2 = num2.size();
        vector<int> ans(n1 + n2, 0);
        for (int i = n1 – 1; i >= 0; –i) {
            for (int j = n2 – 1; j >= 0; –j) {
                int mul = (num1[i] – ‘0’) * (num2[j] – ‘0’);
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + ans[p2];
                ans[p1] += sum / 10;
                ans[p2] = sum % 10;
            }
        }
        string ret = "";
        int i = 0;
        while (i < n1 + n2 && ans[i] == 0)
            ++i;
        if (i >= n1 + n2)
            return "0";
        while (i < n1 + n2) {
            ret.push_back(‘0’ + ans[i]);
            ++i;
        }
        return ret;
    }
};

本代码提交AC，用时9MS。

三刷。巧妙方法还是没记住，下面依然是小学生解法，只不过代码好看一点。

class Solution {
public:
	string SingleMultiply(string s, char c) {
		string ans = "";
		int vc = c - '0';
		int carry = 0;
		for (int i = s.size() - 1; i >= 0; --i) {
			int vs = s[i] - '0';
			int prod = vc * vs + carry;
			ans.push_back('0' + (prod % 10));
			carry = prod / 10;
		}
		if (carry > 0)ans.push_back(carry + '0');
		return ans;
	}
	string multiply(string num1, string num2) {
		int n1 = num1.size(), n2 = num2.size();
		if (n1 > n2)return multiply(num2, num1);
		if (num1 == "0")return "0";
		vector<string> prods;
		int max_len = 0;
		for (int i = n1 - 1; i >= 0; --i) {
			string prod = string(n1 - i - 1, '0') + SingleMultiply(num2, num1[i]);
			max_len = prod.size() > max_len ? prod.size() : max_len;
			prods.push_back(prod);
		}
		string ans = "";
		int carry = 0;
		for (int i = 0; i < max_len; ++i) {
			int val = 0;
			for (int j = 0; j < prods.size(); ++j) {
				if (i < prods[j].size())val += (prods[j][i] - '0');
			}
			val += carry;
			ans.push_back('0' + (val % 10));
			carry = val / 10;
		}
		if (carry > 0)ans.push_back('0' + carry);
		reverse(ans.begin(), ans.end());
		return ans;
	}
};

本代码提交AC，用时24MS。

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹,  2³¹ − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

---

题意就是要我们把整数逆序，需要注意当逆序之后超出int表示范围时，返回0。所以我们用double来保存逆序之后的整数，将其和INT_MAX比较，如果大于INT_MAX，则输出0。 完整代码如下：

class Solution {
public:
    int reverse(int x)
    {
        unsigned int y = (x > 0) ? x : -x;
        double ans = 0;
        while (y) {
            ans = ans * 10 + (y % 10);
            y = y / 10;
        }
        if (ans > INT_MAX)
            return 0;
        return x < 0 ? -ans : ans;
    }
};

本代码提交AC，用时8MS。

二刷。如果不用double存储的话，该怎么办？难就难在如何处理越界的问题。我们可以在计算y的过程中判断y是否越界，代码如下。

如果tmp=y*10+reminder>INT_MAX，有两种情况。一种情况是y*10本身就已经>INT_MAX了，此时即y>INT_MAX/10。另一种情况是y*10没>INT_MAX，是加上reminder之后大于的，由于INT_MAX=2147483647，所以如果reminder>7的话，y*10+reminder就会大于INT_MAX。INT_MIN的情况类似。另外，负数的余数也是负数，所以正负数的情况可以合并考虑。

class Solution {
public:
	int reverse(int x) {

		int y = 0;
		while (x != 0) {
			int reminder = x % 10;
			x /= 10;
			if (y > INT_MAX / 10 || (y == INT_MAX / 10 && reminder > 7))return 0;
			if (y < INT_MIN / 10 || (y == INT_MIN / 10 && reminder < -8))return 0;
			y = y * 10 + reminder;
			
		}
		return y;
	}
};

本代码提交AC，用时4MS。