字符串(4)_字符串相乘_高精度乘法

个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

字符串(4)_字符串相乘_高精度乘法

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌 

目录

1. 题目链接

2. 题目描述

3, 解法:

解法一(模拟列竖式运算):

算法思路:

代码展示:

解法二(无进位相乘): 

算法思路:

代码展示:

1. 题目链接

OJ链接 : 高精度乘法https://leetcode.cn/problems/multiply-strings/description/

2. 题目描述

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

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

示例 1:

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

示例 2:

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

提示：

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

3, 解法:

解法一(模拟列竖式运算):

算法思路:

解法一的思路很简单, 我们直接模拟小学的列竖式运算就行, 主要是要注意细节问题:

细节一 : 高位相乘的时候, 要补上'0'

细节二 : 处理前导'0'

细节三 : 注意计算结果的顺序

代码展示:

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        int n = num1.size(), m = num2.size(), t = 0;
        if(num1 == "" && num2 == "") return "";

        vector<int> tmp(m + n);

        for(int i = n - 1; i>= 0; i--)
            for(int j = m - 1; j >= 0; j--)
            {
                int current_sum = (num1[i] - '0') * (num2[j] - '0');
                int sum = current_sum + tmp[i + j + 1];

                tmp[i + j + 1] = sum % 10;
                tmp[i + j] += sum / 10;
            }

        //将结果转换成字符串
        string ret;
        for(auto num : tmp)
            if(!(ret.empty() && num == 0)) ret += num + '0'; // 如果ret为空num等于, 这个就是前导0, 舍去
            
        return ret.empty() ? "0" : ret;
    }
};

注意这里的细节特别多, 建议画画图! 

解法二(无进位相乘): 

算法思路:

 整体思路就是模拟小学列竖式计算两个数相乘的结果, 但是为了我们书写代码的方便性, 我们选择一种优化版本的, 就是在计算两数相乘的时候, 先不考虑进位, 等到所有结果计算完毕之后, 再去考虑进位. 如下图:

代码展示:

class Solution {
public:
    string multiply(string num1, string num2) 
    {
        int n = num1.size(), m = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int> tmp(m + n - 1);

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');

        //处理进位
        int t = 0, cur = 0;
        string ret;
        while(cur < m + n -1 || t)
        {
            if(cur < m + n - 1) t += tmp[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }

        //处理前导0
        while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};