LeetCode 306. Additive Number

GeekQiaQia 發布于2019-07-31 10:03 / 582人閱讀

摘要：描述累加數是一個字符串，組成它的數字可以形成累加序列。一個有效的累加序列必須至少包含個數。說明累加序列里的數不會以開頭，所以不會出現或者的情況。示例輸入輸出解釋累加序列為。

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

源代碼文件在這里.
?本文首發于何睿的博客，歡迎轉載，轉載需保留文章來源，作者信息和本聲明.

GPU云服務器云服務器 Additive 306云服務器 LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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