成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode 306. Additive Number

GeekQiaQia / 590人閱讀

摘要：描述累加數(shù)是一個(gè)字符串，組成它的數(shù)字可以形成累加序列。一個(gè)有效的累加序列必須至少包含個(gè)數(shù)。說(shuō)明累加序列里的數(shù)不會(huì)以開(kāi)頭，所以不會(huì)出現(xiàn)或者的情況。示例輸入輸出解釋累加序列為。

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
描述

累加數(shù)是一個(gè)字符串，組成它的數(shù)字可以形成累加序列。

一個(gè)有效的累加序列必須至少包含 3 個(gè)數(shù)。除了最開(kāi)始的兩個(gè)數(shù)以外，字符串中的其他數(shù)都等于它之前兩個(gè)數(shù)相加的和。

給定一個(gè)只包含數(shù)字 "0"-"9" 的字符串，編寫(xiě)一個(gè)算法來(lái)判斷給定輸入是否是累加數(shù)。

說(shuō)明: 累加序列里的數(shù)不會(huì)以 0 開(kāi)頭，所以不會(huì)出現(xiàn) 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
思路

這道題可以使用深度優(yōu)先搜索進(jìn)行回溯.

我們使用深度優(yōu)先搜索，找到所有可能拆分給定字符串的方式，然后我們判斷當(dāng)前的拆分方式是否能構(gòu)成累加數(shù)，如果可以，我們用res記錄為True，否則為False.

__valid函數(shù)用于判斷當(dāng)前的組合方式是否能構(gòu)成累加數(shù)，注意：累加數(shù)至少需要三個(gè).

# -*- 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":
        # 根據(jù)題意，累計(jì)加數(shù)至少有三個(gè)
        if len(num) < 3: return False
        self.res = False
        # 深度優(yōu)先搜索，遍歷所有可能的解
        self.__dfs(0, num, [])
        return self.res

    def __dfs(self, start, num, coms):
        # 遞歸結(jié)束條件，當(dāng)num中沒(méi)有數(shù)字時(shí)，檢查當(dāng)前組合是否滿足條件
        if start == len(num):
            # 如果當(dāng)前組合合法，我們將self.res置為True
            if self.__valid(coms): self.res = True
            return
        # 記錄起始位置
        index = start
        while index < len(num):
            # 如果當(dāng)前數(shù)字的起始數(shù)字是"0"退出循環(huán)（注意多帶帶一個(gè)"0"本身是合法的）
            if num[start] == "0" and index != start: break
            # 如果當(dāng)前的組合已經(jīng)有了至少3個(gè)數(shù)，我們檢查前面的所有數(shù)是否是累加數(shù)
            # 如果不是我們退出循環(huán)，表示當(dāng)前的分支不用再查找，減少時(shí)間
            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):
        # 如果一共都沒(méi)有三個(gè)數(shù)，返回False
        if len(coms) < 3: return False
        for i in range(len(coms) - 2):
            # 只要有一個(gè)不滿足累加數(shù)的條件，返回False
            if int(coms[i]) + int(coms[i + 1]) != int(coms[i + 2]):
                return False
        return True

源代碼文件在這里.
?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留文章來(lái)源，作者信息和本聲明.

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/43169.html

相關(guān)文章

  • leetcode306. Additive Number

    摘要：為了減少無(wú)效遍歷，我們可以在尋找第一個(gè)數(shù)字和第二個(gè)數(shù)字的時(shí)候及時(shí)終止。我們可以知道第一個(gè)數(shù)字的長(zhǎng)度不應(yīng)該超過(guò)字符串長(zhǎng)度的一般，第二個(gè)數(shù)字的長(zhǎng)度無(wú)法超過(guò)字符串長(zhǎng)度減去第一個(gè)數(shù)字的長(zhǎng)度。因此一旦遇到，在判斷完作為加數(shù)時(shí)是否合法后，直接跳出循環(huán)。 題目要求 Additive number is a string whose digits can form additive sequence....

    2shou 評(píng)論0 收藏0

  • 306. Additive Number

    摘要：題目解答不越界長(zhǎng)度的當(dāng)可以走到后面沒(méi)有和了的時(shí)候，說(shuō)明這個(gè)滿足條件直接可以知道這個(gè)是不是存在于中越界長(zhǎng)度的越界長(zhǎng)的度 題目：Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers...

    dkzwm 評(píng)論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 評(píng)論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 評(píng)論0 收藏0

  • 容器最大盛水量

    摘要：容器最大盛水量給定個(gè)非負(fù)整數(shù)，，，，其中每個(gè)表示坐標(biāo)，處的點(diǎn)。找到兩條線，它們與軸一起形成一個(gè)容器，使得容器含有最多的水。 容器最大盛水量 Container With Most Water 給定n個(gè)非負(fù)整數(shù)a1，a2，...，an，其中每個(gè)表示坐標(biāo)（i，ai）處的點(diǎn)。 繪制n條垂直線，使得線i的兩個(gè)端點(diǎn)在（i，ai）和（i，0）處。 找到兩條線，它們與x軸一起形成一個(gè)容器，使得容器...

    luckyw 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

GeekQiaQia

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<