（坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）

　　题目：

　　思路：这一道题其实和高精度加法的思路是差不多的，都是使用算式进行模拟。

　　重点：关于代码怎么写，在高精度加法那里还看不太出来（我也没有写），但是在高精度减法这里就完全可以看出来了。我们在加法算式里面，一般是A[i]+B[i]+t，但是也可以这么写：t+A[i]+B[i]，我们可以先写进位，然后之后对进位t进行处理就行了，而在刚开始的时候我们只要将t设置成0就可以了，0没有进位为0，那么t+A[i]+B[i]就是通用的式子，所以高精度加法可以这么写：　

 vector<int> C;
 int t = 0 ;
 for(int i = 0 ; i < A.size() || i <B.size(); i ++){
     if(i < A.size()) t += A[i];
     if(i < B.size()) t += B[i];
     C.push_back(t % 10);
     t /= 10;
 }

　　那么在高精度加法里面也可以是同个思路，我们一般是A[i]-B[i]-t，但是我们可以换成：A[i]-t-B[i]，在刚开始我们将借位t设为0即可，而我们的借位是怎么来的呢？就是在每一轮中(A[i]-t-B[i])<0我们的t就会变换，所以我们的代码可以这么写：

vector<int> C;
int t = 0;
    
for(int i = 0 ; i < A.size() || i < B.size() ; i ++){
    t = A[i] - t;
    if(i < B.size() ) t -= B[i];
    C.push_back((t + 10) % 10 );
    if(t < 0) t = 1;
    else t = 0;//if-else是为了借位
}

　　（注意，接下来一段由于没有图很难理解相当于自言自语，可以不用观看）

　　在得出通用式子，或者想要想要获得通用情况的时候，往往需要处理第一次情况，在这个例子里面就是将t设置为0，类似的处理还有：如果第一次和之后的流程不一样，直接用if来特指第一种情况；如果某变量在整个过程都需要更新尤其需要在第一次赋值更新，那么使用for条件筛选掉第一次情况在for后面添加第一次情况即可。（很抽象，如果遇到了那种代码，这里还会更新的）

　　在上面A[i]-t-B[i]的思路里，我们都是默认A大于B，如果是类似于5-23或者23-24这种就要将A和B的地位互换了，这里是图解：

 　　这里是代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

//虽然说本题目的减法借位可以做出来，但是我按照A.size() - B.size() 然后分别做出来的数不是一样的，只要位数太大了，那么我的代码就会失败
//所以反而是cmp函数需要注意
bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();

    for (int i = A.size() - 1; i >= 0; i -- )
        if (A[i] != B[i])
            return A[i] > B[i];//从大比到小，看看是谁先绷不住

    return true;//等于的话也要true
}


vector<int> sub (vector<int>&A , vector<int>&B ){//别忘了地址符
    vector<int> C;
    int t = 0;

    for(int i = 0 ; i < A.size() || i < B.size() ; i ++){
        t = A[i] - t;
        if(i < B.size() ) t -= B[i];
        C.push_back((t + 10) % 10 );
        if(t < 0) t = 1;
        else t = 0;//if-else是为了借位
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main(){
    string a , b;
    cin >> a >> b;

    vector<int> 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;


    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

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

}

　　补充：关于为什么要将A,B的数字反着存储这件事情，因为我们常见的数组（数据结构，vector也算）都是从左往右算（这里不考虑队列可以使用头插法），而算式是从右往左算，故将A，B的数字反着存储。

　　时间复杂度：观察一下代码，发现还是取决于A的位数，核心代码只有一个循环，无递归，如果A的位数是n，那么时间复杂度就是O（n）。