Multiply Strings

Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = “2”, num2 = “3” Output: “6”

Example 2:

Input: num1 = “123”, num2 = “456” Output: “56088”

将两个字符串表示的数字相乘（大数相乘）。

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contain only digits 0-9.
  3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

实现大数相乘：以string的形式给出两个非负整数，求乘积。

Solution

我在实现这个乘法时，按照手写计算的方式，每次按位相乘之后记录进位然后写下当前位。 然后把当前位结果加上前一位的结果并存为byte。每次外循环都会做一次大数加法，将乘积结果累加。 效率很不理想：40ms。

在看了别人的算法之后，重新实现了一遍。

先将每一位的乘法结果保存，最后再按位相加并处理进位。

这里贴出别人的算法：

func multiply(num1 string, num2 string) string {
    l1, l2 := len(num1), len(num2)

    // 需要使用int，使用byte会在按位相加的时候溢出
    r := make([]int16, l1+l2)

    idx := 0
    for i1 := l1 - 1; i1 >= 0; i1-- {
        // num1的个位数从最后一位开始写；
        // num1的十位数从倒数第二位开始写；
        // num2的百位数从倒数第三位开始写
        // ...
        // so: l1 + l2 - 1 - (l1 - i1 - 1)
        idx = l2 + i1
        for i2 := l2 - 1; i2 >= 0; i2-- {
            r[idx] += int16(num1[i1]-'0') * int16(num2[i2]-'0')
            idx--
        }
    }

    // 按位相加并进位
    for idx = len(r) - 1; idx >= 0; idx-- {
        if r[idx] > 9 {
            r[idx-1] += (r[idx] / 10)
            r[idx] %= 10
        }
    }


    var buf bytes.Buffer
    // truncate front '0'
    for _, v := range r {
        if buf.Len() > 0 || v != 0 {
            buf.WriteByte(byte(v) + '0')
        }
    }

    if buf.Len() == 0 {
        buf.WriteByte('0')
    }

    return buf.String()
}