leetcode 43. 字符串相乘

leetcode 43. 字符串相乘

题目描述

43. 字符串相乘

给定两个以字符串形式表示的非负整数 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本身。

解题思路

法1

模拟相乘:\

1. 其实我们只需要进行两步操作:
2. 第一:将字符串转换为int数据

将每一个字符单独提取出来,减去'0'再转换为int类型就是当前的数字了

再乘以位数(个位乘1,十位*10以此类推)

依次循环求和就可以得到结果数字了

3. 第二:对int数据进行乘法运算

我们可以使用加法原理,先计算第一个的数值,在第二个的时候直接用数值乘以位数再相加求和,循环的结果就是我们需要的结果

比如"1234"*"123"

1. 得出1234
2. 将第二个123分成100+20+3,从最后一位开始

先是r=r+3x1234(开始的r=0)
然后r=r+20x1234 最后r=r+100x1234

最后返回r就可以了

• 时间复杂度(O())
• 空间复杂度(O())

法2

乘法原理:先将两个数转换位int类型
然后直接乘就可以了

比如"1234"*"123"

1. 转换1234
2. 转换123
3. 返回1234x123

执行结果

法1

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

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

    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            mul := int((num1[i] - '0') * (num2[j] - '0'))
            p1 := i + j
            p2 := i + j + 1
            sum := mul + pos[p2]

            pos[p1] += sum / 10
            pos[p2] = sum % 10
        }
    }

    var result strings.Builder
    for _, val := range pos {
        if !(len(result.String()) == 0 && val == 0) {
            result.WriteString(strconv.Itoa(val))
        }
    }

    return result.String()
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2.3 MB , 在所有 Go 提交中击败了 89.13% 的用户 通过测试用例： 311 / 311 炫耀一下: