AcWing 792. 高精度减法    原题链接    简单

作者： 作者的头像   jasonlin ,  2020-04-04 12:33:11 ,  所有人可见 ,  阅读 14800

81


37

思路

  • 和高精度加法差不多，值得注意的是
    • 减法的借位处理
    • 相减为负数的处理
    • 前导0的处理

收获

  • 对于 t = A[i] - B[i] - t； 可以拆为 t = A[i] - t如果B[i]合法，再t -= B[i] 这么两步来做
  • 相减后t的处理 ，把 t >=0 和 t < 0 用一个式子来表示 t = (t + 10) % 10 这个木有想到
  • A B大小判断，自己写的太冗余，不如单独拎出来
bool cmp(vector<int>& A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();  //直接ruturn 了就不用else

    for(int i = A.size(); i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];

    return true;
}

拓展

  • A B 可以为正 为负怎么处理
    • 绝对值的相减相加，再加标志，标志由输入来决定，判断一下字符串的首字符了类型

自己的写法

// 给定两个正整数

#include <iostream>
#include <vector>

using namespace std;

vector <int> sub(vector<int>& A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10 ); // 合而为1
        if(t < 0)  t = 1;
        else t = 0;

    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导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');

    if (a.size() < b.size()) 
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }


    if (a.size() == b.size())
    {
        for(int i = a.size() -1 ; i >= 0; i --)
            if(A[i] != B[i]) 
            {  
                if(A[i] < B[i])
                {
                    auto C = sub(B, A);
                    printf("-");
                    for(int j = C.size() - 1; j >= 0; j--) printf("%d", C[j]);
                    return 0;
                }
                else
                {
                    auto C = sub(A, B);
                    for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
                    return 0;
                }
            }
    }

    auto C = sub(A, B);
    for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

    return 0;
}

YXC

// 给定两个正整数

#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int>& A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();  //直接ruturn 了就不用else

    for(int i = A.size(); i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];

    return true;
}

vector <int> sub(vector<int>& A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10 ); // 合而为1
        if(t < 0)  t = 1;
        else t = 0;

    }

    while(C.size() > 1 && C.back() == 0) C.pop_back();  //去掉前导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');

    if (cmp(A,B)) 
    {
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }
    else
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }


}

26 评论

用户头像
15890576541   2020-11-21 22:10      12    踩      回复

说实话，看了你们的题解发表，还是有很多好处的，思路，收获，完整题解以及拓展。看来都是大佬啊。

用户头像
15890576541   2020-11-21 21:47      5    踩      回复

应该是i-a.size()-1吧

用户头像
尚且   2023-03-27 09:20      3    踩      回复

为什么cmp里要对A,B进行引用呢

用户头像
考不上研不改名   2023-12-11 19:37      2    踩      回复

可写可不写，一次循环引用了数组地址和拷贝数组元素，空间差不多。但是放到大一点的循环里面，引用比不引用节约很多空间

用户头像
不破爱花   2023-04-02 18:42      2    踩      回复

有个疑问，string类不是可以直接比较运算吗，为什么还要特意写个cmp函数

用户头像
っっ   11个月前      4    踩      回复

string s1 = “3”;
string s2 = “12”;
if(s1 > s2)
cout << “1大”;
else cout <<”2大”;
字符串比较：基于左端对齐，从左到右，依次比较单个字符。
整数比较：基于右端对齐（最低为对齐）

用户头像
sleepycat   9个月前      1    踩      回复

不可以 比如 2,13，字符串比较是按照字典序比较，会输出2，必须要先比较size

用户头像
longzx   2023-03-25 10:34      1    踩      回复

有一个问题 ， 我直接用string进行比较大小， 但是输入很长时就通不过了 有没有大佬 帮我解答一下是为什么

用户头像
lagom   2022-12-31 15:34      1    踩      回复

cmp函数里不应该判断A、B两个数组长度的大小吗？看是不是A.size() >= B.size()

用户头像
jjya   2022-10-23 11:35      1    踩      回复

t<0 t=1
else t=0是什么意思有大佬解答一下吗？这一块听y总讲的时候就没听懂，，

用户头像
xiansta   2022-10-28 21:29      4    踩      回复

如果t<0;就代表上一位运算时借了一位，在计算更高一位时减去借位的1

用户头像
193043506   2022-02-15 22:39      1    踩      回复

在cmp函数里的for循环不应该是i=A.size()-1吗

用户头像
墨墨   2022-02-26 18:54         踩      回复

应该是手误吧确实应该是A.size() - 1

用户头像
懒惰的蚩蚩   2022-07-19 23:29         踩      回复

确实严谨来说，是i=A.size()-1，不过这里A.size()的那一位等于0，所以都相等，不影响最终结果，都能AC，

用户头像
tobetheonly   5个月前         踩      回复

