حداقل تعداد پرش ها برای رسیدن به پایان


سطح دشواری ساده
اغلب در خشت آمازون Housing.com آزمایشگاه Moonfrog مورگان استنلی اتاق های OYO آزمایشگاههای SAP آزمایشگاه های والمارت
برنامه نویسی پویا ریاضی

بیان مسأله

فرض کنید شما یک صف از اعداد صحیح و هر عنصر از صف هر عدد را به عنوان حداکثر پرش هایی که می توان از آن نقطه گرفت ، نشان می دهد. وظیفه شما این است که از حداقل تعداد پرش برای رسیدن به پایان ، یعنی حداقل پرش هایی که می توان برای رسیدن به انتها انجام داد ، مطلع شوید.

مثال

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 مرحله به پایان خود برسیم ، بهتر است. ما فقط باید حداقل تعداد پرش هایی را پیدا کنیم که به ما کمک می کند تا انتهای آرایه را بدست آوریم.

ما می خواهیم تنظیمات را انجام دهیم قدم برداشت و maxValue به عنوان اولین عنصر یک آرایه. سپس ، تنظیم خواهیم کرد پرش همانطور که 1 اگر مقدار موجود در یک آرایه وجود داشته باشد ، باید 1 را برگردانیم. یک شرط نیز وجود دارد اگر اولین عنصر به عنوان 0 داده شود. این بدان معنی است که ما چیزی برای قدم برداشتن نداریم بنابراین فقط -1 را برمی گردانیم. سپس آرایه را تا طول آرایه پیمایش می کنیم. ما عملیات را تا رسیدن به آخرین مقدار آرایه ادامه می دهیم و مقدار را باز می گردانیم پرش.

ما حداکثر مقدار بین maxValue و مجموع i و arr [i]، و مقدار را کاهش دهید قدم برداشت همانطور که ما همچنان مقدار را کاهش می دهیم تا زمانی که مقدار stepTaken را به 1. برسانیم. اگر مشخص شد 0 است ، مقدار jumpTaken را افزایش می دهیم ، به این معنی که ما یک یا چند مرحله را برای رسیدن به انتها برداشته ایم و بررسی می کنیم اگر i بزرگتر از برابر است با maxValue، ما در حال بازگشت به -1 هستیم. و مقدار stepTaken را به maxValue-i به روز کنید. ما این مرحله را در stepTaken ذخیره می کنیم زیرا تا پرش بعدی می توانیم حداکثر مقدار حداکثر را انجام دهیم.

همانطور که قبلاً شرط بازگشت و زمان بازگشت را اعلام کرده ایم ، اگر آخرین عنصری که هنگام پیمایش به آن رسیدیم ، مقدار jumpTaken را برمی گردانیم. و این مقدار jumpTaken حداقل تعداد پرش ها برای رسیدن به نقطه پایان است

حداقل تعداد پرش ها برای رسیدن به پایان

پیاده سازی در ++ 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

پیاده سازی در جاوا برای حداقل تعداد پرش ها برای پایان یافتن

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 (N) جایی که "n" تعداد عناصر آرایه است. ما فقط یک بار از آرایه عبور می کنیم ، که به پیچیدگی زمان خطی کمک می کند.

پیچیدگی فضا

O (1) زیرا فضای اضافی مورد نیاز نیست. از آنجا که ما از فضای اضافی دیگری به غیر از تعداد متغیرهای خاصی استفاده نکرده ایم ، می گوییم این الگوریتم دارای پیچیدگی فضایی ثابت است.