本文主要是介绍43字符串相乘（暴力模拟竖式乘法计算过程），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
2、示例
输入: num1 = "2", num2 = "3"
输出: "6"
输入: num1 = "123", num2 = "456"
输出: "56088"
3、题解
基本思想：暴力模拟竖式乘法计算过程，两重循环第一重循环读取num2中某个数与第二重循环读取num1所有数相乘这就是一层结果layer，然后将每一层结果加到res最后返回res的逆序。
- layer为num2中某个数与num1所有数相乘结果也就是一层结果，将每一层结果加到res就是最后返回结果。cur是num1中某个数字和num2某个数字相乘得到结果的个位数。temp临时num1和num2某两个数字对应相乘结果，carry是结果的十位数也就是进位数。
- 如果num1和num2中有一个是0，结果返回0
- 第一重循环读取num2中某个数，每一层layer初始化为空，根据num2中读取数所在的位数，layer添加相应个数的0，进位数carry初始化为0
- 第二重循环读取num1所有数与num2读取的数num2[i]相乘得到这一层结果layer
- 如果num2[i]与num1所有数相乘后还有进位，加到layer后面
- 然后将每一层结果layer加到res上
- 可能layer的长度大于res的长度，layer大于res长度的部分加到res后面
- 考虑可能最后还有进位
- 最后返回res的逆序
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:string multiply(string num1, string num2) {int l1 = num1.size();int l2 = num2.size();string res(l1 + l2, '0');for(int i=l1-1; i>=0; i--) {for(int j=l2-1; j>=0; j--) {int tmp = (res[i+j+1] - '0') + (num1[i] - '0')*(num2[j] - '0'); res[i+j+1] = tmp%10 + '0';res[i+j] += tmp/10;}}for(int i = 0; i < l1+l2; i++){if(res[i]!='0') return res.substr(i);}return "0"; }
};
class Solution {
public:string multiply(string num1, string num2) {//基本思想：暴力模拟竖式乘法计算过程，两重循环第一重循环读取num2中某个数与第二重循环读取num1所有数相乘这就是一层结果layer，然后将每一层结果加到res最后返回res的逆序//layer为num2中某个数与num1所有数相乘结果也就是一层结果，将每一层结果加到res就是最后返回结果string res, layer;//cur是num1中某个数字和num2某个数字相乘得到结果的个位数char cur;//temp临时num1和num2某两个数字对应相乘结果，carry是结果的十位数也就是进位数int i, j, carry, temp, k;//如果num1和num2中有一个是0，结果返回0if (num1 == "0" || num2 == "0")return "0";//第一重循环读取num2中某个数for (i = num2.size() - 1; i >= 0; i--){//每一层layer初始化为空layer = "";//根据num2中读取数所在的位数，layer添加相应个数的0for (k = 0; k < num2.size() - 1 - i; k++)layer.push_back('0');//进位数carry初始化为0carry = 0;//第二重循环读取num1所有数与num2读取的数num2[i]相乘得到这一层结果layerfor (j = num1.size() - 1; j >= 0; j--){temp = (num2[i] - '0') * (num1[j] - '0') + carry;cur = temp % 10 + '0';carry = temp / 10;layer.push_back(cur); }//如果num2[i]与num1所有数相乘后还有进位，加到layer后面if (carry > 0)layer.push_back(carry + '0');carry = 0;//然后将每一层结果layer加到res上for (k = 0; k < res.size() && k < layer.size(); k++){temp = (res[k] - '0') + (layer[k] - '0') + carry;res[k] = temp % 10 + '0';carry = temp / 10;}//可能layer的长度大于res的长度，layer大于res长度的部分加到res后面while (k < layer.size()){temp = layer[k] - '0' + carry;res.push_back(temp % 10 + '0');carry = temp / 10;k++;}//考虑可能最后还有进位if (carry == 1)res.push_back('1');}//最后返回res的逆序reverse(res.begin(), res.end());return res;}
};
int main()
{Solution solute;string nums1 = "23";string nums2 = "112";cout << solute.multiply(nums1, nums2) << endl;return 0;
}
这篇关于43字符串相乘（暴力模拟竖式乘法计算过程）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
