題目

累加數(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

進(jìn)階:你如何處理一個(gè)溢出的過(guò)大的整數(shù)輸入?

解題思路分析

1、回溯；時(shí)間復(fù)雜度O(n(log(n))^2)，空間復(fù)雜度O(n)

var res []intfunc isAdditiveNumber(num string) bool {if len(num) < 3 {return false}res = make([]int, 0)dfs(num, 0, 0, 0, make([]int, 0))return len(res) >= 3}func dfs(s string, index, sum, prev int, path []int) bool {if index == len(s) {if len(path) >= 3 {res = path}return len(path) >= 3}value := 0for i := index; i < len(s); i++ {// 0開(kāi)頭不滿足要求(當(dāng)前i=index的時(shí)候，可以為0， 避免錯(cuò)過(guò)1+0=1的情況)if s[index] == '0' && i > index {break}value = value*10 + int(s[i]-'0')if len(path) >= 2 {if value < sum {continue}if value > sum {break}}if dfs(s, i+1, prev+value, value, append(path, value)) == true {return true}}return false}

總結(jié)

Medium題目，回溯問(wèn)題，題目類(lèi)似leetcode 842.將數(shù)組拆分成斐波那契序列

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的编写一个函数实现从 1 到 n 共 n 个数的累加_leetcode306_go_累加数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。