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?
if j+1+len(third) <= len(num) && third == num[j+1:j+1+len(third)] {
...
}
}
}
returnfalse
有了第一組個組合，接下來就是要檢查剩餘的組合是否皆符合條件(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 {
returntrue
}
完整程式碼:
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
funcisAdditiveNumber(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]
iflen(first) > 1 && first[0] == '0' {
break
}
tmp1, _ = strconv.Atoi(first)
for j := i + 1; j < len(num); j++ {
second = num[i+1 : j+1]
iflen(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)] {
