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

题目描述

示例

代码如下：

public class SplitIntoFibonacci {

    LinkedList<Integer> res = new LinkedList<>();
    public List<Integer> splitIntoFibonacci(String num) {
        if(num.length() < 3) return res;
        if(dfs(num, 0)) return res;
        return new LinkedList<>();
    }

    public boolean dfs(String num, int start) {
        //边界条件判断，如果截取完了，并且res长度大于等于3，表示找到了一个组合。
        if (start == num.length() && res.size() >= 3) {
            return true;
        }
        for (int i = start; i < num.length(); i++) {
            //两位以上的数字不能以0开头
            if (num.charAt(start) == '0' && i > start) {
                break;
            }
            String s = num.substring(start, i + 1);
            //截取字符串转化为数字
            long cur = Long.valueOf(s);
            //如果截取的数字大于int的最大值，则终止截取
            if (cur > Integer.MAX_VALUE) {
                break;
            }
            int size = res.size();
            //如果截取的数字大于res中前两个数字的和，说明这次截取的太大，直接终止，因为后面越截取越大
            if (size >= 2) {
                if(cur > res.get(size - 1) + res.get(size - 2)){
                    break;
                }
                if(cur < res.get(size - 1) + res.get(size - 2)){
                    continue;
                }
            }
            //把数字cur添加到集合res中
            res.add((int) cur);
            //如果找到了就直接返回
            if (dfs(num, i + 1))
                return true;
            //如果没找到，就会走回溯这一步，然后把上一步添加到集合res中的数字给移除掉
            res.removeLast();
        }
        return false;
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49