C++刷LeetCode（45. 跳跃游戏 II）【贪心思想】

糖逗

题目描述：

1. 给定一个非负整数数组，你最初位于数组的第一个位置。
   
2. 
   
3. 数组中的每个元素代表你在该位置可以跳跃的最大长度。
   
4. 
   
5. 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
   
6. 
   
7. 示例:
   
8. 
   
9. 输入: [2,3,1,1,4]
   
10. 输出: 2
    
11. 解释: 跳到最后一个位置的最小跳跃数是 2。
    
12.      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
    
13. 说明:
    
14. 
    
15. 假设你总是可以到达数组的最后一个位置。
    
16. 
    
17. 来源：力扣（LeetCode）
    
18. 链接：https://leetcode-cn.com/problems/jump-game-ii
    
19. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int jump(vector<int>& nums) {
   
4.         int res = 0;
   
5.         int cur = 0;
   
6.         int len = nums.size();
   
7.         while(cur < len-1){
   
8.             int step = nums[cur];
   
9.             int max_pos = 0;
   
10.             int temp;
    
11.             for(int i = 1; i <= step; i++){
    
12.                 if(cur + i >= len - 1)return ++res;
    
13.                 if(cur + i + nums[cur + i] > max_pos){
    
14.                     max_pos = cur + i + nums[cur + i];
    
15.                     temp = cur + i;
    
16.                 }
    
17.             }
    
18.             res++;
    
19.             cur = temp;
    
20.         }
    
21.         return res;
    
22.     }
    
23. };

复制代码

参考链接：https://leetcode-cn.com/problems ... i-duo-jie-fa-by-10/