大数操作

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

 

示例 1：

输入：num1 = “11”, num2 = “123”
输出：”134”
示例 2：

输入：num1 = “456”, num2 = “77”
输出：”533”
示例 3：

输入：num1 = “0”, num2 = “0”
输出：”0”

---

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
        string ans = "";
        while (i >= 0 || j >= 0 || carry != 0){
            int a = i >= 0 ? num1[i] - '0' : 0;
            int b = j >= 0 ? num2[j] - '0' : 0;
            int result = a + b + carry;
            // 余数保留，大于10进位
            ans = to_string(result % 10) + ans;
            carry = result / 10;
            i--;
            j--;
            // cout << "i,j,carry" << i << " " << j << " " << carry << endl;
        }
        return ans;
    }
};

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

 

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

class Solution {
    string add(string num1, string num2) {
        int i = num1.size() - 1;
        int j = num2.size() - 1;
        int carry = 0;
        string ans = "";
        while (i >= 0 || j >= 0 || carry > 0){
            int a = i >= 0 ? num1[i] - '0' : 0;
            int b = j >= 0 ? num2[j] - '0' : 0;
            int result = a + b + carry;
            ans = to_string(result%10) + ans;
            carry = result/10;
            i--;
            j--;
        }
        return ans;
    }
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0"){
            return "0";
        }
        int m = num1.size();
        int n = num2.size();
        if (m == 0){
            return num2;
        }
        if (n == 0){
            return num1;
        }
        string ans;
        for (int i = m - 1; i >= 0; i--) {
            string tmp = "";
            int count = m - 1 - i;
            while (count > 0){
                tmp += '0';
                count--;
            }
            int carry = 0;
            for (int j = n - 1; j >= 0; j--){
                int a = num1[i] - '0';
                int b = num2[j] - '0';
                int result = a * b + carry;
                tmp = to_string(result%10) + tmp;
                carry = result/10;
            }
            if (carry > 0){
                tmp = to_string(carry%10) + tmp;
            }
            // cout << "i:" << i << "\t" << tmp << endl;
            ans = add(ans, tmp);
        }
        return ans;
    }
};

还有一种直接计算的方法

乘法的时候，长度为m、n的两个数相乘，结果最大为m+n+1位，两个位为i,j的数乘积所在的位置为i+j+1,进位在i+j

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0"){
            return "0";
        }
        int m = num1.size();
        int n = num2.size();
        if (m == 0){
            return num2;
        }
        if (n == 0){
            return num1;
        }
        vector<int> ansArray(m+n);
        for (int i = m - 1; i >= 0; i--) {
            int a = num1[i] - '0';
            for (int j = n - 1; j >= 0; j--) {
                int b = num2[j] - '0';
                int result = a * b + ansArray[i+j+1];
                ansArray[i+j+1] = (result % 10);
                ansArray[i+j] += (result / 10);
            }
        }
        string ans = "";
        for (int i = 0; i < ansArray.size(); i++) {
            if (i == 0 && ansArray[i] == 0) continue;
            ans += to_string(ansArray[i]);
        }
        return ans;
    }
};