计算青蛙到达河对岸所需的最少跳跃次数

Question

我处理下面提供的 Codility 问题，

斐波那契数列使用以下递归公式定义：

F(0) = 0
F(1) = 1
F(M) = F(M - 1) + F(M - 2) if M >= 2

一只小青蛙想要到河的另一边。青蛙最初位于河的一侧（位置 ?1），并想到达另一侧（位置 N）。青蛙可以跳过任何距离 F(K)，其中 F(K) 是第 K 个斐波那契数。幸运的是，河上有很多树叶，青蛙可以在树叶之间跳跃，但只能在位置 N 的河岸方向跳跃。

河上的树叶用由 N 个整数组成的数组 A 表示。数组 A 的连续元素表示从 0 到 N 的连续位置？1 在河上。数组 A 仅包含 0 和/或 1：

0 代表没有叶子的位置；1表示包含叶子的位置。目标是计算青蛙可以到达河对岸（从位置?1 到位置N）的最少跳跃次数。青蛙可以在位置?1 和N（河岸）之间跳跃，每个位置都包含一片叶子。

例如，考虑数组 A 使得：

A[0] = 0
A[1] = 0
A[2] = 0
A[3] = 1
A[4] = 1
A[5] = 0
A[6] = 1
A[7] = 0
A[8] = 0
A[9] = 0
A[10] = 0

青蛙可以跳 3 次，长度为 F(5) = 5、F(3) = 2 和 F(5) = 5。

写一个函数：

class Solution { public int solution(int[] A); }

给定一个由 N 个整数组成的数组 A，返回青蛙可以到达河对岸的最小跳跃次数。如果青蛙不能到达河的另一边，函数应该返回?1。

例如，给定：

A[0] = 0
A[1] = 0
A[2] = 0
A[3] = 1
A[4] = 1
A[5] = 0
A[6] = 1
A[7] = 0
A[8] = 0
A[9] = 0
A[10] = 0

如上所述，该函数应返回 3。

假使，假设：

N 是范围内的整数[0..100,000]；数组 A 的每个元素都是一个整数，可以具有以下值之一：0、1。复杂性：

预期的最坏情况时间复杂度为O(N*log(N))；预期的最坏情况空间复杂度为O(N)（不计算输入参数所需的存储空间）。

我写了以下解决方案，

class Solution {
    private class Jump {
        int position;
        int number;

        public int getPosition() {
            return position;
        }

        public int getNumber() {
            return number;
        }

        public Jump(int pos, int number) {
            this.position = pos;
            this.number = number;
        }
    }

    public int solution(int[] A) {

        int N = A.length;

        List<Integer> fibs = getFibonacciNumbers(N + 1);

        Stack<Jump> jumps = new Stack<>();
        jumps.push(new Jump(-1, 0));

        boolean[] visited = new boolean[N];

        while (!jumps.isEmpty()) {

            Jump jump = jumps.pop();

            int position = jump.getPosition();
            int number = jump.getNumber();

            for (int fib : fibs) {

                if (position + fib > N) {
                    break;
                } else if (position + fib == N) {
                    return number + 1;
                } else if (!visited[position + fib] && A[position + fib] == 1) {

                    visited[position + fib] = true;
                    jumps.add(new Jump(position + fib, number + 1));
                }
            }
        }

        return -1;
    }


    private List<Integer> getFibonacciNumbers(int N) {

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < 2; i++) {
            list.add(i);
        }

        int i = 2;

        while (list.get(list.size() - 1) <= N) {

            list.add(i, (list.get(i - 1) + list.get(i - 2)));
            i++;
        }

        for (i = 0; i < 2; i++) {
            list.remove(i);
        }

        return list;
    }




    public static void main(String[] args) {

    int[] A = new int[11];

    A[0] = 0;
    A[1] = 0;
    A[2] = 0;
    A[3] = 1;
    A[4] = 1;
    A[5] = 0;
    A[6] = 1;
    A[7] = 0;
    A[8] = 0;
    A[9] = 0;
    A[10] = 0;

    System.out.println(solution(A));
   }
}

然而，虽然正确性看起来不错，但性能还不够高。代码中是否存在错误以及如何提高性能？

Answer 1

使用简单的 BFS 获得 100%：

public class Jump {
    int pos;
    int move;
    public Jump(int pos, int move) {
        this.pos = pos;
        this.move = move;
    }
}

public int solution(int[] A) {

    int n = A.length;
    List < Integer > fibs = fibArray(n + 1);
    Queue < Jump > positions = new LinkedList < Jump > ();
    boolean[] visited = new boolean[n + 1];

    if (A.length <= 2)
        return 1;

    for (int i = 0; i < fibs.size(); i++) {
        int initPos = fibs.get(i) - 1;
        if (A[initPos] == 0)
            continue;
        positions.add(new Jump(initPos, 1));
        visited[initPos] = true;
    }

    while (!positions.isEmpty()) {
        Jump jump = positions.remove();
        for (int j = fibs.size() - 1; j >= 0; j--) {
            int nextPos = jump.pos + fibs.get(j);
            if (nextPos == n)
                return jump.move + 1;
            else if (nextPos < n && A[nextPos] == 1 && !visited[nextPos]) {
                positions.add(new Jump(nextPos, jump.move + 1));
                visited[nextPos] = true;
            }
        }
    }


    return -1;
}


private List < Integer > fibArray(int n) {
    List < Integer > fibs = new ArrayList < > ();
    fibs.add(1);
    fibs.add(2);
    while (fibs.get(fibs.size() - 1) + fibs.get(fibs.size() - 2) <= n) {
        fibs.add(fibs.get(fibs.size() - 1) + fibs.get(fibs.size() - 2));
    }
    return fibs;
}