Pregunta

Dada una matriz de enteros donde cada elemento representa el número máximo de pasos que se pueden hacer hacia adelante a partir de ese elemento.
Escribir una función para devolver el mínimo número de saltos para llegar a la
final de la matriz (a partir del primer elemento). Si un elemento es
0, entonces no se puede mover a través de ese elemento.

Ejemplo

De entrada: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}

Salida: 3 (1-> 3 -> 8 ->9)

Encontrado múltiples formas de Programación dinámica a otras concepciones lineales. Yo no soy capaz de entender el enfoque de la cual se dice que es lineal en el tiempo. AQUÍ es el enlace donde un enfoque lineal que se propone.

Yo no soy capaz de comprenderlo del todo. Lo que pude entender es que el autor sugiere para hacer un codicioso enfoque y ver si podemos llegar a la final .. si no, a continuación, volver atrás ?

OriginalEl autor Walt | 2015-01-09

4 Comentarios

  1. 13

    El momento en que la complejidad de la solución propuesta en el sitio es lineal debido a que sólo iterar a través de la matriz de una vez. El algoritmo evita el interior de la iteración de mi propuesta de solución mediante el uso de algunos trucos ingeniosos.

    La variable maxReach tiendas en todo momento la máxima alcanzable posición en la matriz. jump almacena la cantidad de saltos necesarios para alcanzar esa posición. step almacena la cantidad de pasos que puede tomar (y se inicializa con la cantidad de pasos en la primera posición del array)

    Durante la iteración, los valores anteriores se actualizan de la siguiente manera:

    Primero comprobamos si hemos llegado al final de la matriz, en cuyo caso sólo tenemos que devolver el jump variable.

    Siguiente actualizamos la máxima alcanzable posición. Esto es igual a la máxima de maxReach y i+A[i] (el número de pasos que podemos tomar desde la posición actual).

    Utilizamos un paso para llegar a la actual índice, por lo que steps tiene que ser disminuido.

    Si no hay más pasos restantes (es decir,steps=0, entonces debemos utilizar un salto. Por lo tanto, aumentar jump. Ya sabemos que es posible de alguna manera para llegar a maxReach, inicializamos los pasos para la cantidad de pasos para llegar a maxReach desde la posición i.

    public class Solution {
        public int jump(int[] A) {
            if (A.length <= 1)
                return 0;
            int maxReach = A[0];
            int step = A[0];
            int jump = 1;
            for (int i = 1; i < A.length; i++) {
               if (i == A.length - 1)
                    return jump;
                if (i + A[i] > maxReach)
                    maxReach = i + A[i];
                step--;
                if (step == 0) {
                    jump++;
                    step = maxReach - i;
                } 
            }
            return jump;
        }
    }

    Ejemplo:

    int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
    int maxReach = A[0];     //A[0]=1, so the maximum index we can reach at the moment is 1.
    int step = A[0];         //A[0] = 1, the amount of steps we can still take is also 1.
    int jump = 1;            //we will always need to take at least one jump.
    /*************************************
    * First iteration (i=1)
    ************************************/
    if (i + A[i] > maxReach) //1+3 > 1, we can reach further now!
    maxReach = 1 + A[i]  //maxReach = 4, we now know that index 4 is the largest index we can reach.
    step--                   //we used a step to get to this index position, so we decrease it
    if (step == 0) {
    ++jump;              //we ran out of steps, this means that we have made a jump
    //this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
    //but we can continue with the 3 steps received at array position 2.
    steps = maxReach-i   //we know that by some combination of 2 jumps, we can reach  position 4.
    //therefore in the current situation, we can minimaly take 3
    //more steps to reach position 4 => step = 3
    }
    /*************************************
    * Second iteration (i=2)
    ************************************/
    if (i + A[i] > maxReach) //2+5 > 4, we can reach further now!
    maxReach = 1 + A[i]  //maxReach = 7, we now know that index 7 is the largest index we can reach.
    step--                   //we used a step so now step = 2
    if (step==0){
    //step 
    }
    /*************************************
    * Second iteration (i=3)
    ************************************/
    if (i + A[i] > maxReach) //3+8 > 7, we can reach further now!
    maxReach = 1 + A[i]  //maxReach = 11, we now know that index 11 is the largest index we can reach.
    step--                   //we used a step so now step = 1
    if (step==0){
    //step 
    }
    /*************************************
    * Third iteration (i=4)
    ************************************/
    if (i + A[i] > maxReach) //4+9 > 11, we can reach further now!
    maxReach = 1 + A[i]  //maxReach = 13, we now know that index 13 is the largest index we can reach.
    step--                   //we used a step so now step = 0
    if (step == 0) {
    ++jump;              //we ran out of steps, this means that we have made a jump.
    //jump is now equal to 3.
    steps = maxReach-i   //there exists a combination of jumps to reach index 13, so
    //we still have a budget of 9 steps
    }
    /************************************
    * remaining iterations
    ***********************************
    //nothing much changes now untill we reach the end of the array.

    Mi subóptima algoritmo que trabaja en O(nk) tiempo con n el número de elementos de la matriz y k el mayor elemento de la matriz, y utiliza un bucle interno de más de array[i]. Este bucle se evita mediante el siguiente algoritmo.

    Código

    public static int minimum_steps(int[] array) {
    int[] min_to_end = new int[array.length];
    for (int i = array.length - 2; i >= 0; --i) {
    if (array[i] <= 0)
    min_to_end[i] = Integer.MAX_VALUE;
    else {
    int minimum = Integer.MAX_VALUE;
    for (int k = 1; k <= array[i]; ++k) {
    if (i + k < array.length)
    minimum = Math.min(min_to_end[i+k], minimum);
    else
    break;
    }
    min_to_end[i] = minimum + 1;
    }
    }
    return min_to_end[0];
    } 
    ¿Por qué es este el tiempo lineal?
    No creo que este es el tiempo lineal. Necesita una solución lineal en el tiempo.
    Disculpas, de hecho no es en tiempo lineal. He editado mi post…
    Vamos. Muchas gracias por tomar su tiempo para responder. No hay razón para pedir disculpas :). Déjeme saber si usted tiene alguna idea sobre el tiempo lineal de la solución. El leet código de enlace que he compartido dice tener el tiempo lineal de la solución. Es sólo que yo no soy capaz de entenderlo. Puede usted por favor, eche un vistazo a lo
    la función jump nunca falla (ejemplo: A[] = {0,1} y A[]={1,3,1,0,0,0,0,1}, en caso de fallar, de acuerdo a la pregunta descripción). en caso de no agregar una condición en el inicio de bucle: if (steps == 0) return INT_MAX;, y un retorno al final de la función (a pesar de que nunca se debe llegar): return INT_MAX; ?, thnx!

    OriginalEl autor Niels Billen

  2. 2

    Años tarde a la fiesta , pero aquí es otra de O(n) solución que tiene sentido para mí.

    ///<summary>
    ///
    ///The actual problem is if it's worth not to jump to the rightmost in order to land on a value that pushes us further than if we jumped on the rightmost.
    ///
    ///However , if we approach the problem from the end,  we go end to start,always jumping to the leftmost
    ///
    ///with this approach , these is no point in not jumping to the leftmost from end to start , because leftmost will always be the index that has the leftmost leftmost :) , so always choosing leftmost is the fastest way to reach start
    ///
    ///</summary>
    ///<param name="arr"></param>
    static void Jumps (int[] arr)
    {
    var LeftMostReacher = new int[arr.Length];
    //let's see , for each element , how far back can it be reached from 
    LeftMostReacher[0] = -1; //the leftmost reacher of 0 is -1
    var unReachableIndex = 1; //this is the first index that hasn't been reached by anyone yet
    //we use this unReachableIndex var so each index's leftmost reacher is  the first that was able to jump to it . Once flagged by the first reacher , new reachers can't be the leftmost anymore so they check starting from unReachableIndex
    //this design insures that the inner loop never flags the same index twice , so the runtime of these two loops together is O(n)
    for (int i = 0; i < arr.Length; i++)
    {
    int maxReach = i + arr[i];
    for (; unReachableIndex <= maxReach && unReachableIndex < arr.Length; unReachableIndex++)
    {
    LeftMostReacher[unReachableIndex] = i;
    }
    }
    //we just go back from the end and then reverse the path
    int index = LeftMostReacher.Length - 1;
    var st = new Stack<int>();
    while (index != -1)
    {
    st.Push(index);
    index = LeftMostReacher[index];
    }
    while (st.Count != 0)
    {
    Console.Write(arr[st.Pop()] + "  ");
    }
    Console.WriteLine();
    }
    static void Main ()
    {
    var nrs = new[] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    Jumps(nrs);
    }

    OriginalEl autor Vasilescu Andrei

  3. 1

    Aquí es otra lineal de la solución. El código es más largo que el indicado en el leet código de enlace, pero creo que es más fácil de entender. Se basa en dos observaciones: el número de pasos necesarios para llegar a la i + 1 posición nunca es menor que el número de pasos necesarios para llegar a la i posición y cada elemento de cada elemento se le asigna su valor de + 1 a i + 1 ... i + a[i] segmento.

    public class Solution {
    public int jump(int[] a) {
    int n = a.length;
    //count[i] is the number of "open" segments with value i
    int[] count = new int[n];
    //the number of steps to reach the i-th position
    int[] dp = new int[n];
    Arrays.fill(dp, n);
    //toDelete[i] is the list of values of segments 
    //that close in the i-th position
    ArrayList<Integer>[] toDelete = new ArrayList[n];
    for (int i = 0; i < n; i++)
    toDelete[i] = new ArrayList<>();
    //Initially, the value is 0(for the first element).
    toDelete[0].add(0);
    int min = 0;
    count[0]++;
    for (int i = 0; i < n; i++) {
    //Finds the new minimum. It uses the fact that it cannot decrease. 
    while (min < n && count[min] == 0)
    min++;
    //If min == n, then there is no path. So we can stop.
    if (min == n)
    break;
    dp[i] = min;
    if (dp[i] + 1 < n) {
    //Creates a new segment from i + 1 to i + a[i] with dp[i] + 1 value
    count[dp[i] + 1]++;
    if (i + a[i] < n)
    toDelete[i + a[i]].add(dp[i] + 1);
    }
    //Processes closing segments in this position.
    for (int deleted : toDelete[i])
    count[deleted]--;
    }
    return dp[n - 1];
    }
    }

    El análisis de la complejidad:

    1. El número total de elementos en toDelete listas es O(n). Es el caso, porque en cada posición i en más de un elemento añadido. Es por eso que el procesamiento de todos los elementos en todos los toDelete listas requiere tiempo lineal.

    2. La min valor sólo puede aumentar. Es por eso que el interior while bucle hace que en la mayoría de los n iteraciones en total.

    3. El exterior for loop, obviamente, hace n iteraciones. Por lo tanto, el tiempo de complejidad es lineal.

    Muchas gracias. Por favor, puedes poner en un poco más de explicación para el código de tiempo y complejidad. Y cuando usted dice que «el número de pasos necesarios para llegar a la i + 1 posición nunca es menor que el número de pasos necesarios para llegar a la i» Que significa que el número de pasos para llegar a i+1 es siempre menor número de pasos para llegar a i a partir de una posición concreta, j .. derecho ?
    Sobre el número de pasos: significa que dp[i] <= dp[i + 1] para todos los i.
    Muchas gracias @ILoveCoding para agregar el análisis de la complejidad. Pero yo no soy capaz de entender el algoritmo todavía. 🙁 Si se puede algunos comentarios, no así. O ¿cómo exactamente es trabajo
    Por un momento, vamos a recordar un ingenuo solución: para cada i, recorrer para j = i + 1 … + a[i]: dp[j] = min(dp[j], dp[i] + 1). Así se crea un segmento [i + 1, i + a[i]] dp[i] + 1 valor. En lugar de la iteración de esta manera, se puede mantener un conjunto de «abrir» los segmentos y sus valores(abierto significa que k + 1 <= i <= k + a[k]).

    OriginalEl autor kraskevich

  4. 0

    Aquí es la intuición básica sobre el problema anterior codicioso de enfoque y el resto de los requerimientos del código.

    Matriz dada es de Entrada: [] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}.

    Ahora empezamos desde el 1er elemento i.e i=0 y (a[i] = 1. Así que viendo esto podemos tomar en más de un salto de tamaño 1, por lo que ya no tenemos ninguna otra opción, así que hacer que este paso se realice.

    Actualmente nos encontramos en i=1 y (a[i]=3. Por lo que actualmente puede hacer un salto de tamaño 3, pero en su lugar hemos de considerar todos los posibles saltos que podemos hacer desde la ubicación actual y alcanzar la máxima distancia a la que está dentro de los límites(de la matriz). Entonces, ¿cuáles son nuestras opciones? podemos hacer un salto de 1 paso, o 2 pasos o 3 pasos. Así que investigar desde la ubicación actual para cada tamaño de saltos y elegir el que nos puede sacar el máximo más en la matriz.

    Una vez que hemos decidido, que nos apegamos, que demos el salto tamaño y la actualización de nuestro número de saltos realizados hasta el momento y también donde podemos llegar en la mayoría de los y cuántos pasos ahora tenemos que decidir nuestro siguiente movimiento. Y eso es todo. Así es como, finalmente, hemos de seleccionar la mejor opción linealmente atravesar la matriz.
    Así que esta es la idea básica de la algo que usted podría estar buscando, el siguiente es el código para el algoritmo para trabajar. Saludos!

    La esperanza de que alguien viajes en el tiempo y se encuentra en la intuición de ayuda !! 🙂 😛
    «Años tarde a la fiesta» @Vasilescu Andrei – bueno, dijo. A veces me parece que somos viajeros en el tiempo.

    OriginalEl autor Sid Ray

Dejar respuesta

Please enter your comment!
Please enter your name here