Dada una array que contiene números de un solo dígito, suponiendo que estamos parados en el primer índice, debemos llegar al final de la array utilizando un número mínimo de pasos donde, en un paso, podemos saltar a los índices vecinos o podemos saltar a una posición con el mismo valor .
En otras palabras, si estamos en el índice i, entonces en un paso puede llegar a arr[i-1] o arr[i+1] o arr[K] tal que arr[K] = arr[i] ( el valor de arr[K] es el mismo que arr[i])
Ejemplos:
Input : arr[] = {5, 4, 2, 5, 0}
Output : 2
Explanation : Total 2 step required.
We start from 5(0), in first step jump to next 5
and in second step we move to value 0 (End of arr[]).
Input : arr[] = [0, 1, 2, 3, 4, 5, 6, 7, 5, 4,
3, 6, 0, 1, 2, 3, 4, 5, 7]
Output : 5
Explanation : Total 5 step required.
0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) ->
(18)
(inside parenthesis indices are shown)
Este problema se puede resolver usando BFS . Podemos considerar la array dada como un gráfico no ponderado donde cada vértice tiene dos bordes para los elementos de array siguientes y anteriores y más bordes para los elementos de array con los mismos valores. Ahora, para un procesamiento rápido del tercer tipo de bordes, mantenemos 10 vectores que almacenan todos los índices donde están presentes los dígitos del 0 al 9. En el ejemplo anterior, el vector correspondiente a 0 almacenará [0, 12], 2 índices donde 0 ha ocurrido en una array dada.
Se utiliza otra array booleana para que no visitemos el mismo índice más de una vez. Como estamos utilizando BFS y los ingresos de BFS nivel por nivel, se garantizan pasos mínimos óptimos.
Implementación:
C++
// C++ program to find minimum jumps to reach end
// of array
#include <bits/stdc++.h>
using namespace std;
// Method returns minimum step to reach end of array
int getMinStepToReachEnd(int arr[], int N)
{
// visit boolean array checks whether current index
// is previously visited
bool visit[N];
// distance array stores distance of current
// index from starting index
int distance[N];
// digit vector stores indices where a
// particular number resides
vector<int> digit[10];
// In starting all index are unvisited
memset(visit, false, sizeof(visit));
// storing indices of each number in digit vector
for (int i = 1; i < N; i++)
digit[arr[i]].push_back(i);
// for starting index distance will be zero
distance[0] = 0;
visit[0] = true;
// Creating a queue and inserting index 0.
queue<int> q;
q.push(0);
// loop until queue in not empty
while(!q.empty())
{
// Get an item from queue, q.
int idx = q.front(); q.pop();
// If we reached to last index break from loop
if (idx == N-1)
break;
// Find value of dequeued index
int d = arr[idx];
// looping for all indices with value as d.
for (int i = 0; i<digit[d].size(); i++)
{
int nextidx = digit[d][i];
if (!visit[nextidx])
{
visit[nextidx] = true;
q.push(nextidx);
// update the distance of this nextidx
distance[nextidx] = distance[idx] + 1;
}
}
// clear all indices for digit d, because all
// of them are processed
digit[d].clear();
// checking condition for previous index
if (idx-1 >= 0 && !visit[idx - 1])
{
visit[idx - 1] = true;
q.push(idx - 1);
distance[idx - 1] = distance[idx] + 1;
}
// checking condition for next index
if (idx + 1 < N && !visit[idx + 1])
{
visit[idx + 1] = true;
q.push(idx + 1);
distance[idx + 1] = distance[idx] + 1;
}
}
// N-1th position has the final result
return distance[N - 1];
}
// driver code to test above methods
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 5,
4, 3, 6, 0, 1, 2, 3, 4, 5, 7};
int N = sizeof(arr) / sizeof(int);
cout << getMinStepToReachEnd(arr, N);
return 0;
}
Java
// Java program to find minimum jumps
// to reach end of array
import java.util.*;
class GFG
{
// Method returns minimum step
// to reach end of array
static int getMinStepToReachEnd(int arr[],
int N)
{
// visit boolean array checks whether
// current index is previously visited
boolean []visit = new boolean[N];
// distance array stores distance of
// current index from starting index
int []distance = new int[N];
// digit vector stores indices where a
// particular number resides
Vector<Integer> []digit = new Vector[10];
for(int i = 0; i < 10; i++)
digit[i] = new Vector<>();
// In starting all index are unvisited
for(int i = 0; i < N; i++)
visit[i] = false;
// storing indices of each number
// in digit vector
for (int i = 1; i < N; i++)
digit[arr[i]].add(i);
// for starting index distance will be zero
distance[0] = 0;
visit[0] = true;
// Creating a queue and inserting index 0.
Queue<Integer> q = new LinkedList<>();
q.add(0);
// loop until queue in not empty
while(!q.isEmpty())
{
// Get an item from queue, q.
int idx = q.peek();
q.remove();
// If we reached to last
// index break from loop
if (idx == N - 1)
break;
// Find value of dequeued index
int d = arr[idx];
// looping for all indices with value as d.
for (int i = 0; i < digit[d].size(); i++)
{
int nextidx = digit[d].get(i);
if (!visit[nextidx])
{
visit[nextidx] = true;
q.add(nextidx);
// update the distance of this nextidx
distance[nextidx] = distance[idx] + 1;
}
}
// clear all indices for digit d,
// because all of them are processed
digit[d].clear();
// checking condition for previous index
if (idx - 1 >= 0 && !visit[idx - 1])
{
visit[idx - 1] = true;
q.add(idx - 1);
distance[idx - 1] = distance[idx] + 1;
}
// checking condition for next index
if (idx + 1 < N && !visit[idx + 1])
{
visit[idx + 1] = true;
q.add(idx + 1);
distance[idx + 1] = distance[idx] + 1;
}
}
// N-1th position has the final result
return distance[N - 1];
}
// Driver Code
public static void main(String []args)
{
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 5,
4, 3, 6, 0, 1, 2, 3, 4, 5, 7};
int N = arr.length;
System.out.println(getMinStepToReachEnd(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to find minimum jumps to reach end# of array # Method returns minimum step to reach end of array def getMinStepToReachEnd(arr,N): # visit boolean array checks whether current index # is previously visited visit = [False for i in range(N)] # distance array stores distance of current # index from starting index distance = [0 for i in range(N)] # digit vector stores indices where a # particular number resides digit = [[0 for i in range(N)] for j in range(10)] # storing indices of each number in digit vector for i in range(1,N): digit[arr[i]].append(i) # for starting index distance will be zero distance[0] = 0 visit[0] = True # Creating a queue and inserting index 0. q = [] q.append(0) # loop until queue in not empty while(len(q)> 0): # Get an item from queue, q. idx = q[0] q.remove(q[0]) # If we reached to last index break from loop if (idx == N-1): break # Find value of dequeued index d = arr[idx] # looping for all indices with value as d. for i in range(len(digit[d])): nextidx = digit[d][i] if (visit[nextidx] == False): visit[nextidx] = True q.append(nextidx) # update the distance of this nextidx distance[nextidx] = distance[idx] + 1 # clear all indices for digit d, because all # of them are processed # checking condition for previous index if (idx-1 >= 0 and visit[idx - 1] == False): visit[idx - 1] = True q.append(idx - 1) distance[idx - 1] = distance[idx] + 1 # checking condition for next index if (idx + 1 < N and visit[idx + 1] == False): visit[idx + 1] = True q.append(idx + 1) distance[idx + 1] = distance[idx] + 1 # N-1th position has the final result return distance[N - 1] # driver code to test above methods if __name__ == '__main__': arr = [0, 1, 2, 3, 4, 5, 6, 7, 5, 4, 3, 6, 0, 1, 2, 3, 4, 5, 7] N = len(arr) print(getMinStepToReachEnd(arr, N)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find minimum jumps
// to reach end of array
using System;
using System.Collections.Generic;
class GFG
{
// Method returns minimum step
// to reach end of array
static int getMinStepToReachEnd(int []arr,
int N)
{
// visit boolean array checks whether
// current index is previously visited
bool []visit = new bool[N];
// distance array stores distance of
// current index from starting index
int []distance = new int[N];
// digit vector stores indices where a
// particular number resides
List<int> []digit = new List<int>[10];
for(int i = 0; i < 10; i++)
digit[i] = new List<int>();
// In starting all index are unvisited
for(int i = 0; i < N; i++)
visit[i] = false;
// storing indices of each number
// in digit vector
for (int i = 1; i < N; i++)
digit[arr[i]].Add(i);
// for starting index distance will be zero
distance[0] = 0;
visit[0] = true;
// Creating a queue and inserting index 0.
Queue<int> q = new Queue<int>();
q.Enqueue(0);
// loop until queue in not empty
while(q.Count != 0)
{
// Get an item from queue, q.
int idx = q.Peek();
q.Dequeue();
// If we reached to last
// index break from loop
if (idx == N - 1)
break;
// Find value of dequeued index
int d = arr[idx];
// looping for all indices with value as d.
for (int i = 0; i < digit[d].Count; i++)
{
int nextidx = digit[d][i];
if (!visit[nextidx])
{
visit[nextidx] = true;
q.Enqueue(nextidx);
// update the distance of this nextidx
distance[nextidx] = distance[idx] + 1;
}
}
// clear all indices for digit d,
// because all of them are processed
digit[d].Clear();
// checking condition for previous index
if (idx - 1 >= 0 && !visit[idx - 1])
{
visit[idx - 1] = true;
q.Enqueue(idx - 1);
distance[idx - 1] = distance[idx] + 1;
}
// checking condition for next index
if (idx + 1 < N && !visit[idx + 1])
{
visit[idx + 1] = true;
q.Enqueue(idx + 1);
distance[idx + 1] = distance[idx] + 1;
}
}
// N-1th position has the final result
return distance[N - 1];
}
// Driver Code
public static void Main(String []args)
{
int []arr = {0, 1, 2, 3, 4, 5, 6, 7, 5,
4, 3, 6, 0, 1, 2, 3, 4, 5, 7};
int N = arr.Length;
Console.WriteLine(getMinStepToReachEnd(arr, N));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find minimum jumps
// to reach end of array
// Method returns minimum step
// to reach end of array
function getMinStepToReachEnd(arr,N)
{
// visit boolean array checks whether
// current index is previously visited
let visit = new Array(N);
// distance array stores distance of
// current index from starting index
let distance = new Array(N);
// digit vector stores indices where a
// particular number resides
let digit = new Array(10);
for(let i = 0; i < 10; i++)
digit[i] = [];
// In starting all index are unvisited
for(let i = 0; i < N; i++)
visit[i] = false;
// storing indices of each number
// in digit vector
for (let i = 1; i < N; i++)
digit[arr[i]].push(i);
// for starting index distance will be zero
distance[0] = 0;
visit[0] = true;
// Creating a queue and inserting index 0.
let q = [];
q.push(0);
// loop until queue in not empty
while(q.length!=0)
{
// Get an item from queue, q.
let idx = q.shift();
// If we reached to last
// index break from loop
if (idx == N - 1)
break;
// Find value of dequeued index
let d = arr[idx];
// looping for all indices with value as d.
for (let i = 0; i < digit[d].length; i++)
{
let nextidx = digit[d][i];
if (!visit[nextidx])
{
visit[nextidx] = true;
q.push(nextidx);
// update the distance of this nextidx
distance[nextidx] = distance[idx] + 1;
}
}
// clear all indices for digit d,
// because all of them are processed
digit[d]=[];
// checking condition for previous index
if (idx - 1 >= 0 && !visit[idx - 1])
{
visit[idx - 1] = true;
q.push(idx - 1);
distance[idx - 1] = distance[idx] + 1;
}
// checking condition for next index
if (idx + 1 < N && !visit[idx + 1])
{
visit[idx + 1] = true;
q.push(idx + 1);
distance[idx + 1] = distance[idx] + 1;
}
}
// N-1th position has the final result
return distance[N - 1];
}
// Driver Code
let arr=[0, 1, 2, 3, 4, 5, 6, 7, 5,
4, 3, 6, 0, 1, 2, 3, 4, 5, 7];
let N = arr.length;
document.write(getMinStepToReachEnd(arr, N));
// This code is contributed by rag2127
</script>
Producción
5
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA