מספר קפיצות מינימלי כדי להגיע לסוף


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית Housing.com מעבדות מונפרוג מורגן סטנלי חדרי OYO מעבדות SAP מעבדות וולמארט
תכנות דינמי מתמטיקה

הצהרת בעיה

נניח שיש לך מערך של מספרים שלמים וכל אלמנט של מערך מציין כל מספר כקפיצות מקסימליות שניתן לקחת מאותה נקודה. המשימה שלך היא לברר את מספר הקפיצות המינימלי כדי להגיע לסוף, כלומר מינימום קפיצות שניתן לבצע כדי להגיע לסוף.

דוגמה

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

הסבר: כשאנחנו דורכים על 2 זה ייקח שני צעדים ונגיע ל- 7, זה קפיצה אחת, ומ- 1 יש לנו 7 צעדים ונהיה בסוף עם 5 קפיצות כתשובתנו.

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 צעדים נגיע לקצה, עדיף. עלינו רק למצוא את מספר הקפיצות המינימלי שעוזר לנו להגיע לסוף המערך.

אנחנו הולכים להגדיר את צעד אחר צעד ו ערך מקסימלי כאלמנט הראשון במערך. ואז, נקבע jumpTaken כ- 1 כמו שעלינו להחזיר 1 אם קיים הערך במערך. יש גם תנאי שניתן אם האלמנט הראשון נקבע 0. זה אומר שאין לנו מה להתקדם ולכן נחזור רק -1. לאחר מכן נחצה את המערך לאורך המערך. נמשיך בפעולות עד להשגת הערך האחרון של המערך ונחזיר את jumpTaken.

אנו נמצא את הערך המרבי בין ה- ערך מקסימלי וסכום של i ו arr [i], והוריד את הערך של צעד אחר צעד עד 1. ככל שאנו ממשיכים להקטין את הערך עד שנמצא את הערך של stepTaken ל- 0. אם נמצא שהוא 0, אנו מעלים את הערך של jumpTaken, פירושו שלקחנו צעד אחד או יותר כדי להגיע לסוף, ונבדוק אם i גדול משווה ל- ערך מקסימליאנחנו הולכים לחזור -1. ועדכן את הערך של stepTaken ל- maxValue-i. אנו מאחסנים זאת ב stepTaken מכיוון שעד לקפיצה הבאה אנו יכולים לבצע maxValue- מספר שלבים.

כפי שכבר הכרזנו על התנאי מה להחזיר ומתי לחזור, אם האלמנט האחרון אליו הגענו בזמן המעבר, אנו מחזירים את ערך 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

יישום ב- 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 (n) איפה "N" הוא מספר האלמנטים במערך. אנו עוברים דרך המערך פעם אחת בלבד, מה שתורם למורכבות הזמן הליניארית.

מורכבות בחלל

O (1) מכיוון שלא נדרש מקום נוסף. מכיוון שלא השתמשנו במרחב נוסף מלבד מספר משתנים מסוים, אנו אומרים כי לאלגוריתם זה מורכבות שטח קבועה.