为啥我的代码有一个用例正负判断不对

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int>a,b,c;
string n1,n2;
void put(string s,vector<int>&d)
{
    for(int i=s.size()-1;i>=0;i--)
    {
        d.push_back(s[i]-'0');
    }
}
bool cmp(string s1,string s2)
{
    if(s1.size()!=s2.size())return s1.size()>s2.size();
    else
    {
        int i=0;
        while(s1[i]==s2[i])i++;
        return s1[i]>s2[i];
    }
}
void sub(vector<int>l,vector<int>r)
{
    int i=0,j=0,t=0;
    while(i<l.size()||j<r.size())
    {
        if(i<l.size())t+=l[i++];
        if(j<r.size())t-=r[j++];
        if(t<0)
        {
            c.push_back(t+10);
            t=-1;
        }
        else  c.push_back(t),t=0;
    }
    int pos=0;
    while(!c[pos]&&!pos)
    {
        c.pop_back();
    }

}
int main()
{
   // freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false); 
    cin>>n1>>n2;
    put(n1,a);
    put(n2,b);
    if(cmp(n1,n2))sub(a,b);
    else cout<<"-",sub(b,a);
    for(int k=c.size()-1;k>=0;k--)printf("%d",c[k]);
}
用户头像
littlebit.   8个月前         踩      回复

#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;

bool cmp(vector[HTML_REMOVED]& a,vector[HTML_REMOVED]& 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;

}
vector[HTML_REMOVED] add(vector[HTML_REMOVED]& a,vector[HTML_REMOVED]& b){
int t = 0;
vector[HTML_REMOVED] c;
for(int i = 0;i[HTML_REMOVED] sub(vector[HTML_REMOVED]& a,vector[HTML_REMOVED]& b){
vector[HTML_REMOVED] res;
for(int i = 0,t = 0;i<a.size();++i){
t = a[i]-t;
if(i<b.size())t-=b[i];
res.push_back((t+10)%10);
if(t<0)t = 1;
else t = 0;
}

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

return res;

}

int main(){
string a,b;
vector[HTML_REMOVED] A,B;

cin>>a>>b;
for(int i = a.size()-1;i>=0;--i)if(a[i]!='-')A.push_back(a[i]-'0');
for(int i = b.size()-1;i>=0;--i)if(b[i]!='-')B.push_back(b[i]-'0');

vector<int> C;
//A B 同正 同负 一负一正  一正一负
//通过string首元素符号判断
//同正
if('-'!=a[0]&&'-'!=b[0]){
    if(cmp(A,B)){
    C = sub(A,B);
    for(int i = C.size()-1;i>=0;--i)printf("%d",C[i]);
}
else{
    C = sub(B,A);
    printf("-");
    for(int i = C.size()-1;i>=0;--i)printf("%d",C[i]);
    }
}
//同负
else if('-'==a[0]&&'-'==b[0]){
    if(!cmp(A,B)){//类似 -1 - (-2)
    C = sub(B,A);
    for(int i = C.size()-1;i>=0;--i)printf("%d",C[i]);
}
else{
    C = sub(A,B);
    printf("-");
    for(int i = C.size()-1;i>=0;--i)printf("%d",C[i]);
    }
}

//一负一正
else if('-'==a[0]&&'-'!=b[0]){
    C = add(A,B);
    printf("-");
    for(int i = C.size()-1;i>=0;--i)printf("%d",C[i]);
}
//一正一负
else{
    C = add(A,B);
    for(int i = C.size()-1;i>=0;--i)printf("%d",C[i]);
}

return 0;

}

用户头像
脑子里二哈在转圈   8个月前         踩      回复

核心算法的那个循环里我自己写了18行，看了题解只用了5行，太精妙了！

用户头像
Y永爱G   2023-08-08 10:41         踩      回复

Y总的过不了

用户头像
箐行   5个月前         踩      回复

Y总的那个代码在两数相等时会输出-0

用户头像
linshengxuan   2023-06-04 21:05         踩      回复

第10行

用户头像
几番熙攘   2022-08-04 11:54         踩      回复

为什么要if(i<B.size()) t-=B[i];不判断i<B.size()的话 B的高位B[i]是零应该不影响吧

用户头像
小风扇v   2022-08-14 19:28      2    踩      回复

i大于B的位数之后会B[i]会返回很奇怪的数，有可能不是0

用户头像
taez   2022-05-11 20:40         踩      回复

不%10是不是也可以？

用户头像
StkOvflow   2022-07-21 21:41         踩      回复

不行吧，t可能大于10

用户头像
algorithm_12   2023-01-07 14:11    回复了 StkOvflow 的评论         踩      回复

我觉得是要为了防止等于10的情况，不可能大于十的

用户头像
Huan9.13   2023-06-24 20:11      1    踩      回复

不可以的。举个例子：个位数运算的时候3与7进行，向十位借一位，得到6;这个过程可以想象成3-7=-4，将结果+10再取模，就可以得到6