简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
一、写在前面
LeetCode 第二题两数之和传输门：LeetCode010 : 盛最多水的容器
今天给大家分享的是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 努力 ： 终有所获
