[数据结构][Python][经典题目]大数求和

叁歲伎倆 2023-10-11 13:09 34阅读 0赞

## 题目 ##

LeetCode上的算法第415题题目描述：  
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。  
注意：  
num1 和num2 的长度都小于 5100.  
num1 和num2 都只包含数字 0-9.  
num1 和num2 都不包含任何前导零。  
你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。  
LeetCode地址：https://leetcode-cn.com/problems/add-strings/description/

## 思路 ##

类似加法运算，考虑进位。新建一个数组，数组长度与较长的那个数组一致，数组后一部分保存较短数组的值，其余部分全为0，之后利用这个新建的数组  
与原较长的数组进行加和运算。从数组尾部加起，如果求和数值大于10，则只保留个位数，并把数组的前一位加1.如果进位后超出数组长度范围，则用插入操作。  
反转list,各个位数相加，进位

## 代码实现 ##

class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """ :type l1: List :type l2: List :rtype: List """
            l1 = list(reversed(l1))
            l2 = list(reversed(l2))
            l1, l2 = self.judgeLen(l1, l2)
            print(l1, l2)
            add_nums = []
            for i in range(len(l1)):
                add_num, flag = self.judgeCarry(l1[i], l2[i])
                if flag == 0:
                    add_nums.append(add_num)
                else:
                    add_nums.append(add_num)
                    try:
                        l1[i + 1] = l1[i + 1] + 1
                    except:
                        continue
            if add_nums[-1] == 0:
                add_nums.append(1)
            print(list(reversed(add_nums)))
            res = list(reversed(add_nums))
            return res
    
        def judgeCarry(self, a, b):
            if a + b > 9:
                return [(a + b) % 10, 1]
            else:
                return [a + b, 0]
    
        def judgeLen(self, l1, l2):
            lenl1 = len(l1)
            lenl2 = len(l2)
            add_len = []
            for i in range(abs(lenl2 - lenl1)):
                add_len.append(0)
            if lenl1 >= lenl2:
                for i in range(abs(lenl2 - lenl1)):
                    l2.append(0)
                # print([l1,add_len])
                return [l1, l2]
            else:
                for i in range(abs(lenl2 - lenl1)):
                    l1.append(0)
                add_len.append(l1)
                # print([l2,add_len])
                return [l2, l1]
    
    
    if __name__ == '__main__':
        S = Solution()
        S.addTwoNumbers([2, 4, 3, 5, 6, 4, 7, 4], [5, 6, 4, 4, 5, 6, 7])

![在这里插入图片描述][20190923235248700.png]

[20190923235248700.png]: https://img-blog.csdnimg.cn/20190923235248700.png