未分類

Multiply Strings

Go, LeetCode, Math, String

Multiply Strings

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

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.
提示 解題應用
Math 規律觀查
String ASCII

Default:

1
2
3
func multiply(num1 string, num2 string) string {
}

解答思路:

原本思考是否能與做Add String時一樣，每一位數的結果值可以透過直接計算來獲得，也許可以但畢竟乘法較為複雜需要考慮到太多細節，所以倒不如就紀錄每一位數與另一個值相乘的總合，再將所有總合做相加(其實就是一般在算乘法的做法)，最後才將總合結果的每一位數轉成字串後回傳。

程式碼解說:

一開始先判斷給予的兩數字字串如果任一為”0”就直接回傳字串為”0”的結果，接著才開始準備相乘的工作，你可以用二維陣列來儲存每一位數與另一個值相乘的總合，不過這邊我只有一維陣列來做儲存，因為最後都會要將所有總合做相加，所以倒不如一開始每算完一組總合就直接相加，如此一來也省下不少空間，而陣列初始化長度要多少，透過觀查可以發現兩數字相乘的結果長度不會超過兩數字長度相加，所以就將兩數字長度相加做為結果的最大長度，接著便開始將每一位數與另一個值(該值的每一位數)相乘，記得在取出每一位數時要先將該字元轉為數字的ascii才開始相乘，加上原本該位數的值再與10取餘數最後才放回該位數的位置，這邊要注意的是pos表示要存放的位置，而mov則是因應每一位數會差上10倍，所以每組結果在做存儲時都要記得位移，最後在該位數與另一個值相乘結束前，因為剩餘的值可能表示有進位，因此還要再將剩餘的值加到該位數，結束後才把暫存值歸0以開始計算下一位數

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
if num1 == "0" || num2 == "0" {
	return "0"
}
var sum int
var pos int
var mov int
var result string
data := make([]int, len(num1)+len(num2))
for i := len(num1) - 1; i >= 0; i-- {
	pos = len(num1) + len(num2) - 1
	for j := len(num2) - 1; j >= 0; j-- {
		sum += int(num1[i]-48)*int(num2[j]-48) + data[pos-mov]
		data[pos-mov] = sum % 10
		sum /= 10
		pos--
	}
	data[pos-mov] += sum
	sum = 0
	mov++
}

最後得到陣列的每一元素就是結果值的每一位數，此時便開始一一將每一位數字轉成字串，如果陣列的第一個值為0，表示沒有進位就不需要放入結果之中所以跳過，其餘的位數就是將數字轉成數字的ascii值再強制轉成字串放入結果字串中，最後待每一位數處理完畢後才做回傳

1
2
3
4
5
6
7
for i, v := range data {
	if i == 0 && v == 0 {
		continue
	}
	result += string(v + 48)
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	var sum int
	var pos int
	var mov int
	var result string
	data := make([]int, len(num1)+len(num2))
	for i := len(num1) - 1; i >= 0; i-- {
		pos = len(num1) + len(num2) - 1
		for j := len(num2) - 1; j >= 0; j-- {
			sum += int(num1[i]-48)*int(num2[j]-48) + data[pos-mov]
			data[pos-mov] = sum % 10
			sum /= 10
			pos--
		}
		data[pos-mov] += sum
		sum = 0
		mov++
	}
	for i, v := range data {
		if i == 0 && v == 0 {
			continue
		}
		result += string(v + 48)
	}
	return result
}

總結:

給兩數字字串要回傳兩相乘之後的結果字串，做法如果一般在算乘法的做法，紀錄每一位數與另一個值相乘的總合，再將所有總合做相加，最後才將總合結果的每一位數轉成字串後回傳。

分享到