給定一個數字字符串 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 中只含有數字。

回溯+剪枝

使用列表存儲拆分出的數，回溯過程中維護該列表的元素，列表初始為空。遍歷字符串的所有可能的前綴，作為當前被拆分出的數，然后對剩余部分繼續拆分，直到整個字符串拆分完畢。

根據斐波那契式序列的要求，從第 $3$ 個數開始，每個數都等于前 $2$ 個數的和，因此從第 $3$ 個數開始，需要判斷拆分出的數是否等于前 $2$ 個數的和，只有滿足要求時才進行拆分，否則不進行拆分。

回溯過程中，還有三處可以進行剪枝操作。

• 拆分出的數如果不是 $0$，則不能以 $0$ 開頭，因此如果字符串剩下的部分以 $0$ 開頭，就不需要考慮拆分出長度大于 $1$ 的數，因為長度大于 $1$ 的數以 $0$ 開頭是不符合要求的，不可能繼續拆分得到斐波那契式序列；

• 拆分出的數必須符合 $32$ 位有符號整數類型，即每個數必須在 [0,231?1][0,2^{31}-1][0,231?1] 的范圍內，如果拆分出的數大于 231?12^{31}-1231?1，則不符合要求，長度更大的數的數值也一定更大，一定也大于 231?12^{31}-1231?1，因此不可能繼續拆分得到斐波那契式序列；

• 如果列表中至少有 $2$ 個數，并且拆分出的數已經大于最后 $2$ 個數的和，就不需要繼續嘗試拆分了。

當整個字符串拆分完畢時，如果列表中至少有 $3$ 個數，則得到一個符合要求的斐波那契式序列，返回列表。如果沒有找到符合要求的斐波那契式序列，則返回空列表。

Python

class Solution:def splitIntoFibonacci(self, S: str) -> List[int]:def backtrack(index: int):if index == len(S):return len(ans) >= 3curr = 0for i in range(index, len(S)):if i > index and S[index] == "0":breakcurr = curr * 10 + ord(S[i]) - ord("0")if curr > 2 ** 31 - 1:breakif len(ans) < 2 or curr == ans[-2] + ans[-1]:ans.append(curr)if backtrack(i + 1):return Trueans.pop()elif len(ans) > 2 and curr > ans[-2] + ans[-1]:breakreturn Falseans = list()backtrack(0)return ans

復雜度分析

• 時間復雜度：O(nlog?2C)O(n \log^2 C)O(nlog2C)，其中 $n$ 是字符串的長度，$C$ 是題目規定的整數范圍 231?12^{31}-1231?1。在回溯的過程中，實際上真正進行「回溯」的只有前 $2$ 個數，而從第 $3$ 個數開始，整個斐波那契數列是可以被唯一確定的，整個回溯過程只起到驗證（而不是枚舉）的作用。對于前 $2$ 個數，它們的位數不能超過 ?log?10C?\lfloor \log_{10} C \rfloor?log10?C?，那么枚舉的空間為 O(log?2C)O(\log^2 C)O(log2C)；對于后面的所有數，回溯的過程是沒有「分支」的，因此時間復雜度為 $O(n)$，相乘即可得到總時間復雜度 O(nlog?2C)O(n \log^2 C)O(nlog2C)。

• 空間復雜度：$O(n)$，其中 $n$ 是字符串的長度。除了返回值以外，空間復雜度主要取決于回溯過程中的遞歸調用層數，最大為 $n$。

總結

以上是生活随笔為你收集整理的《每日一题》842. Split Array into Fibonacci Sequence 将数组拆分成斐波那契序列的全部內容，希望文章能夠幫你解決所遇到的問題。

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