Biorąc pod uwagę tablicę zawierającą liczby jednocyfrowe, zakładając, że znajdujemy się na pierwszym indeksie, musimy dotrzeć do końca tablicy przy użyciu minimalnej liczby kroków, gdzie w jednym kroku możemy przeskoczyć do sąsiednich indeksów lub przeskoczyć do pozycji o tej samej wartości.
Innymi słowy, jeśli jesteśmy w indeksie i, to w jednym kroku możesz dotrzeć do arr[i-1] lub arr[i+1] lub arr[K] tak, że arr[K] = arr[i] (wartość arr[K] jest taka sama jak arr[i])
znak do ciągu Java
Przykłady:
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) Problem ten można rozwiązać za pomocą BFS . Możemy uznać daną tablicę za graf nieważony, w którym każdy wierzchołek ma dwie krawędzie prowadzące do następnego i poprzedniego elementu tablicy oraz więcej krawędzi do elementów tablicy o tych samych wartościach. Teraz do szybkiego przetwarzania trzeciego rodzaju krawędzi zachowujemy 10 wektory które przechowują wszystkie indeksy, w których obecne są cyfry od 0 do 9. W powyższym przykładzie wektor odpowiadający 0 będzie przechowywać [0 12] 2 indeksy, w których w danej tablicy wystąpiło 0.
Używana jest inna tablica Boolean, abyśmy nie odwiedzali tego samego indeksu więcej niż raz. Ponieważ korzystamy z BFS i BFS osiąga poziom po poziomie, gwarantujemy optymalne minimalne kroki.
Realizacja:
C++// C++ program to find minimum jumps to reach end // of array #include
// 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
# Python 3 program to find minimum jumps to reach end# of array # Method returns minimum step to reach end of array def getMinStepToReachEnd(arrN): # 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(1N): 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# 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
<script> // Javascript program to find minimum jumps // to reach end of array // Method returns minimum step // to reach end of array function getMinStepToReachEnd(arrN) { // 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>
Wyjście
5
Złożoność czasowa: O(N) gdzie N jest liczbą elementów tablicy.
Złożoność przestrzeni: O(N) gdzie N jest liczbą elementów tablicy. Używamy tablicy odległości i odwiedzin o rozmiarze N oraz kolejki o rozmiarze N do przechowywania indeksów tablicy.