Estoy tratando de escribir un algoritmo eficiente que encuentre la cantidad de saltos que le tomará a un peón salir de una matriz. Digamos que nos dan una matriz, para cada elemento de la matriz si matriz[k] = n entonces matriz[k] es igual a matriz[k + n];
Por ejemplo, tenemos esta matriz [2,3,-1,1,3].
Inicialmente, el peón está en matriz[0], en el primer salto se mueve de matriz[0] a matriz[2] porque 0 + matriz[0] es igual a 2. en el segundo salto, el peón se mueve de A[2] a A[1] porque 2 + A[2] = 1; en el tercer salto, el peón se mueve de A[1] a A[4] porque 1 + A[1] = 4; en el cuarto salto, el peón salta fuera de la matriz. Devuelve 4 para este caso de prueba.
Si el peón no puede saltar fuera de la matriz, devolvemos -1;
A continuación se muestra el algoritmo que escribí para este problema y funciona para algunos casos de prueba pero falla en casos de prueba grandes. ¿Cómo puedo hacer que este algoritmo sea más eficiente?
function jumpOut(A) { let start = 0; let end = A.length - 1 let pawn = 0; while (start < end){ pawn= start + A[start] start++; } if(pawn === end){ return pawn } return -1; }Encontrar el número de movimientos necesarios para salir de la matriz se puede hacer en un tiempo lineal si el peón siempre salta EXACTAMENTE la cantidad especificada en la matriz dada.
Antes de cada salto, puedes comprobar si la posición actual del peón ha sido visitada previamente. En caso afirmativo, eso significa que existe un bucle del que el peón no puede salir, por lo que devuelve -1. De lo contrario, sigue saltando y devuelve la cuenta final.
function getNumRequiredMoves(jumps) { // Remember the positions that have been visited let isVisited = Array(jumps.length).fill(false); // Position of the pawn let position = 0; // Final result let numMoves = 0; while (position >= 0 && position < jumps.length) { if (isVisited[position]) { // This position has been visited before return -1; } // Mark this position as visited isVisited[position] = true; // Jump position += jumps[position]; // Increment the jump counter ++numMoves; } return numMoves; } Ahora, en un momento dado, si el peón puede saltar en cualquier lugar entre [1, jumps[position]] , puede usar la programación dinámica para encontrar de manera eficiente la cantidad de movimientos requeridos.