手记

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,分别指向 num1num2 末尾;
  • 定义变量 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

实现结果


0人推荐
随时随地看视频
慕课网APP