第GoJava算法之累加數(shù)示例詳解目錄累加數(shù)方法一：窮舉法（java）方法二：深度優(yōu)先遍歷（go）

累加數(shù)

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

一個有效的累加序列必須至少包含3個數(shù)。除了最開始的兩個數(shù)以外，序列中的每個后續(xù)數(shù)字必須是它之前兩個數(shù)字之和。

給你一個只包含數(shù)字0-9的字符串，編寫一個算法來判斷給定輸入是否是累加數(shù)。如果是，返回true；否則，返回false。

說明：累加序列里的數(shù)，除數(shù)字0之外，不會以0開頭，所以不會出現(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

提示：

1=num.length=35

num僅由數(shù)字（0-9）組成

方法一：窮舉法（java）

一個累加序列，當(dāng)它的第一個數(shù)字和第二個數(shù)字以及總長度確定后，這整個累加序列也就確定了。

根據(jù)這個性質(zhì)，我們可以窮舉累加序列的第一個數(shù)字和第二個數(shù)字的所有可能性，對每個可能性，進(jìn)行一次合法性的判斷。

當(dāng)出現(xiàn)一次合法的累加序列后，即可返回true。

當(dāng)所有可能性都遍歷完仍無法找到一個合法的累加序列時，返回false。

classSolution{

publicbooleanisAdditiveNumber(Stringnum){

intn=num.length();

for(intsecondStart=1;secondStartn-1;++secondStart){

if(num.charAt(0)=='0'secondStart!=1){

break;

for(intsecondEnd=secondStart;secondEndn-1;++secondEnd){

if(num.charAt(secondStart)=='0'secondStart!=secondEnd){

break;

if(valid(secondStart,secondEnd,num)){

returntrue;

returnfalse;

publicbooleanvalid(intsecondStart,intsecondEnd,Stringnum){

intn=num.length();

intfirstStart=0,firstEnd=secondStart-1;

while(secondEnd=n-1){

Stringthird=stringAdd(num,firstStart,firstEnd,secondStart,secondEnd);

intthirdStart=secondEnd+1;

intthirdEnd=secondEnd+third.length();

if(thirdEnd=n||!num.substring(thirdStart,thirdEnd+1).equals(third)){

break;

if(thirdEnd==n-1){

returntrue;

firstStart=secondStart;

firstEnd=secondEnd;

secondStart=thirdStart;

secondEnd=thirdEnd;

returnfalse;

publicStringstringAdd(Strings,intfirstStart,intfirstEnd,intsecondStart,intsecondEnd){

StringBufferthird=newStringBuffer();

intcarry=0,cur=0;

while(firstEnd=firstStart||secondEnd=secondStart||carry!=0){

cur=carry;

if(firstEnd=firstStart){

cur+=s.charAt(firstEnd)-'0';

--firstEnd;

if(secondEnd=secondStart){

cur+=s.charAt(secondEnd)-'0';

--secondEnd;

carry=cur/10;

cur%=10;

third.append((char)(cur+'0'));

third.reverse();

returnthird.toString();

時間復(fù)雜度：o（n^3）

空間復(fù)雜度：o（n）

方法二：深度優(yōu)先遍歷（go）

對字符串num進(jìn)行回溯，回溯過程中截取字符串diff，如果diff的首字符是0，則不進(jìn)行處理，否則判斷前兩個元素相加是否能得到diff

由于num.length的范圍在[1,35]，所以如果用long存儲的話，最終可能會超限，所以這里使用字符串?dāng)?shù)組記錄。

記錄過程中類似于兩數(shù)相加，最后將較長的那個數(shù)組拼在結(jié)果數(shù)組中。對最終數(shù)組進(jìn)行進(jìn)位處理。

funcadd(a,bstring)string{

res,one:=[]byte{},0

fori,j:=len(a)-1,len(b)-1;i=0||j=0;{

curA,curB:=0,0

ifi=0{

curA=int(a[i]-'0')

ifj=0{

curB=int(b[j]-'0')

cur:=curA+curB+one

one=cur/10

res=append(res,byte(cur%10)+'0')

ifone==1{

res=append(res,'1')

fori,n:=0,len(res);in/2;i++{

res[i],res[n-1-i]=res[n-1-i],res[i]

returnstring(res)

funcdfs(numstring,first,secondint)bool{

n,last:=len(num),0

forsecondn{

if(num[last]=='0'firstlast+1)||(num[first]=='0'secondfirst+1){

returnfalse

s:=add(num[last:first],num[first:second])

ifsecond+len(s)n||num[second:second+len(s)]!=s{

returnfalse

last,first,second=first,second,second+len(s)

returntrue

funcisAdditiveNumber(numstring)