Считайте минимальное количество прыжков, необходимых для лягушки, чтобы добраться до другой стороны реки ⇐ JAVA

[Anonymous]

Я работаю с проблемой кодировки, представленной ниже, < /p>

Последовательность Fibonacci определяется с использованием следующей рекурсивной формулы: < /p>

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

Небольшая лягушка хочет добраться до другой стороны реки. Лягушка первоначально расположена на одном берегу реки (позиция -1) и хочет добраться до другого берега (позиция n). Лягушка может перепрыгнуть через любое расстояние f (k), где F (k)-номер K-th Fibonacci. К счастью, на реке много листьев, и лягушка может прыгать между листьями, но только в направлении берега в положении n. < /P>

листья на реке представлены в массиве, состоящем из n целых чисел. Последовательные элементы массива представляют последовательные позиции от 0 до N - 1 на реке. Массив A содержит только 0s и /или 1s: < /p>

0 представляет позицию без листа;
1 представляет позицию, содержащую лист.
Цель состоит в том, чтобы подсчитать минимальное количество прыжков, в которых лягушка может добраться до другой стороны реки (от позиции - до положения n). Лягушка может прыгать между позициями -1 и N (берега реки) и каждой позицией, содержащей лист.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
< /code>

лягушка может сделать три прыжка длины f (5) = 5, f (3) = 2 и f (5) = 5. < /p>

Напишите функцию: < /p>

class Solution { public int solution(int[] A); }
< /code>

, что, учитывая массив, состоящий из n целых чисел, возвращает минимальное количество прыжков, с помощью которых лягушка может добраться до другой стороны реки. Если лягушка не может достичь другой стороны реки, функция должна вернуть −1. < /P>

Например, дано: < /p>

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
< /code>

Функция должна вернуть 3, как объяснено выше. < /p>

Предположим, что: < /p>

n целое число в диапазоне [0..100000] < /code>;
Каждый элемент массива - это интуиция, которая может иметь один из следующих значений: 0. /> Сложность: < /p>

Ожидаемая сложность времени наихудшего часа-O (n*log (n)) < /code>;
Ожидаемая сложность пространства наихудшего часа-O (n) < /code> (не подсчитывая хранилище, необходимое для аргументов ввода). < /P>

Я написал следующее решение, < /p>

Я написал следующее решение, < /p>

.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 fibs = getFibonacciNumbers(N + 1);

Stack 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 getFibonacciNumbers(int N) {

List list = new ArrayList();

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

int i = 2;

while (list.get(list.size() - 1)

Однако, хотя правильность кажется хорошей, производительность недостаточно высока. Есть ли ошибка в коде и как мне улучшить производительность?>

Подробнее здесь: https://stackoverflow.com/questions/516 ... her-side-o