算法-Split Array into Fibonacci Sequence-数组拆分斐波那契数列

将数组拆分成斐波那契序列

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] 也同样被接受。

2、题目分析

通过回溯实现将给定的字符串拆分成斐波那契数列。回溯的过程就是穷举+剪枝+往上回溯/不满足条件就回到之前的状态，有一定的模板方法。

res = [];

backtrack(路径，选择列表){
    if(满足条件){
        res.add(路径)；
        return；
    }
    for(选择 ： 选择列表){
        做选择；
        backtrack(路径，选择列表)；
        撤销该选择；
}

​ 针对本题，需要遍历出字符串可能的前缀，作为当前被拆分出去的数，然后继续拆分判断。

​ 斐波那契数列，前两个数随意，第三个数要等于前两个数之和，写一个判断函数。

    private boolean isFibonacci(Integer num,List<Integer> res){
        if(res.size() < 2) return true;//少于两个元素的时候，可以直接加入
        return res.get(res.size() - 2) + res.get(res.size() - 1) == num;
    }

​ 回溯的终止条件很好判断，遍历到最后一个字符且结果的大小大于等于3的时候（也就是形成斐波那契数列时）

​ 剪枝的条件有三个：

• 1、拆分出的数必须符合 3232 位有符号整数类型，即每个数必须在[0,2^31 - 1] 的范围内

• 2、可以是0，但是不能是以0开头的非0数

• 3、当前拆分出的数大于前两个之和，也就没必要继续拆分了

  针对本题的回溯代码，应该带有返回值来判断是不是符合要求的斐波那契数列。

3、代码实现

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> res = new ArrayList<>();
        recur(S,0,res);
        return res;
    }
    private boolean recur(String S,int start,List<Integer> res){
        //终止条件
        if(start == S.length() && res.size() > 2)
            return true;
        //剪枝+递归+回溯
        for(int i = start;i < S.length();i++){
            String s1 = S.substring(start,i + 1);
            if(Long.parseLong(s1) > Integer.MAX_VALUE) break;
            if(!s1.equals("0") && s1.charAt(0) == '0') break;
            if(res.size() > 1 && res.get(res.size() - 2) + res.get(res.size() - 1)									 < Integer.valueOf(s1))  break;
            if(isFibonacci(Integer.valueOf(s1),res)){
                res.add(Integer.valueOf(s1));
                if(recur(S,i + 1,res)) return true;
                res.remove(res.size() - 1);
            }
        }
        return false;
    }
    private boolean isFibonacci(Integer num,List<Integer> res){
        if(res.size() < 2) return true;//少于两个元素的时候，可以直接加入
        return res.get(res.size() - 2) + res.get(res.size() - 1) == num;
    }
}

4、复杂度分析

• 时间复杂度：O(nlog^2 C，其中 n 是字符串的长度，C是题目规定的整数范围
• 空间复杂度：O(n)，其中 n 是字符串的长度。除了返回值以外，空间复杂度主要取决于回溯过程中的递归调用层数，最大为 n。