【边学边敲边记】LeetCode011:字符串相乘

一、写在前面

LeetCode 第二题两数之和传输门：
今天给大家分享的是LeetCode 数组与字符串 第十一题：字符串相乘，为面试而生，期待你的加入。

二、今日题目

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

说明：
  (1) num1 和 num2 的长度小于110。
  (2) num1 和 num2 只包含数字 0-9。
  (3)num1 和 num2 均不以零开头，除非是数字 0 本身。
  (4) 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
示例:

输入: num1 = "2", num2 = "3"
输出: "6"

输入: num1 = "123", num2 = "456"
输出: "56088"

三、 分析

我第一眼看到题就想，怎么这么简单啊，把str数据int一下，然后做数据乘法运算，再把结果str一下转换成字符串不就好了吗？然后我遇上了这句话“Use the utility in the API is recommended in the project. But if you use it in an interview, you will definitely fail .”，当然我英语不好，也能勉强看懂，直白翻译就是“你这么想你就不可能找到工作”，的确，我们必须认识到，我们现在实在刷算法题，提升思维能力，不是让我们投机取巧来了，我好好一想，包括之前的sort排序我们都不该用，或者说我们至少得知道一些基本排序算法后，才能用，不然，整天调包，调库，调方法，最终只会让大家把一切都掉光。
正确思想的思路分析：

四、解题

• 捷径的方法：
  ~调包调包调包~

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        # str->int
        num1 = int(num1)
        num2 = int(num2)
        # 求积
        result = num1*num2
        # int->str,返回
        return str(result)

• 提交结果

测试数据：311组
运行时间：28ms
击败人百分比:98.89%
这应该是最好情况

• 正确思想
  时间复杂度：O(n^2)

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        # 设置存储列表(原理见思路分析)
        product = [0] * (len(num1) + len(num2))
        # 下标
        pos = len(product) - 1
        # 字符串逆转，方便从个位开始遍历
        num1 = num1[::-1]
        num2 = num2[::-1]
        # 遍历被乘数字符串
        for n1 in num1:
            # 数据存储位置(数量级，第一次个位相乘，最后一位，第二次十位相乘，倒数第二位...)
            tempPos = pos
            # 遍历乘数字符串
            for n2 in num2:
                # 单个数据相乘
                product[tempPos] += int(n1) * int(n2)
                # 取十位及以上量级
                product[tempPos - 1] += product[tempPos] // 10
                # 取个位
                product[tempPos] %= 10
                # 前移
                tempPos -= 1
            # 前移，增加数量级
            pos -= 1
        # 找到结果列表非零数
        pt = 0
        while pt < len(product) - 1 and product[pt] == 0:
            pt += 1
        # 切片取出数据
        res_list = product[pt:]
        # map转换成迭代对象，用jion函数连接返回
        return ''.join(map(str,res_list))

• 提交结果

测试数据：311组
运行时间：308ms
击败人百分比:28.81%

虽然beat的人不多，但我有想法，我骄傲啊~

五、疑惑

其实这个题我想的是有两个方面：
1.考察对字符串的操作处理；
2.考察对数据运行的操作处理。
上面的算法基本包括了，也是LeetCode英文网站比较推崇的一种方法。

六、结语

坚持 and 努力 ： 终有所获

END

往期精彩

进学习交流群

不失联，扫码加X先生微信学习交流

温馨提示

欢迎大家转载，转发，留言，点赞支持X先生。

文末广告点一下也是对X先生莫大的支持。

做知识的传播者，随手转发。

▼

更多精彩推荐，请关注我们

▼

赞赏一下，秋天不会那么冷