如何对数字位子列表构成的二维列表求和且不转整数避免溢出

核心思路 #

不能直接将子列表转换为整数，所以采用逐位运算的方式处理大数：

1. 拆分输入中的正负数：分别收集所有正数的数位列表、所有负数的绝对值数位列表
2. 分别对正数集合、负数绝对值集合做无进位逐位累加，再统一处理进位，得到两个大数的数位表示
3. 比较两个大数的大小，用大数减小数得到结果的绝对值数位列表
4. 根据两个大数的大小关系给结果添加符号位

Python实现代码 #

def add_two_big_num(num1_digits, num2_digits):
    """两个正整数的数位列表相加，返回结果的数位列表，输入输出都是高位在前"""
    # 反转成低位在前方便计算
    num1 = num1_digits[::-1]
    num2 = num2_digits[::-1]
    res = []
    carry = 0
    max_len = max(len(num1), len(num2))
    for i in range(max_len):
        n1 = num1[i] if i < len(num1) else 0
        n2 = num2[i] if i < len(num2) else 0
        total = n1 + n2 + carry
        res.append(total % 10)
        carry = total // 10
    if carry > 0:
        res.append(carry)
    # 反转回高位在前，去掉前导零
    res = res[::-1]
    while len(res) > 1 and res[0] == 0:
        res.pop(0)
    return res

def compare_big_num(num1_digits, num2_digits):
    """比较两个正整数的数位列表大小，num1大返回1，相等返回0，num2大返回-1"""
    if len(num1_digits) != len(num2_digits):
        return 1 if len(num1_digits) > len(num2_digits) else -1
    for a, b in zip(num1_digits, num2_digits):
        if a != b:
            return 1 if a > b else -1
    return 0

def sub_two_big_num(large_digits, small_digits):
    """两个正整数的数位列表相减（large - small），返回结果的数位列表，高位在前"""
    large = large_digits[::-1]
    small = small_digits[::-1]
    res = []
    borrow = 0
    for i in range(len(large)):
        n1 = large[i] - borrow
        n2 = small[i] if i < len(small) else 0
        if n1 < n2:
            n1 += 10
            borrow = 1
        else:
            borrow = 0
        res.append(n1 - n2)
    # 反转回高位在前，去掉前导零
    res = res[::-1]
    while len(res) > 1 and res[0] == 0:
        res.pop(0)
    return res

def sum_big_lists(input_list):
    # 初始化正负总和的数位列表，初始值都是0
    pos_sum = [0]
    neg_sum = [0]
    for item in input_list:
        if item[0] < 0:
            # 负数，提取绝对值的数位
            abs_digits = [-item[0]] + item[1:]
            neg_sum = add_two_big_num(neg_sum, abs_digits)
        else:
            # 正数直接加
            pos_sum = add_two_big_num(pos_sum, item)
    # 比较正负总和的大小
    cmp_res = compare_big_num(pos_sum, neg_sum)
    if cmp_res == 0:
        return [0]
    elif cmp_res > 0:
        # 正数大，结果为正
        return sub_two_big_num(pos_sum, neg_sum)
    else:
        # 负数大，结果为负，首位加负号
        abs_res = sub_two_big_num(neg_sum, pos_sum)
        abs_res[0] = -abs_res[0]
        return abs_res

测试用例验证 #

• 输入 [[1, 0], [-1, 0], [7]]，调用 sum_big_lists 输出 [7]，符合预期
• 输入 [[5], [-1, 0]]，调用 sum_big_lists 输出 [-5]，符合预期

内容的提问来源于stack exchange，提问作者john