- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/additive-number/description/
Additive number is a string whose digits can form additive sequence.
Avalid 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.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Example 1:
Input: "112358"
Output: true
Explanation: 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
Example 2:
Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Follow up:
给出了一个有0-9数字组成的纯数字字符串。判断它能不能组成所谓的“加法数字”,即费布拉奇数列。注意这个题注重点在不管你几位数字去划分,只要满足后面的数字等于前两个的和即可。
是不是很眼熟呢?和我们刚刚做过的判断是否是有效的IP93. Restore IP Addressesopen in new window如出一辙:使用回溯法+合理剪枝。
因为只要判断能否构成即可,所以不需要res数组保存结果。回溯法仍然是对剩余的数字进行切片,看该部分切片能否满足条件。剪枝的方法是判断数组是否长度超过3,如果超过那么判断是否满足费布拉奇数列的规则。不超过3或者已经满足的条件下继续进行回溯切片。最后当所有的字符串被切片完毕,要判断下数组长度是否大于等于3,这是题目要求。
代码如下:
class Solution(object):
def isAdditiveNumber(self, num):
"""
:type num: str
:rtype: bool
"""
return self.dfs(num, [])
def dfs(self, num_str, path):
if len(path) >= 3 and path[-1] != path[-2] + path[-3]:
return False
if not num_str and len(path) >= 3:
return True
for i in range(len(num_str)):
curr = num_str[:i+1]
if (curr[0] == '0' and len(curr) != 1):
continue
if self.dfs(num_str[i+1:], path + [int(curr)]):
return True
return False
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我对编程非常陌生(所以我提前道歉),并且我无法弄清楚如何创建一个 for 循环来执行以下操作: 我要求用户输入两个变量(我将它们称为 x 和 y),然后我计算 x/y = z。我想提出这个两个变量输入
我正在尝试对 vector 使用累加函数 vector A; double B = 0; A.reserve(100); for(itr = 0; itr < 210; itr++) { t
如果我想累积 std::vector 的绝对值,我可以使用 lambda 来计算绝对值并将其添加到 std::accumulate #include int main (){ std::ve
所以我需要使用 accumulate 对 vector 中的一些 double 值求和,其中我的 VECTOR 实际上是指向对象的指针。 现在,当我将 accumulate 与 int 一起用于 in
假设我有一个 (None, 2)-shape 张量 indices 和 (None,)-shape 张量 values。这些实际行号和值将在运行时确定。 我想设置一个 4x5 张量 t,索引的每个元素
我有一小部分固定节点: , , , .每个节点的值可以是 1 或 0。此外,每个节点的权重分别为:1、2、3、4。不使用节点属性。如何使用 XSLT 1.0 将每个节点的值乘以其权重相加?示例:
目前我在下面有一个数据集,如果 ColA 为 0,我尝试累加该值,而如果 ColA 再次为 1,则将值重置为 0(再次重新开始计数)。 ColA 1 0 1
我是一名优秀的程序员,十分优秀!