-
Notifications
You must be signed in to change notification settings - Fork 1
/
seq.go
70 lines (66 loc) · 1.28 KB
/
seq.go
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package seq
import (
"fmt"
"math"
"strconv"
"github.com/catorpilor/leetcode/utils"
)
func splitIntoFib(s string) []int {
var res []int
n := len(s)
if n < 3 {
return res
}
// same idea as additive number
// i, j represents the length of the x1, x2
for i := 1; i <= n/2; i++ {
for j := 1; utils.Max(j, i) <= n-i-j; j++ {
r, f := isValid(i, j, n, s)
if f {
return r
}
}
}
return res
}
func isValid(i, j, n int, s string) (res []int, f bool) {
if s[0] == '0' && i > 1 {
return
}
if s[i] == '0' && j > 1 {
return
}
x1, _ := strconv.ParseInt(s[:i], 10, 64)
x2, _ := strconv.ParseInt(s[i:i+j], 10, 64)
tmp1, tmp2 := x1, x2
var sum string
for start := i + j; start != n; start += len(sum) {
tmp2 += tmp1
tmp1 = tmp2 - tmp1
if tmp1 > math.MaxInt32 || tmp2 > math.MaxInt32 {
return
}
sum = strconv.FormatInt(tmp2, 10)
tn := start + len(sum)
if tn > n {
tn = n
}
if sum != s[start:tn] {
return
}
fmt.Printf("x1:%d, x2:%d,sum:%s,res:%v, start: %d, tn: %d\n", x1, x2, sum, res, start, tn)
// res = append(res, x1, x2, tmp2)
if len(res) == 0 {
res = append(res, int(x1), int(x2), int(tmp2))
} else {
res = append(res, int(tmp2))
}
// if tn == n {
// res = append(res, tmp2)
// }
x1 = tmp1
x2 = tmp2
}
f = true
return
}