0306：累加数（★）

Ian

2015-11-02 约 514 字预计阅读 2 分钟次阅读

力扣第 306 题

题目

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须至少包含 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）组成

进阶：你计划如何处理由过大的整数输入导致的溢出?

分析

#1

类似 0093，回溯即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def dfs(i):
            if len(path)>=3 and path[-1]!=path[-2]+path[-3]:
                return False
            if i == n:
                return len(path)>2
            for j in range(i+1, n+1 if num[i]!='0' else i+2):
                path.append(int(num[i:j]))
                if dfs(j):
                    return True
                path.pop()
            return False

        path, n = [], len(num)
        return dfs(0)

46 ms

#2

也可以先确定前两个数，然后递推序列是否符合即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def check(a,b,s):
            while s:
                c = str(int(a)+int(b))
                if s[:len(c)]!=c:
                    return False
                s = s[len(c):]
                a,b = b,c
            return True
        n = len(num)
        if n<3:
            return False
        for i in range(1 if num[0]=='0' else n-2):
            for j in range(i+1,i+2 if num[i+1]=='0' else n-1):
                if check(num[:i+1],num[i+1:j+1],num[j+1:]):
                    return True
        return False

29 ms

目录

0306：累加数（★）

题目

分析

#1

#2

解答