文章目錄

• 1 題目理解
• 2 回溯

1 題目理解

輸入：一個數字字符串S。例如S=“123456579”。
規則：我們可以把這個字符串分割為菲波那切數列，例如：[123, 456, 579]。
一個菲波那切數列需要符合以下條件：
1 $0<=F[i]<=2^{3}1?1$,也就是正整數
2 F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.
3 在切割過程中每一塊不能有前導0，例如"01"這樣是錯誤的。但可以是"0"和"1"。
輸出：分割后的菲波那切數列。如果不能分割返回空列表。

Example 1:
Input: “123456579”
Output: [123,456,579]

2 回溯

例如S=“123456579”
我們在處理’1’的時候，可以分割為1,12,123,1234… ，123456579
在處理’2’的時候，可以分割為2，23，234，…,23456579
在處理’3’的時候，可以分割為3，34，…,3456579,但是分割后能不能用，需要判斷是不是符合F[i-1] + F[i-2] = F[i]。符合的話可以繼續處理，否則就返回。

…
一直處理到最后，如果列表長度大于等于3，則說明分解成功。

class Solution {private String s;public List<Integer> splitIntoFibonacci(String S) {this.s = S;List<Integer> result = new ArrayList<Integer>();boolean r = dfs(0,result);return r ? result : new ArrayList<Integer>();}private boolean dfs(int start,List<Integer> list){if(start == s.length() && list.size()>2) return true;for(int i=start;i<s.length();i++){if(s.charAt(start)=='0' && i>start) break;String str = s.substring(start,i+1);if(Long.parseLong(str) > Integer.MAX_VALUE) break;int n = Integer.parseInt(str);if(list.size()>1){if(n==list.get(list.size()-1)+list.get(list.size()-2)){list.add(n);if(dfs(i+1,list)) return true;list.remove(list.size()-1);}}else{list.add(n);if(dfs(i+1,list)) return true;list.remove(list.size()-1);}}return false;} }

需要注意：字符串中可能包含0；F[i]的取值范圍是正整數。我第一次刷題是在5月12日，犯了這兩個錯誤。第二次刷題是在12月24日，依然犯了這兩個錯誤。說明在這期間，我看題目的思維沒有升級。關心了輸入、輸出、規則，不太在意，題目中特別說明的地方，以及每個題目在例子后面還有的說明部分。

時間復雜度：對于官方解釋的我不大能明白。但有些部分可以接受。n是字符串長度。
回溯枚舉過程其實枚舉的是前兩個數字。當前兩個數字確定之后，后面的數字都確定了。回溯的過程只是一個確認的過程，時間復雜度O(n)。
枚舉前兩個，最壞情況下，第一個有n種枚舉，第二個有n-1種枚舉。所以是$O(n?(n?1))$，也就是$O(n^2)$。
所以最終，最壞時間復雜度$O(n^3)$。

總結

以上是生活随笔為你收集整理的842. Split Array into Fibonacci Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

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