這題讓計算兩個字符串相乘并且不能使用內(nèi)置的庫函數(shù)。如果是單個數(shù)字乘以一個字符串，可以使用兩個指針一個記錄相乘的結(jié)果，一個記錄進(jìn)位的值，然后不停的把結(jié)果保存下來即可，如下圖所示：

如果是多位數(shù)字相乘也可以參照單個數(shù)字相乘的步驟，每次使用乘數(shù)中的其中一位和被乘數(shù)相乘。這里的關(guān)鍵點(diǎn)是找出相乘之后應(yīng)該存放的位置，我們使用一個一維數(shù)組來記錄。

如下圖所示，如果被乘數(shù)的第 i 位（從右邊數(shù)）和乘數(shù)的第 j 位（從右邊數(shù)）相乘，相乘的結(jié)果應(yīng)該放到數(shù)組的第 i+j 位（從右邊數(shù)），注意存放的時候還要加上數(shù)組中原來的值，如果結(jié)果大于等于 10 ，要取個位數(shù)字，然后往前進(jìn)位。

因為字符串的讀取都是從左邊開始讀取的，而字符串的左邊是最高位，最右邊才是個位，所以我們要逆序遍歷字符串，對于數(shù)組的存儲我們選擇從右邊開始存儲，因為相乘的結(jié)果沒有前導(dǎo) 0 ，最后我們把數(shù)組轉(zhuǎn)化為字符串的時候可以跳過前面的 0 。

    public String solve(String s, String t) {
        // 兩個字符串的長度
        int len1 = s.length(), len2 = t.length();
        // 相乘的結(jié)果存儲到數(shù)組中
        int[] mulArr = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                // 兩個數(shù)字相乘
                int mul = (s.charAt(i) - '0') * (t.charAt(j) - '0');
                int curIndex = i + j + 1;// 當(dāng)前數(shù)字存放的位置
                int carryIndex = curIndex - 1;// 前面進(jìn)位的位置
                int sum = mul + mulArr[curIndex];
                mulArr[carryIndex] += sum / 10;// 進(jìn)位的值
                mulArr[curIndex] = sum % 10;// 當(dāng)前位的值
            }
        }
        // 數(shù)組轉(zhuǎn)字符串
        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();
        // 相乘的結(jié)果存儲到數(shù)組中
        vector<int> mulArr(len1 + len2, 0);
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                // 兩個數(shù)字相乘
                int mul = (s[i] - '0') * (t[j] - '0');
                int curIndex = i + j + 1;// 當(dāng)前數(shù)字存放的位置
                int carryIndex = curIndex - 1;// 前面進(jìn)位的位置
                int sum = mul + mulArr[curIndex];
                mulArr[carryIndex] += sum / 10;// 進(jìn)位的值
                mulArr[curIndex] = sum % 10;// 當(dāng)前位的值
            }
        }
        // 數(shù)組轉(zhuǎn)字符串
        string ans;
        for (int num: mulArr) {
            // 跳過前面的0
            if (ans.empty() && num == 0)
                continue;
            ans += to_string(num);
        }
        return ans.empty() ? "0" : ans;
    }

各大廠算法面試題已經(jīng)整理好了，請看這里：《算法專欄》