未分類

Add Strings

Go, LeetCode, Math

Add Strings

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

Note:

  1. The length of both num1 and num2 is < 5100.
  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 規律觀查

Default:

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

解答思路:

這題解法與我在ADD Binary極為相似，不過一開始的時候原本是直接各別將兩個數字的字串自行轉成數字相加後再轉回字串，然而題目有說數字的長度最長可以到5000多，所以一定是行不通會造成溢位，因此只能像二進位相加那樣，一個位元(或每個位數)慢慢相加處理再轉回字串，本題大致上來說就是將兩字串先從個位數開始計算，先將個位數字串轉為數字相加後再轉回字串(皆為利用ASCII轉換)，同時判斷是否超過10而標註進位，接著才繼續相加下一個位數，如果前一位數有進位就要記得再+1，最後重覆上述動作直到相加結束。

程式碼解說:

一開始先取得兩字串的長度，因為在同時一一取出數字字串時可能發生其一已經取完了，而另一則還有數字尚未取出，因此在用迴圈無窮取出時，誰先將數字取完就成了終止條件，此時先將另一字串尚未取完的部分保存下來，同時順便計算長度以利後續處理，若兩字串皆尚未取出完畢，將分別取出的數字字串轉為數字，因字串”0”的ASCII為48，所以要先將rune值減去48再將其轉回數字，接著將兩個分別取出的數字做相加，如果先前有進位的情況則要再+1，接著再次判斷加否有超過10，如果有則標註為有進位true的狀況，沒有則將其改為false，最後再跟10取餘數，而這次要變回ASCII中的字串，所以要再加上48才轉回字串，最後才繼續處理下一個位數的相加

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
31
var result string
var sum int
var tmp string
var length int
var carry bool
len1 := len(num1)
len2 := len(num2)
for true {
	if len1 == 0 {
		tmp = num2[0:len2]
		length = len(tmp)
		break
	}
	if len2 == 0 {
		tmp = num1[0:len1]
		length = len(tmp)
		break
	}
	sum = int(num1[len1-1]-48) + int(num2[len2-1]-48)
	if carry {
		sum++
	}
	if sum >= 10 {
		carry = true
	} else {
		carry = false
	}
	result = string((sum%10)+48) + result
	len1--
	len2--
}

上述處理完畢後，再來就是尚未取出的數字，因為相加大致上都已經處理完畢，只剩前面尚未取出的位數與上述完成相加後是否還有進位，因此若還有進位的情況迴圈就繼續處理，或者連未取出的部分都已經完全取出了但還是有進位的情況，表示相加後長度又增長了，此時只要在結果前面加上進位的”1”即可，若是有進位而數字也尚未完全取出，這時一樣也就是先將rune值減去48後再轉為數字，因為有進位所以+1，再來也是判斷有沒有超過10，沒有就標註false並且一樣轉回數字放入結果開頭，因為這部分只剩未取出的位數與進位的問題，所以一但沒有進位那麼後面也不會再進位了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for carry {
	if length == 0 {
		if carry {
			result = "1" + result
		}
		break
	}
	sum = int(tmp[length-1]-48) + 1
	if sum < 10 {
		carry = false
	}
	result = string((sum%10)+48) + result
	length--
}

因為可能進位只到一半就結束了，可能前面還是有未處理的數字，此時只要判斷先前剩餘的部分長度加否大於0，如果是就把最後剩下的全部直接放入結果開頭節可，若都已經沒有剩餘的部分則直接回傳結果

1
2
3
4
if length > 0 {
	result = tmp[0:length] + result
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
func addStrings(num1 string, num2 string) string {
	var result string
	var sum int
	var tmp string
	var length int
	var carry bool
	len1 := len(num1)
	len2 := len(num2)
	for true {
		if len1 == 0 {
			tmp = num2[0:len2]
			length = len(tmp)
			break
		}
		if len2 == 0 {
			tmp = num1[0:len1]
			length = len(tmp)
			break
		}
		sum = int(num1[len1-1]-48) + int(num2[len2-1]-48)
		if carry {
			sum++
		}
		if sum >= 10 {
			carry = true
		} else {
			carry = false
		}
		result = string((sum%10)+48) + result
		len1--
		len2--
	}
	for carry {
		if length == 0 {
			if carry {
				result = "1" + result
			}
			break
		}
		sum = int(tmp[length-1]-48) + 1
		if sum < 10 {
			carry = false
		}
		result = string((sum%10)+48) + result
		length--
	}
	if length > 0 {
		result = tmp[0:length] + result
	}
	return result
}

總結:

要將兩數字字串相加並回傳字串，且不得使用任何library，大致上來說就是將兩字串先從個位數開始計算，先將個位數字串轉為數字相加後再轉回字串(皆為利用ASCII轉換)，同時判斷是否超過10而標註進位，接著才繼續相加下一個位數，如果前一位數有進位就要記得再+1，最後重覆上述動作直到相加結束。

分享到