累加数
LeetCode 306. 累加数
1. 问题描述:
给定一个字符串 num
,判断它是否为累加数。
累加序列的要求:
- 序列中必须至少包含 3 个数。
- 除第一个和第二个数字外,每个数字等于前两个数字之和。
- 给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。如果是,返回
true
;否则,返回false
。
数字要求:
- 除了 "0" 之外,其他数字不能以 0 开头。
说明:累加序列里的数,除数字 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)组成
2. 解题思路
要判断给定的字符串 num
是否为累加数,我们需要尝试不同的分割方式,将字符串分割成多个数字,然后验证是否满足累加序列的要求。
确定分割的范围:
因为序列至少包含 3 个数,所以我们可以通过两层循环来枚举前两个数字的结束位置,从而确定前两个数字,然后根据它们来推导出后续数字并验证。第一层循环可以用来确定第一个数的结束位置(范围从索引 0 到字符串长度减 2,要保证至少还能有两个数),第二层循环用来确定第二个数的结束位置(范围从第一个数结束位置的下一个索引到字符串长度减 1,同样要保证后面还能有至少一个数)。
获取前两个数字并进行合法性判断:
从字符串中按照确定的分割位置截取得到前两个数字对应的字符串表示,需要检查它们是否满足数字不能以 0 开头(除了单独的 "0" 这个数字外)的要求,如果不符合直接跳过当前的分割情况继续下一种尝试。
推导后续数字并验证:
根据前两个数字计算出它们的和,然后从字符串中继续往后找,看能否找到对应的数字(也就是看后续的字符串子串能否匹配上计算出来的和对应的字符串表示),如果能找到就继续重复这个过程,用新得到的数字和前面的数字继续求和,再往后找匹配的数字,只要这个过程能一直持续到字符串末尾,说明它是一个累加数;如果在中间某个地方找不到匹配的数字或者出现不符合要求的情况,那就说明不是累加数。
3. 代码
def isAdditiveNumber(num):
# 判断是否可以形成有效的累加数
def is_valid_addition(num1, num2, remaining):
while remaining:
next_num = str(int(num1) + int(num2)) # 计算下一个数
if not remaining.startswith(next_num): # 验证是否匹配
return False
remaining = remaining[len(next_num):] # 更新剩余字符串
num1, num2 = num2, next_num # 更新前两个数字
return True
n = len(num)
# 枚举前两个数字的分割点
for i in range(1, n // 2 + 1): # 第一个数字的长度
for j in range(i + 1, n): # 第二个数字的起点
num1, num2 = num[:i], num[i:j]
# 排除前导零的无效情况
if (len(num1) > 1 and num1[0] == "0") or (len(num2) > 1 and num2[0] == "0"):
continue
# 验证剩余部分是否能形成累加数
if is_valid_addition(num1, num2, num[j:]):
return True
return False
# 示例测试
print(isAdditiveNumber("112358")) # 输出:True
print(isAdditiveNumber("199100199")) # 输出:True
print(isAdditiveNumber("123")) # 输出:True
print(isAdditiveNumber("1023")) # 输出:False