leetcode Additive Number

leetcode Additive Number

Additive number is a positive integer 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.

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string represents an integer, write a function to determine if it’s an additive number.

题目地址 : leetcode Additive Number

题意:

给定一串字符串,让你判断是否可以按顺序划分成诺干个数(三个以上),其中前面的两个数和等于第三个数。

如112358划分为1,1,2,3,5,8恰好满足。

注意,划分的数字不能有前导0

思路:

其实只要前两个数固定了,后面是否能划分就是确定的了。

因为前两个数决定了第三个数,第三个数和第二个数决定了第四个。。。

所以,枚举前两个数的终点位置,进行递归判断即可。

1A水过~

Code

Python

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Additive Number
本文地址:https://www.hrwhisper.me/leetcode-additive-number/

您的支持将鼓励我继续创作!

Leetcode , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *