累加数
累加数 是一个字符串,组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是 累加数 。如果是,返回 true ;否则,返回 false 。
说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
- 示例 1:
输入:"112358"
输出:true
解释:累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
- 示例 2:
输入:"199100199"
输出:true
解释:累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
提示:
1 <= num.length <= 35
num 仅由数字(0 - 9)组成
方法一:穷举法(java)
一个累加序列,当它的第一个数字和第二个数字以及总长度确定后,这整个累加序列也就确定了。
根据这个性质,我们可以穷举累加序列的第一个数字和第二个数字的所有可能性,对每个可能性,进行一次合法性的判断。
当出现一次合法的累加序列后,即可返回true。
当所有可能性都遍历完仍无法找到一个合法的累加序列时,返回 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
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
|
class Solution { public boolean isAdditiveNumber(String num) { int n = num.length(); for ( int secondStart = 1 ; secondStart < n - 1 ; ++secondStart) { if (num.charAt( 0 ) == '0' && secondStart != 1 ) { break ; } for ( int secondEnd = secondStart; secondEnd < n - 1 ; ++secondEnd) { if (num.charAt(secondStart) == '0' && secondStart != secondEnd) { break ; } if (valid(secondStart, secondEnd, num)) { return true ; } } } return false ; } public boolean valid( int secondStart, int secondEnd, String num) { int n = num.length(); int firstStart = 0 , firstEnd = secondStart - 1 ; while (secondEnd <= n - 1 ) { String third = stringAdd(num, firstStart, firstEnd, secondStart, secondEnd); int thirdStart = secondEnd + 1 ; int thirdEnd = secondEnd + third.length(); if (thirdEnd >= n || !num.substring(thirdStart, thirdEnd + 1 ).equals(third)) { break ; } if (thirdEnd == n - 1 ) { return true ; } firstStart = secondStart; firstEnd = secondEnd; secondStart = thirdStart; secondEnd = thirdEnd; } return false ; } public String stringAdd(String s, int firstStart, int firstEnd, int secondStart, int secondEnd) { StringBuffer third = new StringBuffer(); int carry = 0 , cur = 0 ; while (firstEnd >= firstStart || secondEnd >= secondStart || carry != 0 ) { cur = carry; if (firstEnd >= firstStart) { cur += s.charAt(firstEnd) - '0' ; --firstEnd; } if (secondEnd >= secondStart) { cur += s.charAt(secondEnd) - '0' ; --secondEnd; } carry = cur / 10 ; cur %= 10 ; third.append(( char ) (cur + '0' )); } third.reverse(); return third.toString(); } } |
时间复杂度:o(n^3)
空间复杂度:o(n)
方法二:深度优先遍历(go)
对字符串num进行回溯,回溯过程中截取字符串diff,如果diff的首字符是'0',则不进行处理,否则判断前两个元素相加是否能得到diff
由于num.length的范围在[1, 35],所以如果用long存储的话,最终可能会超限,所以这里使用字符串数组记录。
记录过程中类似于两数相加,最后将较长的那个数组拼在结果数组中。 对最终数组进行进位处理。
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
|
func add(a, b string ) string { res, one := [] byte {}, 0 for i, j := len (a) - 1 , len (b) - 1 ; i >= 0 || j >= 0 ; { curA, curB := 0 , 0 if i >= 0 { curA = int (a[i] - '0' ) i-- } if j >= 0 { curB = int (b[j] - '0' ) j-- } cur := curA + curB + one one = cur/ 10 res = append (res, byte (cur% 10 )+ '0' ) } if one == 1 { res = append (res, '1' ) } for i, n := 0 , len (res); i < n/ 2 ; i++ { res[i], res[n- 1 -i] = res[n- 1 -i], res[i] } return string (res) } func dfs(num string , first, second int ) bool { n, last := len (num), 0 for second < n { if (num[last] == '0' && first > last + 1 ) || (num[first] == '0' && second > first + 1 ){ return false } s := add(num[last:first], num[first:second]) if second + len (s) > n || num[second:second + len (s)] != s { return false } last, first, second = first, second, second + len (s) } return true } func isAdditiveNumber(num string ) bool { for i:= 1 ;i< len (num)- 1 ;i++ { for j:=i+ 1 ;j< len (num);j++{ if dfs(num, i, j){ return true } } } return false } |
以上就是Go Java算法之累加数示例详解的详细内容,更多关于Go Java算法累加数的资料请关注服务器之家其它相关文章!
原文链接:https://juejin.cn/post/7133962061301678094