个人主页：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 <= 200num1和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;}//处理前导0while(ret.size() > 1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};