企业网站源码进一品资源网,辽宁建设工程信息网、,建设银行网站连不上,九一果冻制品厂最新电视给定一个数字字符串 S#xff0c;比如 S “123456579”#xff0c;我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上#xff0c;斐波那契式序列是一个非负整数列表 F#xff0c;且满足#xff1a;
0 F[i] 2^31 - 1#xff0c;#xff08;也就是…给定一个数字字符串 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[i1] F[i2] 成立。 另外请注意将字符串拆分成小块时每个块的数字一定不要以零开头除非这个块是数字 0 本身。
返回从 S 拆分出来的任意一组斐波那契式的序列块如果不能拆分则返回 []。
示例 1
输入“123456579” 输出[123,456,579]
代码
class Solution {public ListInteger splitIntoFibonacci(String S) {split(S,0,new ArrayList());return totalnull?new ArrayList():total;}ArrayListInteger total;boolean flagfalse;public void split(String S,int pos,ListInteger list) {if(flag) return;//已经找到了if(list.size()2posS.length())//遍历完了{flagtrue;totalnew ArrayList(list);return;}for(int len1;lenposS.length()len11;len){String subS.substring(pos,poslen);if(len1sub.charAt(0)0) break;//第一位是0long tempLong.parseLong(sub);if(tempInteger.MAX_VALUE) break;//已经溢出了if(list.size()2||list.get(list.size()-1)list.get(list.size()-2)temp)//满足条件{list.add((int)temp);split(S,poslen,list);list.remove(list.size()-1);//回溯}}}
}
