Algorithm

每日一刷-Additive-Number

[每日一刷] (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 = 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 + 99 = 100, 99 + 100 = 199**

解题思路


这题个人感觉应该没什么trick，只能硬算了，整个数列其实都是由最开始的两个数决定的，而最开始的两个数只能
通过枚举的方法来尝试符不符合条件了。这题的关键就是要仔细了吧-.-

Python:

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
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n^2)
"""
class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        n = len(num)
        s1 = 0  
        len1, len2 = 1, 1
        while len1 <= n/2:
            s2 = s1 + len1
            len2 = 1
            while len2 <= n/2:
                num1 = int(num[s1:s1+len1])
                num2 = int(num[s2:s2+len2])
                if s2+len2 == n:
                    break
                if self.isAdditive(num, num1, num2, s2+len2, n):
                    return True
                if num[s2] == '0':
                    break;
                len2 += 1
            if num[s1] == '0':
                break
            len1 += 1
        return False
    def isAdditive(self, num, num1, num2, pos, end):
        if pos == end:
            return True
        target = num1 + num2
        i = 1 # target位数
        while target / 10**i != 0:
            i += 1
        num3 = int(num[pos:pos+i])
        if target == num3:
            return self.isAdditive(num, num2, num3, pos+i, end)
        else:
            return 0