[LeetCode] 45. 점프 게임 II 문제 풀이 보고서 (파 이 썬)

저자: 음 설 명 초 id: fuxuemingzhu 개인 블 로그:http://fuxuemingzhu.cn/
목차
제목 설명
제목
풀이 방법
욕심
날짜
제목 주소:https://leetcode.com/problems/reach-a-number/description/
제목 설명
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.
제목 의 대의
매번 뒤로 점프 할 수 있 는 칸 수 는 현재 의 포인트 와 같 습 니 다.최소한 몇 걸음 이면 마지막 칸 을 늘 릴 수 있 습 니 다.
문제 풀이 방법
욕심
이 문 제 는 55. Jump Game 과 비슷 합 니 다. 모두 마지막 위치 까지 어떻게 뛰 어 내 릴 수 있 는 지 를 구 하 는 것 입 니 다. 다만 이 문제 에 조건 을 붙 였 습 니 다. 바로 우리 가 필요 로 하 는 가장 작은 걸음 수 입 니 다. 사용 하 는 전략 은 욕심 입 니 다.
우 리 는 자신 이 현재 도달 할 수 있 는 몇 개의 위치 에서 어느 위치 로 뛰 어 들 었 는 지 욕심 낼 때마다 다음 단계 에서 가장 멀리 뛸 수 있다.그리고 우 리 는 지금 이 자리 에 뛰 어 올 랐 기 때문에 우 리 는 이 단계 의 도약 에서 다음 단계 에 가장 좋 은 결 과 를 남 겼 다.
따라서 하나의 cur 를 사용 하여 현재 걸음 이 도달 할 수 있 는 가장 먼 위 치 를 표시 하고 pre 를 사용 하여 지난번 에 도달 할 수 있 는 가장 먼 위 치 를 표시 합 니 다.따라서 우 리 는 이전 단계 의 커버 범위 내 에서 현재 뛸 수 있 는 가장 먼 위 치 를 옮 겨 다 니 며 cur 를 업데이트 해 야 합 니 다.계산 자원 을 절약 하 는 방법 은 이전에 검 사 했 던 위 치 를 Pos 로 저장 하 는 것 입 니 다. 이렇게 매번 검사 하 는 범 위 는 pos ~ pre 입 니 다.

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        reach = 0
        cur = 0
        N = len(nums)
        count = 0
        pos = 0
        while cur < N - 1:
            count += 1
            pre = cur
            while pos <= pre:
                cur = max(cur, pos + nums[pos])
                pos += 1
        return count

C + + 버 전의 코드 는 다음 과 같 습 니 다.

class Solution {
public:
    int jump(vector<int>& nums) {
        int N = nums.size();
        int pos = 0;
        int count = 0;
        int pre = 0, cur = 0;
        while (cur < N - 1) {
            count ++;
            pre = cur;
            while (pos <= pre) {
                cur = max(cur, pos + nums[pos]);
                pos ++;
            }
        }
        return count;
    }
};

날짜.
2018 년 11 월 28 일 -- 아래층 에 전염병 이 있다 고 합 니 다.