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[i+1] = F[i+2] 成立。

另外，請注意，將字符串拆分成小塊時，每個塊的數字一定不要以零開頭，除非這個塊是數字 0 本身。

返回從 S 拆分出來的所有斐波那契式的序列塊，如果不能拆分則返回 []。

示例 1： 輸入："123456579" 輸出：[123,456,579]示例 2： 輸入: "11235813" 輸出: [1,1,2,3,5,8,13]示例 3： 輸入: "112358130" 輸出: [] 解釋: 這項任務無法完成。示例 4： 輸入："0123" 輸出：[] 解釋：每個塊的數字不能以零開頭，因此 "01"，"2"，"3" 不是有效答案。示例 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:vector<int> splitIntoFibonacci(string S) {vector<int> ans;if(S.size() < 3)return ans;int i, j;for(i = 0; i < S.size()/2; ++i)for(j = i+1; j < S.size()-1; ++j){ans.clear();if(isok(S,ans,i,j))return ans;}return {};}bool isok(string& S, vector<int>& ans, int i, int j){p = S.substr(0,i+1);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(i+1,j-i);if(q.size()!=1 && q[0]=='0')return false;add(p,q);//字符串數字 加法if(j+sum.size() >= S.size() || sum != S.substr(j+1,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+ (i>=0 ? a[i--]-'0' : 0) + (j>=0 ? b[j--]-'0' : 0);bit = s%10;carry = s/10;sum.insert(0,1,bit+'0');}}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);} };

總結

以上是生活随笔為你收集整理的LeetCode 842. 将数组拆分成斐波那契序列（暴力查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。