Үсрэх тоглоом  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Bloomberg Facebook-ийн Microsoft-
Array Шунахай

Үсрэх тоглоом дээр бид массив сөрөг бус бүхэл тооноос эхлээд та массивын эхний индекс дээр байрлана. Массивын элемент бүр тухайн байрлал дахь хамгийн их үсрэлтийн уртыг илэрхийлнэ. Сүүлийн индекст хүрэх боломжтой эсэхийг тодорхойл.

Жишээ нь  

Оролт: arr = [2,3,1,1,4]

Гаралт: үнэн

Оролт: arr = [3,2,1,0,4]

Гаралт: худал

Үндсэн санаа  

Бид энд шунахай аргыг ашиглах болно. бид массивыг тойрон гарч, одоогийн индексээс бага эсвэл тэнцүү аль ч индекс дээр байгаа бол хүрч болох хамгийн дээд индексийг олно.

Үсрэх тоглоомын алгоритм  

  1. Хамгийн их индексийг зааж өгөх max_index = 0 хувьсагчийг эхлүүлнэ үү.
  2. Дахь одоогийн индексийг зааж буй curr_index = 0 хувьсагчийг эхлүүлнэ үү массив.
  3. Массив дээр давтах.
  4. Хэрэв бид curr_index-ээс үсрэх хамгийн дээд индекс болох (curr_index + arr [curr_index]) бол max_index = curr_index + arr [curr_index] -ийг шинэчил.
  5. Curr_index-ийн өсөлт.
  6. Хэрэв curr_index n ба max_index-ээс бага бол 4,5,6-р алхамыг давт.
  7. Сүүлийн индекст хүрсэн эсэхээ шалгаарай.

Үүнийг жишээгээр ойлгуулъя.

Энд улбар шар өнгө нь curr_index, цэнхэр өнгө нь max_index руу зааж өгдөг

Үсрэх тоглоомPin

Бидний эцсийн max_index> = curr_index тул бид хамгийн сүүлийн индекст хүрч чадна.

Үсрэх тоглоомын хэрэгжилт  

C ++ програм

#include <bits/stdc++.h>
using namespace std;
/* Function to check if we can reach last index or not. */
void JumpGame(int arr[], int n)
{
    int max_index = 0; // Pointer pointing to to maximum index we can jump using the first i elements of the array.
    for (int i = 0; (i < n) and (i <= max_index); i++)
    {
        max_index = max(max_index, i + arr[i]);
    }
    if ((max_index >= (n - 1))) // Checking if we reached last index or not.
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
    return;
}
int main()
{
    int arr[] = {2, 3, 1, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    JumpGame(arr, n);
    return 0;
}


true

JAVA хөтөлбөр

public class Main
{
    
    /* Function to check if we can reach last index or not. */
    public static void JumpGame(int arr[], int n)
    {
        int max_index = 0; // Pointer pointing to to maximum index we can jump using the first i elements of the array.
        for (int i = 0; (i < n) && (i <= max_index); i++)
        {
            max_index = Math.max(max_index, i + arr[i]);
        }
        if ((max_index >= (n - 1))) // Checking if we reached last index or not.
        {
            System.out.println("true");
        }
        else
        {
            System.out.println("false");
        }
        return;
    }
  public static void main(String[] args) {
      int n=6;
    int[] arr={3, 2, 4, 1, 3, 2};
    JumpGame(arr ,n);
  }
}
true

Үсрэх тоглоомын нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N)  ith индекс бүрээс хүрэх хамгийн дээд индексийг тооцоолохын тулд бид зөвхөн нэг давталтыг ашиглаж байгаа тул хамгийн муу тохиолдолд бүх массивыг нэг удаа туулах болно.

мөн үзнэ үү
4 сум

Сансрын нарийн төвөгтэй байдал

O (1) Учир нь бид үүнийг хэрэгжүүлэх явцад нэмэлт зай ашигладаггүй.