LeetCode 43 Multiply Strings

    
        标签：
        
            数学类问题
        
            LeetCode
        
    发布于：2022-03-21 12:49:25
    编辑于：2022-03-23 15:23:11
    浏览量：615

概述

https://leetcode.com/problems/multiply-strings/

解法

注意事项：

由于有溢出的风险，我们必须全程用字符串进行模拟。
涉及到 char 和 int 的相互转换，务必小心别忘记转了。
当输入为 0 时，给出的结果可能包含多个 0，因此需要专门对此进行处理。

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        string ans;
        int numZeros = 0;
        while (!num2.empty()) {
            char b = num2.back();
            num2.pop_back();
            string tmp = multiplyChar(num1, b);
            tmp += string(numZeros, '0');
            numZeros ++;
            ans = add(ans, tmp);
        }
        return ans;
    }
    
    string multiplyChar(string a, char& b) {
        int carry = 0;
        for (int i = a.size() - 1; i >= 0; i --) {
            int tmp = (a[i] - '0') * (b - '0') + carry;
            a[i] = tmp % 10 + '0';
            carry = tmp / 10;
        }
        if (carry != 0) {
            a = string(1, carry + '0') + a;
        }
        return a;
    }
    
    string add(string a, string b) {
        if (a.size() != b.size()) {
            if (a.size() < b.size()) {
                a = string(b.size() - a.size(), '0') + a;
            } else {
                b = string(a.size() - b.size(), '0') + b;
            }
        }
        int carry = 0;
        for (int i = a.size() - 1; i >= 0; i --) {
            int tmp = (a[i] - '0') + (b[i] - '0') + carry;
            a[i] = tmp % 10 + '0';
            carry = tmp / 10;
        }
        if (carry != 0) {
            a = string(1, carry + '0') + a;
        }
        return a;
    }
};

Links: leetcode-43-multiply-strings