SWE / MLE · Coding

Meta 十进制字符串相加:整数溢出、小数对齐与规范输出

不用整串int或float转换,对任意长度非负十进制文本求和,删除多余整数前零与小数尾零。

题目重点:不用整串int或float转换,对任意长度非负十进制文本求和,删除多余整数前零与小数尾零。

题意与假设

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

  • 输入为非负ASCII十进制,允许前导零、可选一个小数点,整数部分必需,小数点后至少一位。正负号、科学计数与千位分隔不在本合同。
  • 输出整数保留至少一个0,小数去尾零,若无小数则不带点。单个位可用ord提取,不把整串转int/float。

解题路线

  1. 分别解析整数与小数,scale取两小数长度最大值;短小数在右侧补零,使两值都变为以10^−scale为单位的整数数字串。
  2. 从右往左按位相加并传carry,输出逆序数字;最后插回小数点,规范整数前零与小数尾零。使用列表而非不断前插字符串,避免额外平方成本。
  3. 固定精度整数/浮点都会限制长度或失去小数精确度;手工十进制进位保留精确结果。整数加法是scale=0的同题变体,无需另写重复文章。

手动走一遍

009.900+0.100,对齐后数字9900+0100=10000,scale3得到10.000,规范输出10。0.001+0.009得到0.01;999+1得到1000。

Python 参考实现

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

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

def add_decimal_strings(first, second):
    """Nonnegative decimals, no int()/float() conversion of entire operands."""
    def parse(text):
        parts = text.split('.')
        if len(parts) > 2 or not parts[0] or any(c not in '0123456789' for c in ''.join(parts)):
            raise ValueError("unsigned decimal required")
        if len(parts) == 2 and not parts[1]:
            raise ValueError("fractional digits required after decimal point")
        return parts[0], parts[1] if len(parts) == 2 else ''
    a, af = parse(first); b, bf = parse(second)
    scale = max(len(af), len(bf))
    left, right = a + af.ljust(scale, '0'), b + bf.ljust(scale, '0')
    i, j, carry, out = len(left)-1, len(right)-1, 0, []
    while i >= 0 or j >= 0 or carry:
        total = carry
        if i >= 0: total += ord(left[i])-ord('0'); i -= 1
        if j >= 0: total += ord(right[j])-ord('0'); j -= 1
        carry, digit = divmod(total, 10); out.append(chr(ord('0')+digit))
    text = ''.join(reversed(out)).rjust(scale+1,'0')
    if scale:
        integer, fraction = text[:-scale], text[-scale:].rstrip('0')
    else:
        integer, fraction = text, ''
    integer = integer.lstrip('0') or '0'
    return integer + ('.'+fraction if fraction else '')

复杂度

O(m+n+scale)时间与输出/工作空间,scale<=max(m,n),故线性。返回文本长度与输入长度同阶。

易错点与追问

容易失分的边界

  • 小数补零方向错误:0.1补为0.100不是0.001。
  • float会把大整数与精确小数舍入,不满足任意长度或精确十进制要求。
  • 把结果rstrip("0")直接用于整串会把1000截成1;只去小数部分尾零。

继续深挖

  • 加入负数先比较绝对值:同号加、异号大绝对值减小,结果符号按较大者;借位与零规范需独立验证。
  • 金融舍入属于另一层合同,指定保留scale及half-even/half-up,不能自行四舍五入。
✓已复制微信号!