Go实现字符串相乘无溢出最详细解释

陌无崖

发布于 2020-07-27 11:08:57

1.2K0

文章被收录于专栏：陌无崖知识分享陌无崖知识分享

作者 | 陌无崖

转载请联系授权

导语

今天在leecode看到了字符串相乘的题，拿来做一下，要做到匹配任意两个数字字符串还是有一定的难度的，在网上看了很多关于Go语言如何解决的，都不全，因此在这里我自己写了一个全面的没有bug的代码逻辑。亲测已经成功。

字符串相乘

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

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

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

num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头，除非是数字 0 本身。不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

注意

该题需要注意的是对于大数如何保证结果不会溢出比如9999999999999999999999999999999999999999999999999999999999999999999999999
9999999999999999999999999999999999999999999 * 999999999999999999999999999999999999999999999999999999999999999999999999

解题思路

对于上面的题，为了避免大数溢出，我们肯定不能使用编程语言中的乘法进行直接输出，首先想到的思路就是按照数学方法应该会怎么算。拿999 * 999 举例，我们的计算如下：

1	2	3	4	5
		81	81	81
	81	81	81
81	81	81
81	162	243	162	81

我们采用二维表的格式显示出来最后一行为的每一列的值为相同列的值进行相加得出，我们暂时没有对我们的最终结果采取进位措施。最终结果我们可以根据最后一行的数据进行进位得出，如下：

1、81 进位为8 留 1
2、162 + 8 进位为17 留 0
3、243 + 17 进位为26 留 0
4、162 + 26 进位为18 留 8
5、81 + 18 进位 为 9 留 9
6、因为接下来没有需要进位的，因此保留上一步骤进位 9
7、最终结果为 998001

因此我们只需要最终保留了最后需要进位的数字就可以算出最终的结果，把他们保存到数组中。因为我们是从右边的81开始算起，为了符合我们的理解思维，我们对我们的上面的二维表进行反转，如下所示

0	1	2	3	4
81	81	81
	81	81	81
		81	81	81
81	162	243	162	81

那我们怎么才能得到每一行的数据，并对每一行进行错位相加呢。我们拿123 * 456 进行举例，我们将这两个字符串想象成一个数组

a = [1,2,3]
b = [4,5,6]
//反转
a = [3,2,1]
b = [6,5,4]

我们可以很轻易的发现我们的 i + j 刚好对应了我们的最终的下标，因此我们只需要对a,b相同下标的进行相加即可。

代码逻辑

1、字符串反转 2、遍历我们的字符串，下表相加一直的进行相加，可以借助于 += 3、遍历我们的最终结果，不停的进行进位，为了有一个结束，我们可以对最后的一个数放置0，

代码

1、首先我们需要一个字符串反转的函数如下，比较简单，首尾替换即可，不作详细解释

func Reverse(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

2、定义我们的字符串相乘的函数

func LargeNumberMultiplication(a string, b string) (reuslt string) {
	if (a[0]-'0') == 0 || (b[0]-'0') == 0 {
		return "0"
	}
	a = Reverse(a)
	b = Reverse(b)

	var c []int
	c = make([]int, len(a)+len(b))

	for i := 0; i < len(a); i++ {
		for j := 0; j < len(b); j++ {
			t := int((a[i] - '0') * (b[j] - '0'))
			c[i+j] += t
		}
	}
	// fmt.Println(c)
	// 表示进位
	var plus int = 0
	for i := 0; i < len(c); i++ {
		temp := c[i] + plus
		plus = 0
		if c[i] == 0 && i == len(c)-1 {
			if temp != 0 {
				reuslt += string(temp + '0')
			}
			break
		}
		// fmt.Println(c)
		if temp > 9 {
			// 得出进位值
			plus = temp / 10
			reuslt += string(temp - plus*10 + '0')
		} else {
			reuslt += string(temp + '0')
		}

	}

	return Reverse(reuslt)
}

函数细节解释

1、首先我们需要判断，如果字符串中含有0 我们需要直接返回 0

if (a[0]-'0') == 0 || (b[0]-'0') == 0 {
		return "0"
}

2、字符转换成数字进行相乘我们可以借助 -'0'完成，不理解的可以查看ASSIC值对照表。为什么需要进行int强制抓换，因为不进行转换，类型为uint8，范围过于小，会出现数字溢出的情况。

t := int((a[i] - '0') * (b[j] - '0'))

3、对于求相同下标的和，因为我们无法判断字符串的长度，我们需要利用+=进行求和/

for i := 0; i < len(a); i++ {
	for j := 0; j < len(b); j++ {
        t := int((a[i] - '0') * (b[j] - '0'))
        c[i+j] += t
    }
}

4、最后在结束的时候我们不仅需要判断存放结果的数组中的值为0，还要判断是否是最后一个值。因为有可能相加后的值为0，比如110 * 10

if c[i] == 0 && i == len(c)-1 {
    if temp != 0 {
        reuslt += string(temp + '0')
    }
    break
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-12-07，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 golang技术杂文微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度