算法之斐波那契序列

斐波那契数列

斐波那契数列的计算问题。例如：f(0) = 1,f(1) = 1; f(i) = f(i - 1) + f(i - 2);（i >=2）
求：f（n）

  //解法1：简单的递归
public int fib(int n) {
    if (n < 0) return -1;
    else if (n == 1 || n == 0) return 1;

    return fib(n - 1) + f(n - 2);
}

这样解法存在最大的问题是做了太多重复的计算。时间复杂度O(N^2);

例如 fib(n - 1) + f(n - 2)中 fib(n-1) = fib(n-3) + f(n-2);可见f(n - 2)等计算了多次.

解决办法：记忆体,时间复杂度O(N);

Map<Integer, Integer> map;//记忆体
public int fib(int n) {
    //特判
    if (n < 0) return 0;
    map = new HashMap<>();
    map.put(0, 0);
    map.put(1, 1);

    return dfs(n);
}

public int dfs(int n) {
    //记忆搜索。
    if (map.containsKey(n)) {
        return map.get(n);
    }

    int res = dfs(n - 2) + dfs(n - 1);
    map.put(n, res);//存储记忆。
    return res;
}

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

输入："123456579"
输出：[123,456,579]

毫无疑问，递归；只要确定了第一个、第二个数，则第三个数可以确定，以此递推

几个特判条件：

• 多数字时，数字不能以 0 开头；
• 数字不能超出量程；

public List<Integer> splitIntoFibonacci(String S) {
    List<Integer> list = new ArrayList<>();
    backTrack(list, S, S.length(), 0, 0, 0);

    return list;
}

/**
拆分字符串为斐波那契序列
@parameter list：存放拆分后字符串。
@parameter S 需要拆分的字符串
@parameter length 字符串长度
@parameter index 当前拆分位置
@parameter sum 前两数之和
@parameter prev 前一个数
@return true:能够拆分为斐波那契序列
        false:不能拆分
*/
public boolean backTrack(List<Integer> list, String S, int length, int index, int sum, int prev) {
    //特判
    if (index == length) {
        return list.size() > 2;
    }

    long curr = 0;
    for (int i = index; i < length; i++) {
        //以0开始(如"01", 但单独的0可以！)
        if (i > index && s.charAt(i) == '0') {
            break;
        }

        curr = curr*10 + (s.charAt(i) - '0');

        //curr超出量程
        if (curr > Integer.MAX_VALUE) {
            break;
        }

        int temp = (int) curr;

        //不为第一、二个数。
        if (list.size() >= 2) {
            if (temp > sum) {//前两个值相加无法构成当前值。
                break;
            } else if (temp < sum) {//curr 小于前两数相加，curr继续增大。
                continue;
            }
        }

        list.add(temp);//匹配成功，或者前两个数；

        if (backTrack(list, S, length, i, pre + temp, temp)) {//后续能够形成斐波那契序列
            return true;
        } else {
            //回溯,本质是修改第一个、第二个数；
            list.remove(list.size() - 1);
            //return false;不能return false；否则无法修改第一、二个数；
        }
    }

    return false;
}

最长的斐波那契子序列的长度

解法1：暴力遍历

穷举第一、二个数，遍历后续是否有后续。时间复杂度O(N^3)

public int lenLongestFibSubseq(int[] arr) {
        int len = arr.length;
        int max = 2;

    //穷举第一、二个数
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {

                int tempLen = 2;//记录单次最大值
                int pre = arr[i], late = arr[j];
                int sum = pre + late;

                //循环后续的数。
                for (int k = j + 1; k < len; j++) {
                    if (arr[k] == sum) {
                        pre = late; 
                        late = sum;
                        sum = pre + late;
                        tempLen++;
                    } else if (arr[k] > sum) {
                        break;
                    }
                }
                //更新最大长度。
                max = Math.max(tempLen, max);
            }
        }

        return max >= 3 ? max : 0;
    }

解法2：Hash加速第三层循环。

第三层循环是为查找arr中是否存在sum，使用hash代替。时间复杂度O(N^2*logM)，M为arr中最大值

public int lenLongestFibSubseq(int[] arr) {
        int len = arr.length;
        int max = 2;

        //set判断是否存在其和。
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i : arr) {
            set.add(i);
        }

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {

                int tempLen = 2;//记录单次最大值
                int pre = arr[i], late = arr[j];
                int sum = pre + late;

                //hash查找。
                while(set.contains(sum)) {
                    tempLen++;
                    pre = late;
                    late = sum;
                    sum = pre + late;
                }
                //更新最大长度。
                max = Math.max(tempLen, max);
            }
        }

        return max >= 3 ? max : 0;
    }

可以看到，虽然hash查找使得速度变快，但依然存在大量的重复计算

例如：[1,2,3,4,5,6,7,8] 中计算了1，2 -> 3 -> 5;也计算了直接的3 + 5

解法3：在解法2基础上将中间结果存储起来(map)，便于后续查询

时间复杂度O(N^2);

public int lenLongestFibSubseq(int[] A) {
    int N = A.length;
    Map<Integer, Integer> index = new HashMap();
    for (int i = 0; i < N; ++i)
        index.put(A[i], i);

    //用于存储中间结果，用于后续查询。
    Map<Integer, Integer> longest = new HashMap();
    int ans = 0;

    for (int k = 0; k < N; ++k)
        for (int j = 0; j < k; ++j) {
            int i = index.getOrDefault(A[k] - A[j], -1);
            if (i >= 0 && i < j) {

                int cand = longest.getOrDefault(i * N + j, 2) + 1;
                longest.put(j * N + k, cand);
                ans = Math.max(ans, cand);
            }
        }

    return ans >= 3 ? ans : 0;
}