[leetcode]贪心算法之jumpgame(一)(二)

一时失言乱红尘 2021-09-28 12:00 311阅读 0赞

### 贪心算法之jumpgameI、II ###

*  I
 *   *  题干 I
     *  答案 I
     *  反思 I
 *  II
 *   *  题干II
     *  答案II
     *  反思II

# I #

## 题干 I ##

[leetcode入口][leetcode]

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.

Determine if you are able to reach the last index.

Ex1:

> Input: \[2,3,1,1,4\]  
> Output: true  
> Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Ex2:

> Input: \[3,2,1,0,4\]  
> Output: false  
> Explanation: You will always arrive at index 3 no matter what. Its maximum  
> jump length is 0, which makes it impossible to reach the last index.

## 答案 I ##

class Solution { 
    public:
        bool canJump(vector<int>& nums) { 
            int size=nums.size();
            
            int reach=0;
            
            for(int i=0;i<size;i++){ 
                if(i>reach) return false;
                
                reach=max(reach,i+nums[i]);
            }
            
            return true;
        }
    };

## 反思 I ##

题目特点：  
一维数组，下标跳越（可在一个范围内跳跃），  
可以逐个下标遍历，  
设置一个reach变量  
一旦下标i超过了reach，就返回假  
否则循环结束表示成功。

# II #

## 题干II ##

[leetcode题目入口][leetcode 1]

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.

## 答案II ##

class Solution { 
    public:
        int jump(vector<int>& nums) { 
            int size=nums.size();
            if(size==1) return 0;
            
            //cur代表当前能到达的最远位置，last表示上一步能到达的最远位置
            int cur=0;
            int last=0;
            int res=0;
            
            for(int i=0;i<size;i++){ 
                cur=max(cur,i+nums[i]); //当前步能到达的最远位置
                
                if(i==last){ 
                    ++res;
                    last=cur;
                    
                    if(last>=size-1) break;
                }
            }
            return res;
                
            
        }
    };

## 反思II ##

这题需要求出**每一步下可以达到的最远距离**(贪心)  
因此，可以设置变量  
res - 步数  
last - 上一步可以达到的最远距离  
cur - 当前步可以达到的最远距离 （不断更新）

[leetcode]: https://leetcode.com/problems/jump-game/
[leetcode 1]: https://leetcode.com/problems/jump-game-ii/