Estoy resolviendo este problema , una parte del problema que me está dando problemas se formula de la siguiente manera:
una. Empezar desde el índice i=0;
b. Saltar al índice i=A[i];
C. Si el índice actual i está fuera del límite válido de [0..N-1], imprima "Fuera" y deténgase;
d. De lo contrario, si el índice actual i es el índice N-1, imprima "Listo" y deténgase;
e1. De lo contrario, repita el paso b;
e2. Si hacer esto conduce a un bucle infinito, imprima "Cíclico" y deténgase;
(todas las salidas son sin las comillas)
arr es una matriz de enteros no negativos:
let index = 0; const seen = new Set([0]); while (true) { index = arr[index]; if (index > arr.length - 1) { console.log("Out"); break; } if (index === arr.length - 1) { console.log("Done"); break; } if (seen.has(index)) { console.log("Cyclic"); break; } seen.add(index); }Recibo WA (respuesta incorrecta) en algunos casos de prueba ocultos, pero no puedo por mi vida encontrar un caso de prueba fallido.
1 2 3 4 5 0 -> Done1 2 3 4 6 0 -> Out1 0 0 -> CyclicEditar:
Mi solución C ++ tiene exactamente los mismos casos de prueba fallidos, realmente debe ser algo con mi lógica ...
Creo que el problema es que el algoritmo codificado no cumple con el requisito. Específicamente, e1 indica que se repita el paso b , que obtiene el siguiente valor, y **if doing this** leads to an infinite loop then print "Cycle" . El problema es que el código realmente lo está haciendo, en lugar de verificar primero...
Entonces, mientras se escribe el código actual, un caso de prueba de...
12344
...devolverá "Terminado" en lugar de "Cíclico"...
EDITAR En el código de lenguaje, esto es lo que sugiero (no probado)...
let index = 0; const seen = new Set([0]); while (true) { index = arr[index]; if (index > arr.length - 1) { console.log("Out"); break; } if (index === arr.length - 1) { console.log("Done"); break; } if (seen.has(index) || seen.has(arr[index])) { console.log("Cyclic"); break; } seen.add(index); }EDICIÓN n.º 2 Al tener la oportunidad de probar mi código no probado anteriormente justo arriba, descubrí que no captaba el matiz de mi punto. Entonces, en un esfuerzo por aclarar aún más, a continuación se encuentran los algoritmos actuales y propuestos, con casos de muestra para mostrar las similitudes y las diferencias.
El último caso, donde la entrada cíclica es la entrada final, es donde el paso e2 informa "Cíclico" antes de que el paso c pueda informar "Terminado"...
Los comentarios en la función proposed() muestran los pasos del algoritmo...
function current( arr ) { let index = 0; const seen = new Set([0]); while (true) { index = arr[index]; if (index > arr.length - 1) { console.log("Out"); break; } if (index === arr.length - 1) { console.log("Done"); break; } if (seen.has(index)) { console.log("Cyclic"); break; } seen.add(index); } } function proposed( arr ) { // a. Start from index i=0; let index = 0; // b. Jump to index i=A[i]; const seen = new Set( [ index ] ); index = arr[ index ]; while( true ) { // c. If the current index i is outside the valid bound of [0..N-1], print “Out” and stop; if ( index > arr.length - 1 ) { console.log( "Out" ); break; } // d. Else if the current index i is index N-1, print “Done” and stop; if ( index === arr.length - 1 ) { console.log( "Done" ); break; } // e1. Otherwise, repeat step b; seen.add( index ); index = arr[ index ]; // e2. If doing this leads to an infinite loop, print “Cyclic” and stop; if ( seen.has( arr[index] ) ) { console.log("Cyclic"); break; } } } arr = [1,0,2]; console.log( arr ); current( arr ); proposed( arr ); arr = [1,2,3,4,5]; console.log( arr ); current( arr ); proposed( arr ); arr = [1,2,3,6,5]; console.log( arr ); current( arr ); proposed( arr ); arr=[1,2,3,4,0]; console.log( arr ); current( arr ); proposed( arr );