점프 게임

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 블룸버그 게시물에서 Facebook Microsoft
배열 탐욕스러운조회수 36

점프 게임에서 우리는 정렬 음이 아닌 정수의 경우 처음에는 배열의 첫 번째 인덱스에 배치됩니다. 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타냅니다. 마지막 색인에 도달 할 수 있는지 확인하십시오.

예

입력 : arr = [2,3,1,1,4]

출력 : 참

입력 : arr = [3,2,1,0,4]

출력 : false

주요 아이디어

여기서는 탐욕스러운 접근 방식을 사용합니다. 현재 인덱스보다 작거나 같은 인덱스에있을 경우 도달 할 수있는 최대 인덱스를 찾기 위해 배열을 탐색합니다.

점프 게임을위한 알고리즘

  1. 도달 할 수있는 최대 인덱스를 가리키는 변수 max_index = 0을 초기화합니다.
  2. 현재 인덱스를 가리키는 변수 curr_index = 0을 초기화합니다. 정렬.
  3. 배열을 반복합니다.
  4. (curr_index + arr [curr_index]) 인 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를 가리 킵니다.

점프 게임핀

마지막 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

점프 게임의 복잡성 분석

시간 복잡성

의 위에)  모든 i 번째 인덱스에서 도달 할 수있는 최대 인덱스를 계산하기 위해 하나의 루프 만 사용하므로 최악의 경우 전체 배열을 한 번 탐색합니다.

공간 복잡성

O (1) 구현하는 동안 보조 공간을 사용하지 않기 때문입니다.

 

Translate »