차례
문제 정책
당신이 정렬 정수 및 각 요소의 정렬 각 숫자를 해당 지점에서 취할 수있는 최대 점프로 나타냅니다. 당신의 임무는 끝까지 도달 할 수있는 최소 점프 수, 즉 끝까지 도달 할 수있는 최소 점프 수를 찾는 것입니다.
예
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 단계에서 끝까지 도달하면 더 좋습니다. 배열의 끝에 도달하는 데 도움이되는 최소 점프 수를 찾아야합니다.
우리는 설정을 할 것입니다 스텝 테이큰 및 최대값 배열의 첫 번째 요소로. 그런 다음 설정합니다 점프 배열에 값이 있으면 1을 반환해야하므로 1로 설정합니다. 또한 첫 번째 요소가 0으로 주어지면 조건이 주어집니다. 이는 우리가 앞으로 나아갈 것이 없음을 의미하므로 -1 만 반환합니다. 그런 다음 배열의 길이까지 배열을 순회합니다. 배열의 마지막 값에 도달 할 때까지 작업을 계속하고 점프.
우리는 사이의 최대 값을 찾을 것입니다 최대값 그리고 합계 i 및 arr [i], 값을 줄입니다. 스텝 테이큰 stepTaken의 값을 1으로 찾을 때까지 값을 계속 감소시키면서 0이 발견되면 jumpTaken의 값을 증가시킵니다. 이는 우리가 끝에 도달하기 위해 한 단계 이상을 밟았 음을 의미합니다. 만약 i 다음보다 큼 최대값, 우리는 -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) 추가 공간이 필요하지 않습니다. 특정 수의 변수 외에 추가 공간을 사용하지 않았기 때문에이 알고리즘은 일정한 공간 복잡성을 가지고 있다고 말합니다.
