网站开发语言有什么要求,湖州市网站建设,网站建设源代码交付,住房建设厅的网站首页1. 题目
给定一个数字字符串 S#xff0c;比如 S “123456579”#xff0c;我们可以将它分成斐波那契式的序列 [123, 456, 579]。
形式上#xff0c;斐波那契式序列是一个非负整数列表 F#xff0c;且满足#xff1a;
0 F[i] 2^31 - 1#xff0c;#xff…1. 题目
给定一个数字字符串 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]示例 2
输入: 11235813
输出: [1,1,2,3,5,8,13]示例 3
输入: 112358130
输出: []
解释: 这项任务无法完成。示例 4
输入0123
输出[]
解释每个块的数字不能以零开头因此 0123 不是有效答案。示例 5
输入: 1101111
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受提示
1 S.length 200
字符串 S 中只含有数字。来源力扣LeetCode 链接https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
类似题目LeetCode 306. 累加数暴力回溯
class Solution {string p, q, sum;
public:vectorint splitIntoFibonacci(string S) {vectorint ans;if(S.size() 3)return ans;int i, j;for(i 0; i S.size()/2; i)for(j i1; j S.size()-1; j){ans.clear();if(isok(S,ans,i,j))return ans;}return {};}bool isok(string S, vectorint ans, int i, int j){p S.substr(0,i1);q sum ;if(p.size()!1 p[0]0)return false;bool flag true;ans.push_back(toNum(p,flag));if(!flag)//超过int范围return false;while(j S.size()){sum ;q S.substr(i1,j-i);if(q.size()!1 q[0]0)return false;add(p,q);//字符串数字 加法if(jsum.size() S.size() || sum ! S.substr(j1,sum.size()))return false;p q;i j;j sum.size();ans.push_back(toNum(p,flag));if(!flag)return false;if(j S.size()-1){ans.push_back(toNum(sum,flag));if(!flag)return false;break;}}return true;}void add(string a, string b){int i a.size()-1, j b.size()-1, carry 0, bit, s;while(i 0 || j 0 || carry){s carry (i0 ? a[i--]-0 : 0) (j0 ? b[j--]-0 : 0);bit s%10;carry s/10;sum.insert(0,1,bit0);}}int toNum(string s, bool flag){long n 0;for(int i 0; i s.size(); i){n n*10(s[i]-0);if(n INT_MAX){ flag false;return -1;}}return int(n);}
};
