[C++知识库]大数相乘（字符串相乘）

在说大数相乘问题之前，我们先来看一下在算法竞赛中使用起来非常方便快捷的C++模板类vector

1. 不定长数组vector

C语言在声明和定义一个数组时，必须要事先指定数组的长度，这就不利于数组中元素的动态增长，而C++引入了不定长数组vector，就能很好的解决这个问题，这也是vector受到广大acm竞赛选手青睐的原因所在。

vector是一个标准模板类，所以需要用vector A 或 vector B来声明一个vector，vector声明一个整数数组,而vector声明一个字符串数组。

vector各种操作：

• vector a ：定义一个int型向量a
• vector a(10)：定义一个初始化大小为10的int型向量a
• a.size()：读取大小
• a.push_back(i)：向尾部添加元素i
• a.pop_back():删除最后一个元素
• a.resize()：改变大小
• a.clear()：清空vector
• a.empty()：判断是否为空

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int> a;
	int x = 1, y = 2, z = 3; 
	a.push_back(x);
	a.push_back(y);
	a.push_back(z);
    
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << ' ';
	}
	cout << endl;
	a.pop_back();
	cout << a.size() << endl;
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << ' ';
	}
	return 0;
}

2. 字符串相乘(大数相乘)

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

示例1：
输入: num1 = “2”, num2 = “3”
输出: “6”

示例2：
输入: num1 = “123”, num2 = “456”
输出: “56088”

说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multiply-strings

小常识：一个m位整数和一个n位整数相乘，得到的乘积位数最大为(m+n)

代码如下：

class Solution {
public:
	vector<int> mul(vector<int> &A, vector<int> &B) {
		vector<int> C(A.size() + B.size(), 0);  //初始化C向量，长度为A、B长度之和，每个元素的值均为0

		int i, j;
		for (j = 0; j < B.size(); j++) {
			for (i = 0; i < A.size(); i++) {
				C[i + j] += A[i] * B[j]; // C存放乘积
			}
		}

		//处理进位
		int extra = 0;
		for (i = 0; i < C.size(); i++) {
			extra += C[i];
			C[i] = extra % 10;
			extra = extra / 10;
		}

		//去0(乘积的真实结果可能没有6位 或者 一个非零数与零相乘，所以要把最高位的0去掉)
		while (C.size() > 1 && C.back() == 0)   //若只有一个0则无需去0
			C.pop_back();

		return C;
	}
	

	string multiply(string num1, string num2) {
		// 例如 num1="123",num2="456"
		vector<int> A;
		vector<int> B;
		int i;


		//倒着存储字符串中的每个数字，方便计算
		for (i = num1.size() - 1; i >= 0; i--)
			A.push_back(num1[i] - '0');  // A=[3,2,1]
		for (i = num2.size() - 1; i >= 0; i--)
			B.push_back(num2[i] - '0');  // B=[6,5,4]

		vector<int> C = mul(A, B);
		string str = "";
		for (i = C.size() - 1; i >= 0; i--)
			str += to_string(C[i]);

		return str; 
	}
};

好久没写代码了，手都生疏了，太不容易了，在Leetcode上提交了4次才通过，呜呜呜以后一定勤奋撸代码，葱丫！