讨论/技术交流/分享|一道Leetcode没有的题目——字符串相减(大数相减)/
分享|一道Leetcode没有的题目——字符串相减(大数相减)

前言

今天补充的题目是字符串相减,俗称大数相减。

如果你还没做过415. 字符串相加,建议先做一下。

减法比加法稍微麻烦一点,但核心思路相似。

五分钟时间,带你掌握这道题~

题目描述

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的差。

注意:

  1. num1 和num2 都只会包含数字 0-9
  2. num1 和num2 都不包含任何前导零
  3. 你不能使用任何內建 BigInteger 库

题目分析

两个正数相减的结果可能为正,也可能为负。

因此,首先比较两个数的大小。

如代码所示,当小减大时,需将两个参数调换一下位置执行减法,在结果前填上负号即可

string subStrings(string num1, string num2) {
    string res;
    if (isLess(num1, num2)) {
        res = sub(num2, num1);
        res.insert(0, "-");
    }
    else res = sub(num1, num2);
    return res;
}

如何比较两个大数的大小呢?

由于是大数,肯定不能直接转成int比较。

我们可以比较两个字符串的长度。

长度更长的字符串,数一定更大;当长度一样的就去比较字典序。

bool isLess(string a, string b) {
    if (a.size() == b.size()) return a < b;
    return a.size() < b.size();
}

大体框架讲解完了,接下来实现关键的sub函数

我强烈推荐下边这种实现算法,简洁优雅。

string sub(string a, string b) {
    string res = "";
    int borrow = 0;
    int i = a.size() - 1, j = b.size() - 1;
    while (i >= 0 || j >= 0) {
        int x = i >= 0 ? (a[i] - '0') : 0; //字符转整数
        int y = j >= 0 ? (b[j] - '0') : 0; //字符转整数
        int z = (x - borrow - y + 10) % 10;
        res += ('0' + z); //整数转成字符
        borrow = x - borrow - y < 0 ? 1 : 0;
        i--, j--;
    }
    reverse(res.begin(), res.end());
    //删除前导0,注意边界是res.size()-1!!防止当res为"0000"时,删为""的清空
    int pos;
    for (pos = 0; pos < res.size() - 1; pos++) {
        if (res[pos] != '0') break;
    }
    return res.substr(pos);
}

需要说明的点有2个:

  1. z = (x - borrow - y + 10) % 10
    这种写法更简洁,其实等价于以下代码
if(x - borrow - y < 0) {
    z = (x - borrow - y + 10) % 10;
}
else z = x - borrow - y;
  1. 删除前导0。
    例如,当121-120=001,需要将前面的0删除,得到最终结果1。注意121-121=000这种情况,不要把所有0都删了!

大功告成~下面附上C++版的完整代码

参考代码

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

string sub(string a, string b) {
    string res = "";
    int borrow = 0;
    int i = a.size() - 1, j = b.size() - 1;
    while (i >= 0 || j >= 0) {
        int x = i >= 0 ? a[i] - '0' : 0;
        int y = j >= 0 ? b[j] - '0' : 0;
        int z = (x - borrow - y + 10) % 10;
        res += '0' + z;
        borrow = x - borrow - y < 0 ? 1 : 0;
        i--, j--;
    }
    reverse(res.begin(), res.end());
    //删除前导0。循环条件是res.size()-1是为防止"0000"的情况
    int pos;
    for (pos = 0; pos < res.size() - 1; pos++) {
        if (res[pos] != '0') break;
    }
    return res.substr(pos);
}

bool isLess(string a, string b) {
    if (a.size() == b.size()) return a < b;
    return a.size() < b.size();
}

string subStrings(string num1, string num2) {
    string res;
    if (isLess(num1, num2)) {
        res = sub(num2, num1);
        res.insert(0, "-");
    }
    else res = sub(num1, num2);
    return res;
}


int main() {
    string a, b, c;
    cin >> a >> b;
    cout << subStrings(a, b) << endl;
    return 0;
}
3
共 2 个回复

这个借位真是punchline

赞一个,借位那里的思路很棒