LeetCode 43 Multiply Strings

Tag: 数学类问题 LeetCode Posted on 2022-03-21 12:49:25 Edited on 2022-03-23 15:23:11 Views: 109

概述

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

解法

注意事项:

  1. 由于有溢出的风险,我们必须全程用字符串进行模拟。
  2. 涉及到 char 和 int 的相互转换,务必小心别忘记转了。
  3. 当输入为 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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/