43. Multiply Strings 字符串相乘

题目

给定两个以字符串形式表示的数字 num1 和 num2。这两个数字不为负。返回这两个数字的乘积。用字符串表示。

解析

主要就是实现两个函数，字符串转数字和数字转字符串。
难点：大数乘法。

1. 设置一个结果字符串 rst
2. 将 num 2 的第1个数字和 num1 相乘，得到一个临时结果记为 tmp
3. 将 tmp 和 rst 按位相加，结果存入 rst 中。
4. 将 num 2 的第2个数字和 num2 相乘，得到一个新的 tmp，tmp 左移一位，继续相加。
5. 直到 num2 迭代完毕。

所以需要实现三个函数

1. 字符串和一个数字相乘，得到一个字符串。
2. 字符串左移动 n 位。
3. 两个不等长字符串相加。

伪代码

var rst string

for i<len(num2); i++ 
  tmp = multiply(num1[i] * num1)
  tmp = move(tmp,i)
  rst = add(rst,tmp)
return rst

func multiply(str, num) str
 var rst string
  var flag int
  for i<len(str) 
    prod =  str[i]*num + flag
    tmp = prod % 10
    flag = prod/10
     rst=tmp+rst
  if flag != 0
    rst = flag+rst
return rst

func move(str,n) string
  for n>0
    str+="0"
  return str

func add(str1, str2) string
  flag int
  var rst string
  for 
    if i = len(str1) && j == len(str2)
        break
    if i <len(str1)
      tmp += str1[i]
    if j < len(str2)
      tmp += str2[i]
    tmp += flag
    pop = tmp%10
    flag = tmp/10
    rst="pop"+rst
return rst

代码

func multiply(num1 string, num2 string) string {
    if len(num1) < len(num2) {
        t := num1
        num1 = num2
        num2 = t
    }
    var rst string
    for i := len(num2)-1; i>=0; i--{
        tmp := mul(num1, int(num2[i]-'0'))
        tmp = move(tmp,len(num2)-1-i)
        rst = add(rst, tmp)
    }
    return rst
}

func mul(str string, num int) string {
    var rst string
    var flag int
    if num == 0 {
        return "0"
    }
    for i:=len(str)-1;i>=0;i--{
        prod := int(str[i]-'0')*num+flag
        pop := prod%10
        flag = prod/10
        rst = string([]byte{byte(pop+'0')}) + rst
    }
    if flag != 0 {
        rst = string([]byte{byte(flag+'0')}) + rst
    }
    return rst
}

func move(str string, n int) string {
    if str == "0" {
        return "0"
    }
    for ;n>0;n-- {
        str+="0"
    }
    return str
}

func add(str1 string, str2 string) string {
    var flag int
    var rst string
    i:=len(str1)-1
    j:=len(str2)-1
    for i>=0 || j>=0 {
        sum := flag
        if i >= 0 {
            sum+=int(str1[i]-'0')
            i--
        }
        if j>=0 {
            sum+=int(str2[j]-'0')
            j--
        }
        pop:= sum%10
        flag =sum/10
        rst=string([]byte{byte(pop+'0')}) + rst
    }
    if flag != 0 {
        rst = string([]byte{byte(flag+'0')}) + rst
    }
    return rst
}

image.png

后记

• 移位运算需要判断字符串是否为 0，不能将 "0" 变成 “0000”
• 字符串低地址是数字的高位