Jianbo Dai's

mq022.字符串相加

 
  • Dec 06, 2020

题目链接

啊就按部就班地写嘛如1，不过写出来有点慢啊，时间和空间消耗都在后半部分。可能是有什么部分不够优美吧。于是复制了别人的代码如下，思路是完全一样的就细节不太一样别人写得更加简练，于是我也试着用了类似的算carry的方法确实有提升，我还有一部分比较慢的原因是求res的时候用了[-1]可能会慢。这个算法的时间复杂度是O（N），空间复杂度是O（1）。

class Solution:
    def addStrings1(self, num1: str, num2: str) -> str:

        def str2num(c):
            return ord(c)-ord("0")

        if len(num1) < len(num2):
            num1, num2 = num2, num1
        res = ""
        p1, p2 = len(num1)-1, len(num2)-1
        carry = 0
        while p1 >= 0 and p2 >= 0:
            n1, n2 = str2num(num1[p1]), str2num(num2[p2])
            tmp = n1 + n2 + carry
            carry = int(str(tmp)[0]) if tmp >= 10 else 0
            res = str(tmp)[-1] + res
            p1 -= 1
            p2 -= 1
        while p1 >= 0:
            tmp = str2num(num1[p1]) + carry
            carry = int(str(tmp)[0]) if tmp >= 10 else 0
            res = str(tmp)[-1] + res
            p1 -= 1
        if carry:
            res = str(carry) + res
        if not res:
            return "0"
        return res

    def addStrings2(self, num1: str, num2: str) -> str:
        res = ""
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        while i >= 0 or j >= 0:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            tmp = n1 + n2 + carry
            carry = tmp // 10
            res = str(tmp % 10) + res
            i, j = i - 1, j - 1
        return "1" + res if carry else res

    def addStrings3(self, num1: str, num2: str) -> str:

        def str2num(c):
            return ord(c)-ord("0")

        if len(num1) < len(num2):
            num1, num2 = num2, num1
        res = ""
        p1, p2 = len(num1)-1, len(num2)-1
        carry = 0
        while p1 >= 0 and p2 >= 0:
            tmp = str2num(num1[p1]) + str2num(num2[p2]) + carry
            carry = tmp // 10
            res = str(tmp)[-1] + res
            p1 -= 1
            p2 -= 1
        while p1 >= 0:
            tmp = str2num(num1[p1]) + carry
            carry = tmp // 10
            res = str(tmp)[-1] + res
            p1 -= 1
        if carry:
            res = str(carry) + res
        if not res:
            return "0"
        return res
Search