java - 计算 Frog 到达河对岸所需的最少跳跃次数

Question

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

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

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

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

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

0表示没有叶子的位置；1 表示包含叶子的位置。目标是计算 Frog 到达河对岸(从位置 -1 到位置 N)的最少跳跃次数。 Frog 可以在位置 −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

Frog 可以跳 3 次，长度分别为 F(5) = 5、F(3) = 2 和 F(5) = 5。

写一个函数:

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

给定一个由 N 个整数组成的数组 A，返回 Frog 到达河对岸所需的最小跳跃次数。如果 Frog 不能到达河的另一边，函数应该返回-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;
}