Мінімальная колькасць скачкоў для дасягнення канца  


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка Housing.com Лабараторыі Moonfrog Morgan Stanley Нумары OYO Лабараторыі SAP Лабараторыі Walmart
Дынамічнае праграмаванне Матэматыка

Пастаноўка праблемы  

Дапусцім, у вас ёсць масіў цэлых лікаў і кожны элемент масіў паказвае кожнае лік як максімальны скачок, які можна зрабіць з гэтай кропкі. Ваша задача - высветліць мінімальную колькасць скачкоў, каб дасягнуць канца, гэта значыць мінімум скачкоў, якія можна зрабіць, каб дасягнуць канца.

Прыклад  

arr[] = {2,4,7,11,5,7,3,5}
2

Тлумачэнне: Калі мы наступім на 2, гэта зробіць два крокі і дасягне 7, гэта 1 скачок, а з 7 у нас ёсць 5 крокаў, і мы будзем у канцы з 2 скачкамі ў якасці адказу.

2 → 7 → 5

arr[] = {1,3,2,1,3,5,1,7}
3

Тлумачэнне: 3 скачкамі мы можам дасягнуць канца 1 → 3 → 3. Тут мінімальная колькасць скачкоў, каб дасягнуць канца, роўная 3.

Алгарытм мінімальнай колькасці скачкоў, каб дасягнуць канца  

1. Check if the first element of the array is equal to 0 if true then return -1.
2. Set the maxValue and stepTaken to the first element of the given array.
3. Set jumpTaken to 1.
4. Traverse the array from i=1 to i<n(length of the array).
  1. If the last element of the array reached, return jumpTaken.
  2. Find out the maximum value between the maxValue and arr[i] + i and store it to maxValue.
  3. Decrease the value of stepTaken by 1.
  4. If stepTaken is equal to 0.
    1. Increase jumpTaken by 1.
    2. Check if i is greater than maxValue
      Return -1.
  5. Set stepTaken to maxValue-i.
5. Return -1.

Тлумачэнне

Мы прывялі цэлалікавы масіў. Тут кожны нумар масіва ўяўляе максімальныя крокі, якія можна зрабіць. Няма неабходнасці рабіць менавіта тую колькасць крокаў, якую ўяўляе кожная лічба. Гэта азначае сказаць, што, дапусцім, 6 даецца, тады трэба зрабіць 6 крокаў, але калі за 5 крокаў мы падыдзем да канца, то гэта лепш. Мы проста павінны знайсці мінімальную колькасць скачкоў, якая дапаможа нам дабрацца да канца масіва.

Глядзіце таксама
Друк продкаў дадзенага вузла двайковага дрэва без рэкурсіі

Мы збіраемся ўсталяваць stepTaken і maxValue як першы элемент масіва. Потым мы ўсталюем jumpTaken як 1, бо мы павінны вярнуць 1, калі ў масіве прысутнічае значэнне. Існуе таксама ўмова, дадзеная першаму элементу як 0. Гэта азначае, што нам няма чаго ісці наперад, таму мы вернем толькі -1. Тады мы пройдзем масіў да даўжыні масіва. Мы будзем працягваць аперацыі, пакуль не будзе дасягнута апошняе значэнне масіва, і вернем jumpTaken.

Мы знойдзем максімальнае значэнне паміж maxValue і сума i і arr [i], і паменшыць значэнне stepTaken на 1. Па меры таго, як мы працягваем памяншаць значэнне, пакуль не знойдзем значэнне stepTaken да 0. Калі гэта будзе роўна 0, мы павялічваем значэнне jumpTaken, гэта значыць, што мы зрабілі адзін або некалькі крокаў, каб дасягнуць канца, і праверыць калі i больш, чым роўна maxValue, мы збіраемся вярнуць -1. І абнавіце значэнне stepTaken да maxValue-i. Мы захоўваем гэта ў stepTaken, таму што да наступнага скачка мы можам выканаць maxValue- я колькасць крокаў.

Як мы ўжо абвясцілі ўмову, што вярнуць і калі вярнуць, калі апошні элемент, які мы дасягнулі падчас праходжання, мы вяртаем значэнне jumpTaken. І гэта значэнне jumpTaken - гэта найменшая колькасць скачкоў, каб дасягнуць канчатковай кропкі

Мінімальная колькасць скачкоў для дасягнення канцаPin

Рэалізацыя ў C ++ для мінімальнай колькасці скачкоў, каб дасягнуць канца  

#include<iostream>
#include<algorithm>
using namespace std;
int getMinimumJumpTakens(int arr[], int n)
{
    if (n <= 1)
        return 0;
    if (arr[0] == 0)
        return -1;
    int maxValue = arr[0];
    int stepTaken = arr[0];
    int jumpTaken = 1;
    int i = 1;
    for (i = 1; i < n; i++)
    {
        if (i == n - 1)
            return jumpTaken;

        maxValue = max(maxValue, i + arr[i]);
        stepTaken--;
        if(stepTaken == 0)
        {
            jumpTaken++;
            if (i >= maxValue)
                return -1;

            stepTaken = maxValue - i;
        }
    }
    return -1;
}
int main()
{
    int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    int size = sizeof(arr) / sizeof(int);
    cout <<getMinimumJumpTakens(arr, size);
    return 0;
}
3

Рэалізацыя ў Java для мінімальнай колькасці скачкоў да канца  

class MinimumJumpTakens
{
    public static int getMinimumJumpTakens(int arr[])
    {
        if (arr.length <= 1)
            return 0;

        if (arr[0] == 0)
            return -1;

        int maxValue = arr[0];
        int stepTaken = arr[0];
        int jumpTaken = 1;

        for (int i = 1; i < arr.length; i++)
        {
            if (i == arr.length - 1)
                return jumpTaken;

            maxValue = Math.max(maxValue, i + arr[i]);
            stepTaken--;
            if (stepTaken == 0)
            {
                jumpTaken++;
                if(i >= maxValue)
                    return -1;
                stepTaken = maxValue - i;
            }
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
        System.out.println(getMinimumJumpTakens(arr));
    }
}
3

Аналіз складанасці  

Складанасць часу

Аб (п) дзе "П" - колькасць элементаў у масіве. Мы абыходзім масіў толькі адзін раз, што спрыяе лінейнай складанасці ў часе.

Глядзіце таксама
Выразныя паслядоўнасці

Касмічная складанасць

O (1) бо дадатковае месца не патрабуецца. Паколькі мы не выкарыстоўвалі дадатковае прастору, акрамя пэўнай колькасці зменных, мы гаворым, што гэты алгарытм мае пастаянную складанасць прасторы.