LeetCode 306. Additive Number

简介: 累加数是一个字符串,组成它的数字可以形成累加序列。一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

v2-52b90b2752f4f77a6e0d2806aa7f5997_1440w.jpg

Description



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.


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


描述



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


一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。


给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 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


思路



  • 这道题可以使用深度优先搜索进行回溯.
  • 我们使用深度优先搜索,找到所有可能拆分给定字符串的方式,然后我们判断当前的拆分方式是否能构成累加数,如果可以,我们用res记录为True,否则为False.
  • __valid函数用于判断当前的组合方式是否能构成累加数,注意:累加数至少需要三个.


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-11 20:50:12
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-11 21:25:41
class Solution:
    def isAdditiveNumber(self, num: 'str') -> 'bool':
        # 根据题意,累计加数至少有三个
        if len(num) < 3: return False
        self.res = False
        # 深度优先搜索,遍历所有可能的解
        self.__dfs(0, num, [])
        return self.res
    def __dfs(self, start, num, coms):
        # 递归结束条件,当num中没有数字时,检查当前组合是否满足条件
        if start == len(num):
            # 如果当前组合合法,我们将self.res置为True
            if self.__valid(coms): self.res = True
            return
        # 记录起始位置
        index = start
        while index < len(num):
            # 如果当前数字的起始数字是"0'退出循环(注意单独一个'0'本身是合法的)
            if num[start] == "0" and index != start: break
            # 如果当前的组合已经有了至少3个数,我们检查前面的所有数是否是累加数
            # 如果不是我们退出循环,表示当前的分支不用再查找,减少时间
            if len(coms) > 2 and not self.__valid(coms): break
            # 递归遍历分支
            self.__dfs(index + 1, num, coms + [num[start:index + 1]])
            index += 1
    def __valid(self, coms):
        # 如果一共都没有三个数,返回False
        if len(coms) < 3: return False
        for i in range(len(coms) - 2):
            # 只要有一个不满足累加数的条件,返回False
            if int(coms[i]) + int(coms[i + 1]) != int(coms[i + 2]):
                return False
        return True


源代码文件在这里.


目录
相关文章
|
11月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
92 1
|
4月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
5月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
39 0
|
11月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
36 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
88 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
91 0
LeetCode 313. Super Ugly Number