算法1

$O(n)$

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

bool comp(char t1[],char t2[]);

void cin_init(stack<int> &a,stack<int> &b,bool &cmp1){
    char t1[100010],t2[100010];
    scanf("%s",t1);
    scanf("%s",t2);
    int str1=strlen(t1),str2=strlen(t2);
    int temp1;
    cmp1 = comp(t1,t2);
    for(int i=0;i<str1;i++)t1[i]-=48;
    for(int i=0;i<str2;i++)t2[i]-=48;
    for(int i=0;i<str1;i++){a.push(t1[i]);
//  printf("apush%d\n",strlen(t1));
    }
    for(int i=0;i<str2;i++){b.push(t2[i]);
//  printf("bpush%d\n",strlen(t2));
    }
    return;
}

void sub(stack<int> &a,stack<int> &b,stack<int> &c){
    int t=0;
    while(!a.empty()&&!b.empty()){
        c.push((a.top()-b.top()+t+10)%10);
//      printf("%d-%d=%d",a.top(),b.top(),((a.top()-b.top()+t+10)%10));
        t=((a.top()-b.top()+t)<0)?-1:0;
//      printf("位%d \n",t);
        a.pop();b.pop();
    }
    while(!a.empty()){
        c.push((a.top()+t+10)%10);
        t=((a.top()+t)<0)?-1:0;
        a.pop();
    }
    while(!b.empty()){
        c.push((b.top()+t+10)%10);
        t=((b.top()+t)<0)?-1:0;
        a.pop();
    }
    return;
}

bool comp(char t1[],char t2[]){
    if(strlen(t1)>strlen(t2))
    return 1;
    else if(strlen(t1)<strlen(t2))
    return 0;
    else if(strcmp(t1,t2)>=0)
    return 1;
    else
    return 0;
}

int main(){
    stack<int> a,b,c;
    bool cmp;
    cin_init(a,b,cmp);
    if(cmp){
        sub(a,b,c);
    }
    else{
        cout<<'-';
        sub(b,a,c);
    }
    while(c.top()==0&&c.size()>1)c.pop();
    while(!c.empty()){
        printf("%d",c.top());
        c.pop();
    }
}