Dada una matriz de enteros no negativos, inicialmente se ubica en el primer índice de la matriz. Cada elemento de la matriz representa su longitud máxima de salto en esa posición. Determina si puedes llegar al último índice. Por ejemplo: A = [2,3,1,1,4], devuelve verdadero. A = [3,2,1,0,4], falso retorno.
Análisis
Podemos rastrear el índice máximo que se puede alcanzar. La clave para resolver este problema es encontrar: 1) cuando la posición actual no puede alcanzar la siguiente posición (devolver falso), y 2) cuando el índice máximo puede llegar al final (devolver verdadero).
El índice más grande que se puede alcanzar es: i + A[i].
Aquí hay un ejemplo:
Solución Java
public boolean canJump(int[] A) { if(A.length <= 1) return true; int max = A[0]; //max stands for the largest index that can be reached. for(int i=0; i<A.length; i++){ //if not enough to go to next if(max <= i && A[i] == 0) return false; //update max if(i + A[i] > max){ max = i + A[i]; } //max is enough to reach the end if(max >= A.length-1) return true; } return false; } |
