（坚持每天都写算法）算法复习与学习part1基础算法1.8高精度乘法

　　这道知识点有点特殊，我当初在学的时候是只学了高精度*高精度，然后其他的我还没有想法，今天就来学学。

　　有大概6天没有写新博客，主要是实习面试和期末考，实习面试没有过关，姐姐朋友推荐我先去刷一下面试题，叫我重温一下之前的知识，然后去参考一下开源项目，我决定边复习边写博客，就这样吧，缺的这6天，我就复习一下我之前学过的算法题就可以了。

　　说回正题。

　　高精度乘法，之前一直没有说过什么是高精度，这里补充一下：计算机计算式子时，数字规模可能会大于数据类型给定的范围，那么这个时候我们就要就要用数组来存储这些大数字，用一位一位或者是四位四位的来格子来存储某大数字的一位数，这样的数一般就是高精度数。

　　高精度乘法分为二类，高精度*高精度，高精度*低精度。

　　高精度乘以低精度，先将高精度数字存入数组里面，然后用数组中的每一位去乘以低精度的数，这个就有个问题，如果乘出来的数很大导致long long都存不了（别忘了还有一个高精度数啊），那么就会出现溢位问题，啊，归回原点。不过为什么会有这种想法出现呢，请看代码：

#include <iostream>
#include <vector>

using namespace std;

vector <int> mul(vector <int> & A, int b) {
    vector <int> C;

    int t = 0;
    for (int i = 0; i < A.size(); i ++) {
        t += A[i] * b;       // t + A[i] * b = 7218
        C.push_back(t % 10); // 只取个位 8
        t /= 10;             // 721 看作 进位
    }

    while (t) {            // 处理最后剩余的 t
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;

    vector <int> A;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i --) {
        cout << C[i];
    }

    return 0;
}

　　代码的模板是不是很熟悉，熟悉就对了。

　　由于高精度*低精度仍然会可能拥有溢位问题，怎么产生的呢？低精度那数字虽然被分成低精度，但是仍然有可能翻车，那只要把它看成高精度的话，也就是两个数组，数组的每一个位进行相乘，就模拟我们的乘法算式一样，就不会产生结果过大（因为是一位一位地乘了）。

　　然后这个是图解，是让我看懂的图解，我直接拿来用了（有参考链接的，shwei大佬神）

 　　哦对了，还有一个问题，前导零，前导零出现的原因，唔，第一个，可能多余的C空间会为0，但是怎么说呢，C.size()最大长度是A.size()+B.size()，所以只要开到两数组长度之和就可以了，但是还有第二个，正常情况下两个高精度数相乘不会出现前导零，但是这种做法也可以适用高精度*低精度，就是怕测试数据可能会出现一个0，那么就会出现前导零，所以要加上这一句代码：

  while(C.size() > 1 && C.back() == 0) C.pop_back(); //如果乘数为零则去前导零

　　加法乘法的前导零我是没有讲到来着，加法减法也有一个类似，比如 123 - 111 = 12， 我们是逆序进行运算的， 减法函数里面是 321 - 111 = 210，但是直接输出就是012， 所以要去除前导0，具体代码逻辑看代码，大概就是在相似的位置。

　　这里是高精度*高精度代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
//吐槽：思路是对的但是杂七杂八写错，脑子里想着加括号手没动，想着要减一手直接划过去写下一个句子 ， 某一个变量设置了后面就没有初始化诸如此类
using namespace std;

vector<int> mul(vector<int> &A , vector<int> &B){
    vector<int> C(A.size() + B.size() , 0);
    int t = 0;
    
    for(int i = 0 ; i < A.size() ; i ++){
        for(int j = 0 ; j < B.size() ; j ++){
            C[i + j] += A[i] * B[j];//看一下shwei大佬的图解就懂了
        }
    }
    for(int i = 0 ; i < C.size() ; i ++){
        t += C[i];
        //这里修改一下C就可以了
        C[i] = t % 10;
        t /= 10;
    }
    
    while(C.size() > 1 && C.back() == 0) C.pop_back();//去掉前导0，我想不出有什么情况，但是就上面的代码来说，确实有可能C最后一位是0,然后再
    return C;
}
int main(){
    string a,b;
    vector<int> A,B;
    
    cin>>a>>b;
    
    for(int i = a.size() - 1; i >= 0 ;i --)A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0 ;i --)B.push_back(b[i] - '0');
    
    vector<int> C = mul(A,B);
    
    for(int i = C.size() - 1 ; i >= 0 ; i --) cout << C[i];
    
    return 0;
}

　　时间复杂度：仔细观察代码，发现有一个O(n^2)，然后也不是二分的那种跳一半，如果A和B的长度是最坏情况n，那么时间复杂度就是O(n^2)。

　　参考链接：AcWing 793. 高精度乘法 - AcWing

　　　　　　　AcWing 793. 高精度乘法 A x b 和 A x B 的模版（大数相加、大数相乘通用模板） - AcWing