题解 | #字符串相乘#

题目链接

字符串相乘

题目描述

给定两个数字（0-9）字符串（长度不限），求它们的乘积。

解题思路

由于输入的字符串长度不限，代表的数字可能会非常大，超出标准整数类型（如 long long）的表示范围。因此，我们需要使用高精度算法来模拟手动乘法的过程。

核心思想是，将乘法计算的结果存储在一个整数数组中，数组的每一位对应结果的一个数位。

算法步骤：

处理特殊情况：

如果任意一个输入字符串是 "0"，则乘积直接为 "0"。
准备结果数组：

两个长度分别为 $m$ 和 $n$ 的数字相乘，其结果的长度最多为 $m+n$ 。因此，我们可以创建一个长度为 $m+n$ 的整数数组 res，并全部初始化为 0，用于存储计算结果的每一位。
模拟乘法：

我们从两个数字字符串的末尾开始，向前遍历，模拟竖式乘法。
- 遍历第一个数 num1 的每一位 num1[i]（从右到左）。
- 在内部，遍历第二个数 num2 的每一位 num2[j]（从右到左）。
- num1[i] 和 num2[j] 相乘的结果，应该被加到 res 数组的 [i+j, i+j+1] 这两位上。
- 计算与进位：
  - product = (num1[i] - '0') * (num2[j] - '0')。
  - p1 = i + j, p2 = i + j + 1 是结果中受影响的两个位置。
  - sum = product + res[p2] (乘积加上原来 p2 位置的数，可能是上一轮的进位)。
  - 更新 p2 位置的值：res[p2] = sum % 10。
  - 将进位加到 p1 位置上：res[p1] += sum / 10。
- 双重循环结束后，res 数组中就以逆序的形式存储了乘积的每一位数字。
格式化输出：
- 遍历 res 数组，找到第一个非零数字的位置（为了跳过可能存在的前导零）。
- 从这个非零数字开始，将数组中的所有数字拼接成一个字符串，即为最终答案。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string num1, num2;
    cin >> num1 >> num2;

    if (num1 == "0" || num2 == "0") {
        cout << "0" << endl;
        return 0;
    }

    int m = num1.length();
    int n = num2.length();
    vector<int> res(m + n, 0);

    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int d1 = num1[i] - '0';
            int d2 = num2[j] - '0';
            int product = d1 * d2;
            
            int p1 = i + j;
            int p2 = i + j + 1;
            
            int sum = product + res[p2];
            res[p2] = sum % 10;
            res[p1] += sum / 10;
        }
    }

    int start_index = 0;
    while (start_index < res.size() && res[start_index] == 0) {
        start_index++;
    }

    stringstream ss;
    for (int i = start_index; i < res.size(); i++) {
        ss << res[i];
    }
    
    cout << ss.str() << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String num1 = sc.nextLine();
        String num2 = sc.nextLine();

        if (num1.equals("0") || num2.equals("0")) {
            System.out.println("0");
            return;
        }

        int m = num1.length();
        int n = num2.length();
        int[] res = new int[m + n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int d1 = num1.charAt(i) - '0';
                int d2 = num2.charAt(j) - '0';
                int product = d1 * d2;

                int p1 = i + j;
                int p2 = i + j + 1;

                int sum = product + res[p2];
                res[p2] = sum % 10;
                res[p1] += sum / 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        int startIndex = 0;
        while (startIndex < res.length && res[startIndex] == 0) {
            startIndex++;
        }

        for (int i = startIndex; i < res.length; i++) {
            sb.append(res[i]);
        }
        
        System.out.println(sb.length() == 0 ? "0" : sb.toString());
    }
}

import sys

def solve():
    try:
        num1 = sys.stdin.readline().strip()
        num2 = sys.stdin.readline().strip()

        if num1 == "0" or num2 == "0":
            print("0")
            return

        m, n = len(num1), len(num2)
        res = [0] * (m + n)

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                d1 = int(num1[i])
                d2 = int(num2[j])
                product = d1 * d2
                
                p1, p2 = i + j, i + j + 1
                
                total_sum = product + res[p2]
                res[p2] = total_sum % 10
                res[p1] += total_sum // 10

        start_index = 0
        while start_index < len(res) and res[start_index] == 0:
            start_index += 1
        
        result_str = "".join(map(str, res[start_index:]))
        print(result_str)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：高精度乘法、模拟
时间复杂度： $\mathcal{O}(m \cdot n)$ ，其中 $m$ 和 $n$ 分别是两个输入字符串的长度。我们需要一个双重循环来计算每一位的乘积。
空间复杂度： $\mathcal{O}(m+n)$ 。主要的空间开销来自于存储结果的数组，其长度为 $m+n$ 。