끝에 도달하기위한 최소 점프 수


난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Housing.com 문 프로그 연구소 모건 스탠리 (Morgan Stanley) 오요 룸 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 단계에서 끝까지 도달하면 더 좋습니다. 배열의 끝에 도달하는 데 도움이되는 최소 점프 수를 찾아야합니다.

우리는 설정을 할 것입니다 stepTakenmaxValue 배열의 첫 번째 요소로. 그런 다음 설정합니다 jumpTaken 배열에 값이 있으면 1을 반환해야하므로 1로 설정합니다. 또한 첫 번째 요소가 0으로 주어지면 조건이 주어집니다. 이는 우리가 앞으로 나아갈 것이 없음을 의미하므로 -1 만 반환합니다. 그런 다음 배열의 길이까지 배열을 순회합니다. 배열의 마지막 값에 도달 할 때까지 작업을 계속하고 jumpTaken.

우리는 사이의 최대 값을 찾을 것입니다 maxValue 그리고 합계 iarr [i], 값을 줄입니다. stepTaken stepTaken의 값을 1으로 찾을 때까지 값을 계속 감소시키면서 0이 발견되면 jumpTaken의 값을 증가시킵니다. 이는 우리가 끝에 도달하기 위해 한 단계 이상을 밟았 음을 의미합니다. 만약 i 다음보다 큼 maxValue, 우리는 -1을 반환 할 것입니다. 그리고 stepTaken의 값을 maxValue-i로 업데이트합니다. 다음 점프까지 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

끝에 도달하기위한 최소 점프 수를위한 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) 어디에 "엔" 배열의 요소 수입니다. 우리는 배열을 한 번만 통과하므로 선형 시간 복잡성에 기여합니다.

공간 복잡성

O (1) 추가 공간이 필요하지 않습니다. 특정 수의 변수 외에 추가 공간을 사용하지 않았기 때문에이 알고리즘은 일정한 공간 복잡성을 가지고 있다고 말합니다.