Interview Support Pro北美科技面试辅助与冲刺陪跑

SWE · Coding

TikTok 带正负号字符数组相加：绝对值比较、进位与借位

不转整段整数，拆符号和绝对值，统一零与前导零，覆盖长串进位和跨符号抵消。

题目重点：不转整段整数，拆符号和绝对值，统一零与前导零，覆盖长串进位和跨符号抵消。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

  • 训练API收两个字符串，字符数组可先join；只允许ASCII数字，首位可选+或−，无空白、小数和科学记数法。
  • 允许前导零，输出不含+和多余零，正负零均输出0。
  • 禁止整体int转换；示例借助单个字符ord得到0–9，用独立大整数模型验证结果。

解题路线

  1. 先校验并解析符号，将绝对值的前导零去掉；空符号后缀要报错。归一化后才能用长度和字典序比较绝对值，例如0009与10若直接按原长度比较就错。
  2. 同号时做绝对值相加，符号保持。两指针从右到左，当前和为两个数位加carry，divmod(total,10)生成下一位与进位，处理完所有位后还要输出最后carry。
  3. 异号时不做有符号进位。先比较绝对值，用大的减小的，结果符号来自绝对值较大的操作数；绝对值相等直接得到0。比较依据是规范十进制长度，长度相同时比较字符串。
  4. 减法从低位向高位借位：digit=x[i]−borrow−y[j]。若负则加10并将borrow置1，否则置0；缺少的高位按0处理。前置条件x≥y保证最后不留下借位。
  5. 循环不变量是已生成低位等于对应部分的和或差，carry/borrow承载对下一位的唯一影响。两指针每次至少向左移动一格，所以每个输入数位只参与一次计算。
  6. 反向积累到列表，最后一次反转join。不要反复把新字符插到字符串头部，这会复制已生成前缀，长数可退化为平方时间。减法完成后清理前导零，并禁止产生−0。
  7. 如果调用方直接给字符数组，保持相同逻辑或一次join即可；是否原地修改、返回数组还是字符串是API合同，不能把展示代码的字符串接口强称唯一输入格式。

手动走一遍

−0099 + +100 = 1；−1000 + 1 = −999，借位跨过多个0；999 + 1 = 1000，需要最后进位。−000与+0归一化为0。−500与+500抵消后不可返回−0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def add_signed(a, b):
    def parse(value):
        if not isinstance(value, str) or not value:
            raise ValueError('expected a signed decimal string')
        negative = value[0] == '-'
        magnitude = value[1:] if value[0] in '+-' else value
        if not magnitude or any(c not in '0123456789' for c in magnitude):
            raise ValueError('invalid decimal digits')
        magnitude = magnitude.lstrip('0') or '0'
        return negative and magnitude != '0', magnitude

    def plus(x, y):
        i, j, carry, result = len(x) - 1, len(y) - 1, 0, []
        while i >= 0 or j >= 0 or carry:
            total = carry
            if i >= 0:
                total += ord(x[i]) - 48
                i -= 1
            if j >= 0:
                total += ord(y[j]) - 48
                j -= 1
            carry, digit = divmod(total, 10)
            result.append(chr(48 + digit))
        return ''.join(reversed(result))

    def minus(x, y):  # x >= y in absolute value
        i, j, borrow, result = len(x) - 1, len(y) - 1, 0, []
        while i >= 0:
            digit = ord(x[i]) - 48 - borrow - (ord(y[j]) - 48 if j >= 0 else 0)
            borrow = int(digit < 0)
            result.append(chr(48 + digit + 10 * borrow))
            i -= 1
            j -= 1
        return ''.join(reversed(result)).lstrip('0') or '0'

    neg_a, x = parse(a)
    neg_b, y = parse(b)
    if neg_a == neg_b:
        magnitude, negative = plus(x, y), neg_a
    elif (len(x), x) >= (len(y), y):
        magnitude, negative = minus(x, y), neg_a
    else:
        magnitude, negative = minus(y, x), neg_b
    return ('-' if negative and magnitude != '0' else '') + magnitude

复杂度

设两串长度为m、n，时间O(m+n)，解析、反向结果与输出O(m+n)空间；若输入是字符数组，join成本也在此界内。没有依赖任意精度整体整数运算。

易错点与追问

容易失分的边界

  • 不同符号仍用同号加法。
  • 按未去零的原字符串长度比较绝对值。
  • 漏掉最终carry或输出−0。
  • 逐字符插入字符串头部造成二次复制。

继续深挖

  • 怎样扩展十进制减法或任意进制？
  • 怎样对超大输入流做外部存储处理？
  • 如果小数也允许，需要怎样对齐？
  • 怎样复用绝对值操作而保持签名清楚？
✓已复制微信号！