Рубрики

Минимальные шаги для достижения конца массива при ограничениях

Учитывая массив, содержащий только однозначные числа, предполагая, что мы стоим на первом индексе, нам нужно достичь конца массива, используя минимальное количество шагов, где за один шаг мы можем перейти к соседним индексам или перейти к позиции с тем же значением ,

Другими словами, если мы находимся с индексом i, то за один шаг вы можете достичь, arr [i-1] или arr [i + 1] или arr [K], так что arr [K] = arr [i] ( значение arr [K] совпадает с arr [i])

Примеры:

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)

Эта проблема может быть решена с помощью BFS . Мы можем рассматривать данный массив как невзвешенный граф, где каждая вершина имеет два ребра для следующего и предыдущего элементов массива и больше ребер для элементов массива с одинаковыми значениями. Теперь для быстрой обработки ребер третьего типа мы сохраняем 10 векторов, в которых хранятся все индексы, в которых присутствуют цифры от 0 до 9. В приведенном выше примере вектор, соответствующий 0, будет хранить [0, 12], 2 индекса, где 0 произошло в данном массиве.
Используется другой логический массив, чтобы мы не посещали один и тот же индекс более одного раза. Поскольку мы используем BFS и BFS, выручка от уровня к уровню, оптимальные минимальные шаги гарантированы.

C ++

// C ++ программа для поиска минимальных переходов до конца
// массива
#include <bits/stdc++.h>

using namespace std;

  
// Метод возвращает минимальный шаг для достижения конца массива

int getMinStepToReachEnd(int arr[], int N)

{

    // посещение логического массива проверяет, является ли текущий индекс

    // ранее посещался

    bool visit[N];

  

    // массив расстояний хранит расстояние тока

    // индекс из начального индекса

    int distance[N];

  

    // цифровой вектор хранит индексы, где

    // определенное число проживает

    vector<int> digit[10];

  

    // При запуске все индексы не посещаются

    memset(visit, false, sizeof(visit));

  

    // сохраняем индексы каждого числа в цифре-векторе

    for (int i = 1; i < N; i++)

        digit[arr[i]].push_back(i);

  

    // для начального индекса расстояние будет нулевым

    distance[0] = 0;

    visit[0] = true;

  

    // Создание очереди и вставка индекса 0.

    queue<int> q;

    q.push(0);

  

    // цикл до очереди не пустой

    while(!q.empty())

    {

        // Получить элемент из очереди, q.

        int idx = q.front();        q.pop();

  

        // Если мы дошли до последнего выхода из цикла

        if (idx == N-1)

            break;

  

        // Находим значение снятого индекса

        int d = arr[idx];

  

        // цикл для всех индексов со значением как d.

        for (int i = 0; i<digit[d].size(); i++)

        {

            int nextidx = digit[d][i];

            if (!visit[nextidx])

            {

                visit[nextidx] = true;

                q.push(nextidx);

  

                // обновляем расстояние этого nextidx

                distance[nextidx] = distance[idx] + 1;

            }

        }

  

        // очищаем все индексы для цифры d, потому что все

        // из них обрабатываются

        digit[d].clear();

  

        // проверка условия для предыдущего индекса

        if (idx-1 >= 0 && !visit[idx - 1])

        {

            visit[idx - 1] = true;

            q.push(idx - 1);

            distance[idx - 1] = distance[idx] + 1;

        }

  

        // проверка условия для следующего индекса

        if (idx + 1 < N && !visit[idx + 1])

        {

            visit[idx + 1] = true;

            q.push(idx + 1);

            distance[idx + 1] = distance[idx] + 1;

        }

    }

  

    // N-1 позиция имеет конечный результат

    return distance[N - 1];

}

  
// код драйвера для тестирования вышеуказанных методов

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 программа для поиска минимальных переходов
// достичь конца массива

import java.util.*;

class GFG

{

  
// Метод возвращает минимальный шаг
// достичь конца массива

static int getMinStepToReachEnd(int arr[], 

                                int N)

{

    // посещение логического массива проверяет,

    // текущий индекс посещен ранее

    boolean []visit = new boolean[N];

  

    // массив расстояний хранит расстояние

    // текущий индекс из начального индекса

    int []distance = new int[N];

  

    // цифровой вектор хранит индексы, где

    // определенное число проживает

    Vector<Integer> []digit = new Vector[10];

    for(int i = 0; i < 10; i++)

        digit[i] = new Vector<>();

  

    // При запуске все индексы не посещаются

    for(int i = 0; i < N; i++)

        visit[i] = false;

  

    // сохраняем индексы каждого номера

    // в цифровом векторе

    for (int i = 1; i < N; i++)

        digit[arr[i]].add(i);

  

    // для начального индекса расстояние будет нулевым

    distance[0] = 0;

    visit[0] = true;

  

    // Создание очереди и вставка индекса 0.

    Queue<Integer> q = new LinkedList<>();

    q.add(0);

  

    // цикл до очереди не пустой

    while(!q.isEmpty())

    {

        // Получить элемент из очереди, q.

        int idx = q.peek();     

        q.remove();

  

        // Если мы дошли до последнего

        // разрыв индекса из цикла

        if (idx == N - 1)

            break;

  

        // Находим значение снятого индекса

        int d = arr[idx];

  

        // цикл для всех индексов со значением как 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);

  

                // обновляем расстояние этого nextidx

                distance[nextidx] = distance[idx] + 1;

            }

        }

  

        // очистить все индексы для цифры d,

        // потому что все они обрабатываются

        digit[d].clear();

  

        // проверка условия для предыдущего индекса

