当前位置：首页 > article >正文

Leetcode 43 字符串相乘

article 2025/3/20 15:22:00

Leetcode43字符串相乘

- 题解1（按位计算）

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

来源：力扣（LeetCode）题目链接
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2都不包含任何前导零，除了数字0本身。

题解1（按位计算）

class Solution {
public:
    string multiply(string num1, string num2) {
        const int s1 = num1.length();
        const int s2 = num2.length();
        // 相乘结果最长s1+s2位
        vector<int> sum = vector(s1 + s2, 0);
        
        for(int i=s1-1; i>=0; i--){
            int k = num1[i] - '0';
            for(int j=s2-1; j>=0; j--){
                int f = num2[j] - '0';
                // key : 按位思想即可发现位置关系（i+j, i+j+1） --- 最重要
                int l = k*f + sum[i+j+1];
                sum[i+j] += l/10;
                sum[i+j+1] = l%10; 
            }
        }

        int i = 0;
        // 除 0
        for(; i < sum.size() && sum[i]==0; i++);
        string str("");
        for(; i<sum.size(); i++){
            str.push_back(sum[i]+'0');
        }
        // 如果结果是0 上面的循环返回的是空str
        return str.size() == 0 ? "0" : str;
    }
};