计算青蛙到达河对岸所需的最小跳跃次数
我处理下面提供的一个可编码性问题，
斐波那契序列使用以下递归公式定义：
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的连续元素表示从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
青蛙可以跳三次，长度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..100000]内的整数；数组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));
}
}
然而，正确性看似不错的同时，性能却不够高。代码中是否存在错误，如何提高性能？
共有3个答案
JavaScript 100%
function solution(A) {
function fibonacciUntilNumber(n) {
const fib = [0,1];
while (true) {
let newFib = fib[fib.length - 1] + fib[fib.length - 2];
if (newFib > n) {
break;
}
fib.push(newFib);
}
return fib.slice(2);
}
A.push(1);
const fibSet = fibonacciUntilNumber(A.length);
if (fibSet.includes(A.length)) return 1;
const reachable = Array.from({length: A.length}, () => -1);
fibSet.forEach(jump => {
if (A[jump - 1] === 1) {
reachable[jump - 1] = 1;
}
})
for (let index = 0; index < A.length; index++) {
if (A[index] === 0 || reachable[index] > 0) {
continue;
}
let minValue = 100005;
for (let jump of fibSet) {
let previousIndex = index - jump;
if (previousIndex < 0) {
break;
}
if (reachable[previousIndex] > 0 && minValue > reachable[previousIndex]) {
minValue = reachable[previousIndex];
}
}
if (minValue !== 100005) {
reachable[index] = minValue + 1;
}
}
return reachable[A.length - 1];
}
你可以应用背包算法来解决这个问题。在我的解决方案中，我预先计算了斐波那契数。并应用背包算法进行求解。它包含重复的代码，没有太多的时间来重构它。具有相同代码的联机ide位于repl中
import java.util.*;
class Main {
public static int solution(int[] A) {
int N = A.length;
int inf=1000000;
int[] fibs={1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025};
int[] moves = new int[N+1];
for(int i=0; i<=N; i++){
moves[i]=inf;
}
for(int i=0; i<fibs.length; i++){
if(fibs[i]-1<N && A[fibs[i]-1]==1){
moves[ fibs[i]-1 ] = 1;
}
if(fibs[i]-1==N){
moves[N] = 1;
}
}
for(int i=0; i<N; i++){
if(A[i]==1)
for(int j=0; j<fibs.length; j++){
if(i-fibs[j]>=0 && moves[i-fibs[j]]!=inf && moves[i]>moves[i-fibs[j]]+1){
moves[i]=moves[i-fibs[j]]+1;
}
}
System.out.println(i + " => " + moves[i]);
}
for(int i=N; i<=N; i++){
for(int j=0; j<fibs.length; j++){
if(i-fibs[j]>=0 && moves[i-fibs[j]]!=inf && moves[i]>moves[i-fibs[j]]+1){
moves[i]=moves[i-fibs[j]]+1;
}
}
System.out.println(i + " => " + moves[i]);
}
if(moves[N]==inf) return -1;
return moves[N];
}
public static void main(String[] args) {
int[] A = new int[4];
A[0] = 0;
A[1] = 0;
A[2] = 0;
A[3] = 0;
System.out.println(solution(A));
}
}
通过简单的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;
}
-
问题：到达终点的最小跳跃次数 给定一个整数数组，其中每个元素表示可以从该元素向前执行的最大步数。编写一个函数返回到达数组末尾的最小跳转次数（从第一个元素开始）。如果一个元素是0，那么我们不能移动该元素。 例子： 输入：arr[]={1,3,5,8,9,2,6,7,6,8,9}输出：3（1- 来源：http://www.geeksforgeeks.org/minimum-number-of-jump
-
我一直在尝试解决一个在Codility网页上的Java练习。 下面是提到的练习和我的解决方案的链接。 https://codility.com/demo/results/demoH5GMV3-PV8 有人能告诉我为了提高分数，我的代码中可以纠正什么吗？ 以下是任务描述，以防万一： 一只小青蛙想去河的另一边。青蛙目前位于位置0，想要到达位置X。树叶从树上掉落到河面上。 您将获得一个非空的零索引数组A
-
问题声明：给定数组：[1,0,1,0,1,1,1,1,1,0,1,1,1,0]输出：到达结束所需的最小步骤 条件： 0上的步骤是退出 我已经完成了不使用DP的情况下的使用，是否存在针对此问题的DP解决方案。 我的代码：
-
问题是获取和数组中相应的索引，这些索引导致以较小的跳跃结束。例如：将需要s... 我说的跳跃是指跳跃；i、 e需要多少啤酒花。如果您是一个特定的索引，则可以通过该索引中的值进行跳跃。 下面是我在中的实现，它正确地给出了最小的跳转次数，但是我很难用
-
一只青蛙正试图穿过池塘，但他只能在石头上跳跃，最多能跳五个单位。 我们得到了一个包含1和0（水为0，石头为1）的数组，任务是找到可能的最佳方法，以找到跳跃次数最少的路径（如果可能，使用分治）。 数组示例- 我刚刚开始学习算法，所以如果你们能帮我学习算法和代码就好了。
-
下面是寻找最小跳跃次数的算法谜题。发布了详细的问题声明和两个代码版本来解决这个问题。我做了测试，似乎两个版本都可以工作，我的第二个版本是版本一代码的优化版本，这使得我从开始，而不是持续增加，这可以通过不迭代所有的插槽来节省时间数组。 我的问题是，想知道我的第二个版本代码是否100%正确？如果有人发现任何逻辑问题，请指出。 问题陈述 给定一个非负整数数组，您最初位于数组的第一个索引处。 数组中的每个