LeetCode 415. 字符串相加 | Python

415. 字符串相加

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/add-strings

题目

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

注意：

num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库，也不能直接将输入的字符串转换为整数形式。

解题思路

思路：双指针，模拟

在这里，先说明一下，题目中注意部分的最后一个，不能直接将输入的字符串转换为整数，这里说的是不能将整个字符串转换之后进行计算，并非说完全不能使用类型转换。

在这里，使用双指针的方法，然后模拟加法运算，具体的做法及注意如下：

定义双指针 p、q，分别指向 num1，num2 末尾；
定义变量 carry，用以存储进位；
开始模拟计算（注意要加上进位），这里相加结果当大于 10 时，将结果模 10，然后再将此时的取模结果添加到 ans 头部；
因为 num1 和 num2 的长度可能不等，那么就有可能出现索引溢出的情况。当出现这种情况时，要将较短的字符串前面添加 0，用以后续的计算。
循环计算直至结束，这里要注意进位 carry 是否不为 0，当 carry 为 1 的情况下，也要将 1 添加到 ans 头部。

算法的实现过程图解如下：

图示

具体的代码实现如下。

代码实现

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        # 用以存储计算结果
        ans = ""
        # 定义指针分别指向 num1, num2 末尾
        p = len(num1) - 1
        q = len(num2) - 1
        # 存储进位
        carry = 0

        # 模拟加法运算
        # 这里将 carry 放到条件中，是考虑后续计算结束后，还有进位，也就是 carry 为 1 的情况
        while p >= 0 or q >= 0 or carry:
            # 由于有可能出现索引溢出的现象，
            # 当较短的字符串索引溢出时，要在头部添加 0，用以后续计算
            elem1 = int(num1[p]) if p >= 0 else 0
            elem2 = int(num2[q]) if q >= 0 else 0
            # 模拟计算，注意加上进位
            tmp = elem1 + elem2 + carry
            # 相加结果可能大于 10
            # 计算进位，并且就将结果模 10，余数添加到 ans 头部
            carry = tmp // 10
            ans = str(tmp % 10) + ans
            # 往前继续计算
            p -= 1
            q -= 1
        return ans

实现结果

欢迎关注

公众号【书所集录】