LeetCode 306. Additive Number

GeekQiaQia 发布于2019-07-31 10:03 / 365人阅读

摘要：描述累加数是一个字符串，组成它的数字可以形成累加序列。一个有效的累加序列必须至少包含个数。说明累加序列里的数不会以开头，所以不会出现或者的情况。示例输入输出解释累加序列为。

LeetCode 306. Additive Number 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

源代码文件在这里.
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.

海外云主机云服务器 Additive 306云服务器 LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43169.html

leetcode306. Additive Number

摘要：为了减少无效遍历，我们可以在寻找第一个数字和第二个数字的时候及时终止。我们可以知道第一个数字的长度不应该超过字符串长度的一般，第二个数字的长度无法超过字符串长度减去第一个数字的长度。因此一旦遇到，在判断完作为加数时是否合法后，直接跳出循环。题目要求 Additive number is a string whose digits can form additive sequence....

2shou 2019-08-15 15:09 评论0 收藏0
306. Additive Number

摘要：题目解答不越界长度的当可以走到后面没有和了的时候，说明这个满足条件直接可以知道这个是不是存在于中越界长度的越界长的度题目：Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers...

dkzwm 2019-08-14 14:23 评论0 收藏0
306. Additive Number

For example: 112358 is an additive number because 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 199100199 is also an additive number, the addi...

eccozhou 2019-08-16 10:36 评论0 收藏0
[LeetCode] Additive Number

Additive Number 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 ...

yibinnn 2019-08-14 16:38 评论0 收藏0
容器最大盛水量

摘要：容器最大盛水量给定个非负整数，，，，其中每个表示坐标，处的点。找到两条线，它们与轴一起形成一个容器，使得容器含有最多的水。容器最大盛水量 Container With Most Water 给定n个非负整数a1，a2，...，an，其中每个表示坐标（i，ai）处的点。绘制n条垂直线，使得线i的两个端点在（i，ai）和（i，0）处。找到两条线，它们与x轴一起形成一个容器，使得容器...

luckyw 2019-07-25 12:04 评论0 收藏0