【算法题】大数乘法

这题让计算两个字符串相乘并且不能使用内置的库函数。如果是单个数字乘以一个字符串，可以使用两个指针一个记录相乘的结果，一个记录进位的值，然后不停的把结果保存下来即可，如下图所示：

如果是多位数字相乘也可以参照单个数字相乘的步骤，每次使用乘数中的其中一位和被乘数相乘。这里的关键点是找出相乘之后应该存放的位置，我们使用一个一维数组来记录。

如下图所示，如果被乘数的第 i 位（从右边数）和乘数的第 j 位（从右边数）相乘，相乘的结果应该放到数组的第 i+j 位（从右边数），注意存放的时候还要加上数组中原来的值，如果结果大于等于 10 ，要取个位数字，然后往前进位。

因为字符串的读取都是从左边开始读取的，而字符串的左边是最高位，最右边才是个位，所以我们要逆序遍历字符串，对于数组的存储我们选择从右边开始存储，因为相乘的结果没有前导 0 ，最后我们把数组转化为字符串的时候可以跳过前面的 0 。

    public String solve(String s, String t) {
        // 两个字符串的长度
        int len1 = s.length(), len2 = t.length();
        // 相乘的结果存储到数组中
        int[] mulArr = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                // 两个数字相乘
                int mul = (s.charAt(i) - '0') * (t.charAt(j) - '0');
                int curIndex = i + j + 1;// 当前数字存放的位置
                int carryIndex = curIndex - 1;// 前面进位的位置
                int sum = mul + mulArr[curIndex];
                mulArr[carryIndex] += sum / 10;// 进位的值
                mulArr[curIndex] = sum % 10;// 当前位的值
            }
        }
        // 数组转字符串
        StringBuilder ans = new StringBuilder();
        for (int num : mulArr) {
            // 跳过前面的0
            if (ans.length() == 0 && num == 0)
                continue;
            ans.append(num);
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }

public:
    string solve(string s, string t) {
        // 两个字符串的长度
        int len1 = s.length(), len2 = t.length();
        // 相乘的结果存储到数组中
        vector<int> mulArr(len1 + len2, 0);
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                // 两个数字相乘
                int mul = (s[i] - '0') * (t[j] - '0');
                int curIndex = i + j + 1;// 当前数字存放的位置
                int carryIndex = curIndex - 1;// 前面进位的位置
                int sum = mul + mulArr[curIndex];
                mulArr[carryIndex] += sum / 10;// 进位的值
                mulArr[curIndex] = sum % 10;// 当前位的值
            }
        }
        // 数组转字符串
        string ans;
        for (int num: mulArr) {
            // 跳过前面的0
            if (ans.empty() && num == 0)
                continue;
            ans += to_string(num);
        }
        return ans.empty() ? "0" : ans;
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》