未分類

Additive Number

Go, LeetCode

Additive Number

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:

“112358” is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

“199100199” is also an additive number, the additive sequence is: 1, 99, 100, 199.

1
1 + 99 = 100, 99 + 100 = 199

Note:

Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Follow up:

How would you handle overflow for very large input integers?

Default:

1
2
3
func isAdditiveNumber(num string) bool {
}

解答思路:

這題需要拆分成兩個階段來處理，最初要先找出第一個組合(第一個數+第二個數=第三個數的總合)，也就是說透過巢狀迴圈將第一個數可能長度的值與第二個數可能長度的值做排列組合，進而找出符合條件第三個數的總合，待第一個組合出來便可進行下一個階段，將第二個數賦予至第一個數，第三個數賦予至第二個數，再確認後頭新的第三個數是否符合前兩個數的總合，如果不符合條件便回到第一個階段重新找尋新的組合，否則就不斷重覆上述動作直到數列全數確認完畢為止，唯一要注意的是數列由字串所組合而成，所以在取出第一個數與第二個數做相加前需要將其轉換為數字型別，然而如果兩個取出的字串極大(超過int32能儲存的範圍，甚至是int64)，可以參考Add Strings從字串一個個字元相加的方式來做計算。

程式碼解說:

如思路所述最初要先找出第一個組合(第一個數+第二個數=第三個數的總合)，也就是說透過巢狀迴圈將第一個數可能長度的值與第二個數可能長度的值做排列組合，如果其長度大於1且開頭為0便跳過(如果是發生在第一個數則結束迴圈)，由於取出的皆為字串型別，因此需要分別將其轉換為數字型別相加做為第三個數的總合再轉回字串，接著先判斷第三個數可能的位置是否仍位於數列範圍之中且與先前的總合是否相同，如果都符合條件，表示已經找出第一個組合便可進行下一個階段，而如果都完全沒有則待全數數列組合遍歷結束後回傳false

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
var tmp1 int
var tmp2 int
var first string
var second string
var third string
var result bool
var length int
for i := 0; i < len(num); i++ {
	first = num[:i+1]
	if len(first) > 1 && first[0] == '0' {
		break
	}
	tmp1, _ = strconv.Atoi(first)
	for j := i + 1; j < len(num); j++ {
		second = num[i+1 : j+1]
		if len(second) > 1 && second[0] == '0' {
			continue
		}
		tmp2, _ = strconv.Atoi(second)
		third = strconv.Itoa(tmp1 + tmp2)
		if j+1+len(third) <= len(num) && third == num[j+1:j+1+len(third)] {
		...
		}
	}
}
return false

有了第一組個組合，接下來就是要檢查剩餘的組合是否皆符合條件(1+2=3)，一直到全數組合都確認完畢為止(已取出值的總長度等於數列的長度)，將第二個數賦予至第一個數，第三個數賦予至第二個數，再確認後頭新的第三個數是否符合前兩個數的總合(一樣要檢查位置是否仍位於數列範圍之中)，符合條件的話便將第三個數的長度加總至已取出值的總長度，不符合條件便回到第一個階段重新找尋新的組合，並將一開始初始化註記的true改為false後結束迴圈(記得要將第一個數還原回去，有可能原來第一個數與第二個數的其它組合能符合條件)，最後就不斷重覆上述動作直到迴圈結束，如果註記的結果仍為true便確定此數列為Additive Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
result = true
length = len(first) + len(second) + len(third)
for length < len(num) {
	first = second
	tmp1, _ = strconv.Atoi(first)
	second = third
	tmp2, _ = strconv.Atoi(second)
	third = strconv.Itoa(tmp1 + tmp2)
	if length+len(third) <= len(num) && third == num[length:length+len(third)] {
			length += len(third)
	} else {
		first = num[:i+1]
		tmp1, _ = strconv.Atoi(first)
		result = false
		break
	}
}
if result {
	return true
}

完整程式碼:

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
func isAdditiveNumber(num string) bool {
	var tmp1 int
	var tmp2 int
	var first string
	var second string
	var third string
	var result bool
	var length int
	for i := 0; i < len(num); i++ {
		first = num[:i+1]
		if len(first) > 1 && first[0] == '0' {
			break
		}
		tmp1, _ = strconv.Atoi(first)
		for j := i + 1; j < len(num); j++ {
			second = num[i+1 : j+1]
			if len(second) > 1 && second[0] == '0' {
				continue
			}
			tmp2, _ = strconv.Atoi(second)
			third = strconv.Itoa(tmp1 + tmp2)
			if j+1+len(third) <= len(num) && third == num[j+1:j+1+len(third)] {
				result = true
				length = len(first) + len(second) + len(third)
				for length < len(num) {
					first = second
					tmp1, _ = strconv.Atoi(first)
					second = third
					tmp2, _ = strconv.Atoi(second)
					third = strconv.Itoa(tmp1 + tmp2)
					if length+len(third) <= len(num) && third == num[length:length+len(third)] {
						length += len(third)
					} else {
						first = num[:i+1]
						tmp1, _ = strconv.Atoi(first)
						result = false
						break
					}
				}
				if result {
					return true
				}
			}
		}
	}
	return false
}

總結:

要確認一數列是否符合Additive Number(詳情請參考範例)，需要拆分成兩個階段來處理，最初要先找出第一個組合(第一個數+第二個數=第三個數的總合)，也就是說透過巢狀迴圈將第一個數可能長度的值與第二個數可能長度的值做排列組合，進而找出符合條件第三個數的總合，待第一個組合出來便可進行下一個階段，將第二個數賦予至第一個數，第三個數賦予至第二個數，再確認後頭新的第三個數是否符合前兩個數的總合，如果不符合條件便回到第一個階段重新找尋新的組合，否則就不斷重覆上述動作直到數列全數確認完畢為止。

分享到