43. 字符串相乘

Link

43. 字符串相乘 - 力扣（LeetCode）力扣 LeetCode

Problem

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

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1：

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

示例2：

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

提示：

• 1 <= num1.length, num2.length <= 200

• num1 和 num2 只能由数字组成。

• num1 和 num2 都不包含任何前导零，除了数字0本身。

Solution

解法一：做加法

Go

func multiply(num1 string, num2 string) string {
    //减少加法次数
    if len(num1) > len(num2) {
        num1, num2 = num2, num1
    }
    //判断零元提前返回
    if num1 == "0" || num2 == "0" {
        return "0"
    }
    //计算num1各个数位与num2的乘积
    addees := make([]string, len(num1))
    var a, b, s, cin byte
    for i := len(num1)-1; i >=0; i-- {
        p := []byte{}
        a, cin = num1[i] - '0', 0 
        for j := len(num2)-1; j >=0; j-- {
            b = num2[j] - '0'
            s = a * b + cin
            cin = s / 10
            p = append(p, s%10 + '0')
        }
        if cin > 0 {
            p = append(p, cin + '0')
        }
        reverse(p)
        addees[i] = string(p)
    }
    //将所有乘积相加
    ans := ""
    for _, addee := range addees {
        ans = add(ans + "0", addee)
    }
    return ans
}

func add(num1 string, num2 string) string {
    ans := []byte{}
    var a, b, s, cin byte 
    for i, j := len(num1)-1, len(num2)-1; i >=0 || j >= 0 || cin != 0; i, j = i-1, j-1 {
        if i >= 0 {
            a = num1[i] - '0'
        } else {
            a = 0
        }
        if j >= 0 {
            b = num2[j] - '0'
        } else {
            b = 0
        }
        s =  a + b + cin
        cin = s / 10
        
        ans = append(ans, s%10 + '0')
    } 
    reverse(ans)
    return string(ans)
}

func reverse(nums []byte) {
    n := len(nums)
    for i := 0; i < n>>1; i++ {
        nums[i], nums[n-i-1] = nums[n-i-1], nums[i]
    }
}

C++

解法二：做乘法

Go

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }
    m, n := len(num1), len(num2)
    ans := make([]int, m+n)
    
    var a, b int
    for i := m - 1; i >= 0; i-- {
        a = int(num1[i] - '0')       
        for j := n-1; j >= 0; j-- {
            b = int(num2[j] - '0')
            ans[i+j+1] += a * b
        }
    }
    for i := m + n - 1; i > 0; i-- {
        ans[i-1] += ans[i] / 10
        ans[i] = ans[i] % 10
    } 

    // var sb strings.Builder
    // i := 0
    // if ans[0] == 0 {
    //     i++
    // }
    // for ; i < m + n; i++ {
    //     sb.WriteByte(byte(ans[i] + '0'))
    // }
    // return sb.String()
    sb := make([]byte, m+n)
    for i := range sb{
        sb[i] = byte(ans[i] + '0')
    }
    if sb[0] == '0' {
        sb = sb[1:]
    }
    return string(sb)
}

C++