0306. 累加数【中等】
1. 📝 题目描述
累加数 是一个字符串,组成它的数字可以形成累加序列。
一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和。
给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是 累加数。如果是,返回 true ;否则,返回 false。
说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 1:
txt
输入:"112358"
输出:true
解释:累加序列为: 1, 1, 2, 3, 5, 8。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 81
2
3
2
3
示例 2:
txt
输入:"199100199"
输出:true
解释:累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 1991
2
3
2
3
提示:
1 <= num.length <= 35num仅由数字(0-9)组成
进阶:你计划如何处理由过大的整数输入导致的溢出?
2. 🎯 s.1 - 枚举 + 大数加法
c
char* addStrings(const char* a, const char* b) {
int la = strlen(a), lb = strlen(b);
int maxLen = (la > lb ? la : lb) + 2;
char* res = (char*)calloc(maxLen, 1);
int i = la - 1, j = lb - 1, k = maxLen - 2, carry = 0;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += a[i--] - '0';
if (j >= 0) sum += b[j--] - '0';
res[k--] = sum % 10 + '0';
carry = sum / 10;
}
return res + k + 1;
}
bool isAdditiveNumber(char* num) {
int n = strlen(num);
for (int i = 1; i <= n / 2; i++) {
for (int j = i + 1; j < n; j++) {
if (i > 1 && num[0] == '0') break;
if (j - i > 1 && num[i] == '0') continue;
char s1[n + 1], s2[n + 1];
strncpy(s1, num, i); s1[i] = '\0';
strncpy(s2, num + i, j - i); s2[j - i] = '\0';
char *a = strdup(s1), *b = strdup(s2);
int pos = j;
while (pos < n) {
char* c = addStrings(a, b);
int cl = strlen(c);
if (strncmp(num + pos, c, cl) != 0) break;
pos += cl;
a = b;
b = c;
}
if (pos == n) return true;
}
}
return 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
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
js
/**
* @param {string} num
* @return {boolean}
*/
var isAdditiveNumber = function (num) {
const n = num.length
function addStrings(a, b) {
let i = a.length - 1,
j = b.length - 1,
carry = 0,
res = ''
while (i >= 0 || j >= 0 || carry) {
const sum = (i >= 0 ? +a[i--] : 0) + (j >= 0 ? +b[j--] : 0) + carry
res = (sum % 10) + res
carry = Math.floor(sum / 10)
}
return res
}
for (let i = 1; i <= Math.floor(n / 2); i++) {
for (let j = i + 1; j < n; j++) {
const s1 = num.slice(0, i),
s2 = num.slice(i, j)
if (s1.length > 1 && s1[0] === '0') break
if (s2.length > 1 && s2[0] === '0') continue
let a = s1,
b = s2,
pos = j
while (pos < n) {
const c = addStrings(a, b)
if (!num.startsWith(c, pos)) break
pos += c.length
a = b
b = c
}
if (pos === n) return true
}
}
return 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
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
py
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
n = len(num)
for i in range(1, n // 2 + 1):
for j in range(i + 1, n):
s1, s2 = num[:i], num[i:j]
if len(s1) > 1 and s1[0] == '0':
break
if len(s2) > 1 and s2[0] == '0':
continue
a, b, pos = s1, s2, j
while pos < n:
c = str(int(a) + int(b))
if not num.startswith(c, pos):
break
pos += len(c)
a, b = b, c
if pos == n:
return True
return False1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
- 时间复杂度:
,其中 是字符串长度 - 空间复杂度:
,存储中间字符串
算法思路:
- 枚举前两个数的分割位置,然后不断验证后续是否满足累加关系
- 使用字符串加法避免大数溢出,注意跳过前导零