题目

给定一个数字字符串 S，比如 S = “123456579”，我们可以将它分成斐波那契式的序列 [123, 456, 579]。

形式上，斐波那契式序列是一个非负整数列表 F，且满足：

  • 0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；

  • F.length >= 3；

  • 对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。

  • 另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。

解题思路

Fibonacci 数列可由直接前2个数字确定，所以从 S 依次取2个数字所形成的 Fibonacci 数列和 S 比较是否一样即可。

code

尝试次数：3
要注意F[i] < 2 ^ 31, 被坑了2次，明明测试用例65可以出结果，但是返回是空，没注意到这坑，还提交多一次以为有bug

  1. class Solution:
  2.     def splitIntoFibonacci(self, S: str) -> List[int]:
  3.         i1,i2= 1,1
  4.         def getFibList(num1, num2):
  5.             numLen = len(str(num1))+len(str(num2))
  6.             f1,f2 = num1,num2
  7.             res = [f1,f2]
  8.             resStr = str(num1)+str(num2)
  9.             while numLen < len(S):
  10.                 f3 = f1+f2
  11.                 f1,f2 = f2,f3
  12.                 # 这里注意有坑
  13.                 if f3 >= pow(2,31):
  14.                     return [],''
  15.                 res.append(f3)
  16.                 numLen += len(str(f3))
  17.                 resStr+=str(f3)
  18.             return res, resStr
  19.         while i1+i2<len(S):
  20.             if i1>1 and S[0] == '0':
  21.                 return []
  22.             f1 = int(S[0:i1])
  23.             if f1 >= pow(2,31):
  24.                 break
  25.             while i1+i2<len(S):
  26.                 if i2>1 and S[i1] == '0':
  27.                     break
  28.                 f2 = int(S[i1:i1+i2])
  29.                 if f2 >= pow(2,31):
  30.                     break
  31.                 if resStr == S:
  32.                     return res
  33.                 i2+=1
  34.             i1 += 1
  35.             i2 = 1
  36.         return []