        if (idx - 1 >= 0 && !visit[idx - 1])

        {

            visit[idx - 1] = true;

            q.add(idx - 1);

            distance[idx - 1] = distance[idx] + 1;

        }

  

        // проверка условия для следующего индекса

        if (idx + 1 < N && !visit[idx + 1])

        {

            visit[idx + 1] = true;

            q.add(idx + 1);

            distance[idx + 1] = distance[idx] + 1;

        }

    }

  

    // N-1 позиция имеет конечный результат

    return distance[N - 1];

}

  
// Код драйвера

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));

}
}

  
// Этот код предоставлен 29AjayKumar

python3

# Программа Python 3 для поиска минимальных переходов для достижения конца # массива

  
# Метод возвращает минимальный шаг для достижения конца массива

def getMinStepToReachEnd(arr,N):

      

    # посещение логического массива проверяет, является ли текущий индекс

    # посещался ранее

    visit = [False for i in range(N)]

  

    # массив расстояний хранит расстояние тока

    # индекс из начального индекса

    distance = [0 for i in range(N)]

  

    # значный вектор хранит индексы, где

    # конкретное число проживает

    digit = [[0 for i in range(N)] for j in range(10)]

  

    # хранение индексов каждого числа в векторе цифр

    for i in range(1,N):

        digit[arr[i]].append(i)

  

    # для начального индекса расстояние будет равно нулю

    distance[0] = 0

    visit[0] = True

  

    # Создание очереди и вставка индекса 0.

    q = []

    q.append(0)

  

    # цикл до очереди в не пустой

    while(len(q)> 0):

          

        # Получить предмет из очереди, q.

        idx = q[0]

        q.remove(q[0])

  

        # Если мы дошли до последнего разрыва индекса из цикла

        if (idx == N-1):

            break

  

        # Найти значение снятого индекса

        d = arr[idx]

  

        # цикл для всех индексов со значением как d.

        for i in range(len(digit[d])):

            nextidx = digit[d][i]

            if (visit[nextidx] == False):

                visit[nextidx] = True

                q.append(nextidx)

  

                # обновить расстояние этого nextidx

                distance[nextidx] = distance[idx] + 1

  

        # очистить все индексы для цифры d, потому что все

        Количество из них обработано

  

        # проверка условия для предыдущего индекса

        if (idx-1 >= 0 and visit[idx - 1] == False):

            visit[idx - 1] = True

            q.append(idx - 1)

            distance[idx - 1] = distance[idx] + 1

  

        # проверка условия для следующего индекса

        if (idx + 1 < N and visit[idx + 1] == False):

            visit[idx + 1] = True

            q.append(idx + 1)

            distance[idx + 1] = distance[idx] + 1

  

    # N-1-я позиция имеет конечный результат

    return distance[N - 1]

  
# код драйвера для тестирования вышеуказанных методов

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))

      
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # программа для поиска минимальных прыжков
// достичь конца массива

using System;

using System.Collections.Generic;

  

class GFG

{

  
// Метод возвращает минимальный шаг
// достичь конца массива

static int getMinStepToReachEnd(int []arr, 

                                int N)

{

    // посещение логического массива проверяет,

    // текущий индекс посещен ранее

    bool []visit = new bool[N];

  

    // массив расстояний хранит расстояние

    // текущий индекс из начального индекса

    int []distance = new int[N];

  

    // цифровой вектор хранит индексы, где

    // определенное число проживает

    List<int> []digit = new List<int>[10];

    for(int i = 0; i < 10; i++)

        digit[i] = new List<int>();

  

    // При запуске все индексы не посещаются

    for(int i = 0; i < N; i++)

        visit[i] = false;

  

    // сохраняем индексы каждого номера

    // в цифровом векторе

    for (int i = 1; i < N; i++)

        digit[arr[i]].Add(i);

  

    // для начального индекса расстояние будет нулевым

    distance[0] = 0;

    visit[0] = true;

  

    // Создание очереди и вставка индекса 0.

    Queue<int> q = new Queue<int>();

    q.Enqueue(0);

  

    // цикл до очереди не пустой

    while(q.Count != 0)

    {

        // Получить элемент из очереди, q.

        int idx = q.Peek();     

        q.Dequeue();

  

        // Если мы дошли до последнего

        // разрыв индекса из цикла

        if (idx == N - 1)

            break;

  

        // Находим значение снятого индекса

        int d = arr[idx];

  

        // цикл для всех индексов со значением как d.

        for (int i = 0; i < digit[d].Count; i++)

        {

            int nextidx = digit[d][i];

            if (!visit[nextidx])

            {

                visit[nextidx] = true;

                q.Enqueue(nextidx);

  

                // обновляем расстояние этого nextidx

                distance[nextidx] = distance[idx] + 1;

            }

        }

  

        // очистить все индексы для цифры d,

        // потому что все они обрабатываются

        digit[d].Clear();

  

        // проверка условия для предыдущего индекса

        if (idx - 1 >= 0 && !visit[idx - 1])

        {

            visit[idx - 1] = true;

            q.Enqueue(idx - 1);

            distance[idx - 1] = distance[idx] + 1;

        }

  

        // проверка условия для следующего индекса

        if (idx + 1 < N && !visit[idx + 1])

        {

            visit[idx + 1] = true;

            q.Enqueue(idx + 1);

            distance[idx + 1] = distance[idx] + 1;

        }

    }

  

    // N-1 позиция имеет конечный результат

    return distance[N - 1];

}

  
// Код драйвера

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));

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

5

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальные шаги для достижения конца массива при ограничениях

0.00 (0%) 0 votes