python leetcode 字符串相乘实例详解

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

示例 1:

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

输出: "6"

示例 2:

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

输出: "56088"

说明：

  1. num1  和  num2  的长度小于110。
  2. num1  和  num2  只包含数字  0-9 。
  3. num1  和  num2  均不以零开头，除非是数字 0 本身。

不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

从题目要求来看，应该是让我们实现一个比较省内存的大数乘法，先分享几个我在discuss中发现的不太切合题意的解法：

class Solution:
  def multiply(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    return str(eval(num1+'*'+num2))

这个可以说是个毫无技术含量的解法，如果面试的时候掏出这种解法，八成是跪了。

还有很多人使用了以下的解法。

class Solution:
  def multiply(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    dict = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}
    if (num1=='0' or num2=='0'):
      return "0"
    n1 = 0
    n2 = 0
    for c in num1:
      val = dict[c]
      n1 = n1*10 + val
    for s in num2:
      val = dict[s]
      n2 = n2*10 + val
    result = n1 * n2;
    return str(result)

这种解法我觉得还是没有切合题意，将注意力放在的字符串转数字上，乘法还是使用的*。题目要求不能将输入直接转成数字类型，解体人自己实现了int方法完成了字符串的转换，好像是符合要求，但有投机取巧的感觉。

我来分享一下我的解法，思路很简单也很好理解，当我们徒手计算222*11时我们怎么计算呢，肯定是分解成222+2220来计算的，那么我们就可以使用一个一维列表来记录计算结果11分解成10+1，第一轮计算列表的结果为[0, 2, 2, 2]，第二轮计算后变为[2, 2+2, 2+2, 2]计算结束。如果需要进位的话，进位的计算放到最后一步。

class Solution(object):
  def multiply(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    if num1 == "0" or num2 == "0":
      return "0"
    num1 = num1[::-1]
    num2 = num2[::-1]
    str_list = [0 for _ in range(len(num1)+len(num2))]
    for i in range(len(num1)):
      for j in range(len(num2)):
        str_list[i+j] += (int(num1[i])*int(num2[j]))
    result = ""
    up = 0
    for i in str_list:
      now = i + up
      cur = now % 10
      up = now / 10
      result += str(cur)
    begin = 0
    result = result[::-1]
    for i in result:
      if i == "0":
        begin += 1
      else:
        break
    return result[begin:]
赞 (0)

相关推荐

  • 对python中的乘法dot和对应分量相乘multiply详解

    向量点乘 (dot) 和对应分量相乘 (multiply) : >>> a array([1, 2, 3]) >>> b array([ 1., 1., 1.]) >>> np.multiply(a,b) array([ 1., 2., 3.]) >>> np.dot(a,b) 6.0 矩阵乘法 (dot) 和对应分量相乘 (multiply) : >>> c matrix([[1, 2, 3]]) >>

  • 对numpy 数组和矩阵的乘法的进一步理解

    1.当为array的时候,默认d*f就是对应元素的乘积,multiply也是对应元素的乘积,dot(d,f)会转化为矩阵的乘积, dot点乘意味着相加,而multiply只是对应元素相乘,不相加 2.当为mat的时候,默认d*f就是矩阵的乘积,multiply转化为对应元素的乘积,dot(d,f)为矩阵的乘积 3. 混合时候的情况,一般不要混合 混合的时候默认按照矩阵乘法的, multiply转化为对应元素的乘积,dot(d,f)为矩阵的乘积 总结:数组乘法默认的是点乘,矩阵默认的是矩阵乘法,混

  • Python 实现两个列表里元素对应相乘的方法

    方法一: 结合zip函数,使用map函数: List1 = [1,2,3,4] List2 = [5,6,7,8] List3 = map(lambda (a,b):a*b,zip(List1,List2)) print List3 方法二: 把列表转化为数组,使用np.multiply函数 List = [1,2,3] List2 = [5,6,7] List3 = np.multiply(np.array(List1),np.array(List2)) print List3.tolist(

  • python leetcode 字符串相乘实例详解

    给定两个以字符串形式表示的非负整数 num1 和  num2 ,返回  num1 和  num2 的乘积,它们的乘积也表示为字符串形式. 示例 1: 输入: num1 = "2", num2 = "3" 输出: "6" 示例 2: 输入: num1 = "123", num2 = "456" 输出: "56088" 说明: num1  和  num2  的长度小于110. num1  和

  • Python字符串处理实例详解

    Python字符串处理实例详解 一.拆分含有多种分隔符的字符串 1.如何拆分含有多种分隔符的字符串 问题: 我们要把某个字符串依据分隔符号拆分不同的字段,该字符串包含多种不同的分隔符,例如: s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz" 其中;,|,\t 都是分隔符号,如何处理? 方法一: 连续使用str.split()方法,每次处理一种分隔符号 s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz&q

  • Python 处理数据的实例详解

    Python 处理数据的实例详解 最近用python(3.2的版本)写了根据特定规则,处理数据的一个小程序,用到了一些python常用的基础知识,在此总结一下: 1,python读文件 2,python写文件 3,python的流程控制 4,python的for循环 5,python的集合,或字符串里判断是否存在某个元素 6,python的逻辑或,逻辑与 7,python的正则过滤 8,python的字符串忽略空格,和以某个字符串开头和按某个字符拆分成list python的打开文件的模式: 关

  • python模块常用用法实例详解

    1.time模块(※※※※) import time #导入时间模块 print(time.time()) #返回当前时间的时间戳,可用于计算程序运行时间 print(time.localtime()) #返回当地时间的结构化时间格式,参数默认为时间戳 print(time.gmtime) #返回UTC时间的结构化时间格式 print(time.mktime(time.localtime())) #将结构化时间转换为时间戳 print(time.strftime("%Y-%m-%d %X&quo

  • python 正则表达式参数替换实例详解

    正则表达式是一个特殊的字符序列,它能帮助你方便的检查一个字符串是否与某种模式匹配. Python 自1.5版本起增加了re 模块,它提供 Perl 风格的正则表达式模式. re 模块使 Python 语言拥有全部的正则表达式功能. compile 函数根据一个模式字符串和可选的标志参数生成一个正则表达式对象.该对象拥有一系列方法用于正则表达式匹配和替换. re 模块也提供了与这些方法功能完全一致的函数,这些函数使用一个模式字符串做为它们的第一个参数. 本章节主要介绍python 正则表达式参数替

  • Python : turtle色彩控制实例详解

    turtle.pencolor(* args ) 返回或设置pencolor. 允许四种输入格式: pencolor() 将当前的pencolor返回为颜色规范字符串或元组(参见示例).可用作另一种颜色/ pencolor / fillcolor调用的输入. pencolor(colorstring) 设置pencolor到colorstring,这是一个Tk的颜色指定的字符串,例如"red","yellow",或"#33cc8c". penco

  • python中time包实例详解

    在python中基础的时间运用,离不开time函数的支持.这些函数为了方便调用集中放在一个地方,叫做time包.有的人会仔细追寻time包的来源,会发现它和C语言有密不可分的关系.下面我们简单介绍time包的概念,然后就包中的一些函数进行列举,并附上对应的使用方法. 1.概念 time包基于C语言的库函数(library functions).Python的解释器通常是用C编写的,Python的一些函数也会直接调用C语言的库函数. 2.time包中的函数 time.clock()返回程序运行的整

  • python time.strptime格式化实例详解

    在python的时间使用时,我们无非就是输出字符串的形式,又或者是其他的形式跟字符串之间的来回转换.时间数组对于我们获取具体的年或是天数,都是常用的首段.本篇需要讲到的time.strptime函数,就是把字符串转换成时间元组的方法.在接下来的内容中就其函数的概念.语法.参数.返回值和实例分别介绍. 1.概念 能够根据指定的格式把一个时间字符串解析为时间元组. 2.语法 time.strptime(string[, format]) 3.参数 string -- 时间字符串. format --

  • python+flask编写接口实例详解

    python+flask编写接口实例详解

    环境:Pycharm :其他环境:安装Anaconda 最近在做一个小型项目练手,涉及到大量的IP和相关数据处理,所以选用了Python来处理数据,但是处理完怎么给前端调用呢,今天这篇就是在Python方便地处理完数据后以接口形式把数据返回给前端. flask就是使用Python编写接口实例的关键库,先配置项目: ①(这一步可以使用Python默认解释器,但是后续安装库可能还需要配置,建议使用Anaconda)首先打开PyCharm,在file->settings->Project->p

  • IOS开发之字典转字符串的实例详解

    IOS开发之字典转字符串的实例详解 在实际的开发需求时,有时候我们需要对某些对象进行打包,最后拼接到参数中 例如,我们把所有的参数字典打包为一个 字符串拼接到参数中 思路:利用系统系统JSON序列化类即可,NSData作为中间桥梁 //1.字典转换为字符串(JSON格式),利用 NSData作为桥梁; NSDictionary *dic = @{@"name":@"Lisi",@"sex":@"m",@"tel&qu

随机推荐