C++LeetCode 구현(45.점프 게임 의 2)

[LeetCode]45.점프 게임 II 점프 게임 2
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
이 문 제 는 이전 문제 입 니 다.  Jump Game  의 연장,그 문 제 는 마지막 숫자 에 도달 할 수 있 느 냐 는 것 이다.이 문 제 는 마지막 위치 에 도달 하 는 최소 점프 수 만 을 구 하 는 것 이다.기본적으로 마지막 위치 에 도달 할 수 있 는 것 같다.이 문제 의 핵심 방법 은 탐욕 알고리즘 Greedy 의 사상 을 이용 하여 푸 는 것 이다.왜 그런 지 생각해 보 자.빨리 끝까지 뛰 기 위해 서 는 한 걸음 한 걸음 뛸 수 있 는 범 위 를 알 고 싶 습 니 다.여기 서 탐욕 은 뛸 수 있 는 범위 에서 점프 력 이 가장 먼 위 치 를 선택해 야 하 는 것 이 아 닙 니 다.이렇게 선택 하 는 것 이 꼭 최 적 화 된 것 이 아니 기 때문에 탐욕 알고리즘 같 지 않 습 니 다.사실 여기 서 탐 내 는 것 은 도달 할 수 있 는 가장 먼 범위 이다.현재 점프 할 수 있 는 모든 위 치 를 두루 돌아 다 닌 다음 에 이 위치의 점프 력 에 따라 다음 단계 에 도달 할 수 있 는 가장 먼 거 리 를 예측 하고 가장 먼 범 위 를 탐낸다.이 범위 가 끝 에 도달 하면 현재 사용 하 는 걸음 수 는 반드시 가장 작은 걸음 이다.현재 도달 할 수 있 는 가장 먼 위치 와 이전에 도달 할 수 있 는 가장 먼 위 치 를 저장 하기 위해 서 는 두 개의 변수 cur 와 pre 가 각각 필요 합 니 다.cur 가 마지막 위치 에 이 르 지 않 으 면 순환 이 계속 되 고 pre 가 먼저 cur 의 값 을 부여 하여 지난번 순환 후에 도달 할 수 있 는 가장 먼 위 치 를 표시 합 니 다.만약 에 현재 위치 i 가 pre 보다 작 으 면 이전 점프 에서 도달 할 수 있 는 범위 내 에 있 음 을 설명 합 니 다.현재 위치 에 점프 력 을 더 해서 cur 를 업데이트 합 니 다.cur 를 업데이트 하 는 방법 은 현재 의 cur 와 i+A[i]의 비교적 큰 값 을 비교 하 는 것 입 니 다.만약 에 문제 에서 끝까지 도달 할 수 있 는 지 설명 하지 않 으 면 이때 pre 와 cur 가 같 는 지 판단 할 수 있 습 니 다.만약 에 똑 같이 설명 하면 cur 가 업데이트 되 지 않 으 면 끝 에 도달 할 수 없습니다.-1 로 돌아 갑 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, n = nums.size(), i = 0, cur = 0;
        while (cur < n - 1) {
            ++res;
            int pre = cur;
            for (; i <= pre; ++i) {
                cur = max(cur, i + nums[i]);
            }
            if (pre == cur) return -1; // May not need this
        }
        return res;
    }
};

또 하나의 표기 법 은 위의 해법 과 약간 다 르 지만 본질 적 인 사상 은 똑 같 습 니 다.여기 cur 는 현재 도착 할 수 있 는 가장 먼 위치 입 니 다.last 는 지난 단계 에 도착 할 수 있 는 가장 먼 위치 입 니 다.배열 을 옮 겨 다 니 며 먼저 i+nums[i]로 cur 를 업데이트 합 니 다.이것 은 위의 해법 에서 말 한 다음 에 현재 위치 가 last 에 도착 하면 판단 합 니 다.즉,지난 단계 에 도착 할 수 있 는 가장 먼 위 치 는 다시 한 번 뛰 어야 한 다 는 것 을 설명 합 니 다.last 할당 값 을 cur 로 하고 걸음 수 res 를 1 로 늘 립 니 다.여기 서 최적화 시 켜 cur 가 끝 에 도착 하면 바로 break 하면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, n = nums.size(), last = 0, cur = 0;
        for (int i = 0; i < n - 1; ++i) {
            cur = max(cur, i + nums[i]);
            if (i == last) {
                last = cur;
                ++res;
                if (cur >= n - 1) break;
            }
        }
        return res;
    }
};

C++구현 LeetCode(45.점프 게임 의 2)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 점프 게임 의 2 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!