算法：字符串相乘

本文主要是介绍算法：字符串相乘，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 题目描述

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

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

//字符串相乘

//做加法 1234 * 567
func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    ans := "0"
    m, n := len(num1), len(num2)

    //遍历字符串num2
    for i := n - 1; i >= 0; i-- {
        curr := ""
        //进位
        add := 0

        for j := n - 1; j > i; j-- {
            curr += "0"
        }

        //转换为整数
        y := int(num2[i] - '0')

        //做乘法
        for j := m - 1; j >= 0; j-- {
            //转换为整数
            x := int(num1[j] - '0')

            product := x * y + add
            //itoa 整形转换为字符串
            //curr 为对应的每一位数
            curr = strconv.Itoa(product % 10) + curr
            add = product / 10
        }

        //处理最后一个进位
        for ; add != 0; add /= 10 {
            curr = strconv.Itoa(add % 10) + curr
        }

        ans = addStrings(ans, curr)
    }

    return ans
}


func addStrings(num1, num2 string) string {
    i, j := len(num1) - 1, len(num2) - 1
    add := 0
    ans := ""
    //add 也要判断
    for ; i >= 0 || j >= 0 || add != 0; i, j = i - 1, j - 1 {
        x, y := 0, 0
        if i >= 0 {
            x = int(num1[i] - '0')
        }
        if j >= 0 {
            y = int(num2[j] - '0')
        }
        result := x + y + add
        ans = strconv.Itoa(result % 10) + ans
        add = result / 10
    }
    return ans
}


//做乘法
func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    m, n := len(num1), len(num2)
    ansArr := make([]int, m + n)

    for i := m - 1; i >= 0; i-- {
        x := int(num1[i]) - '0'
        for j := n - 1; j >= 0; j-- {
            y := int(num2[j] - '0')
            //相乘
            ansArr[i + j + 1] += x * y
        }
    }

    for i := m + n - 1; i > 0; i-- {
        ansArr[i - 1] += ansArr[i] / 10
        ansArr[i] %= 10
    }

    //存储最终结果
    ans := ""
    idx := 0
    if ansArr[0] == 0 {
        idx = 1
    }
    for ; idx < m + n; idx++ {
        //整形转换为字符串
        ans += strconv.Itoa(ansArr[idx])
    }

    return ans
}

参考链接：https://leetcode-cn.com/problems/multiply-strings/solution/zi-fu-chuan-xiang-cheng-by-

这篇关于算法：字符串相乘的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！