数组跳跃问题

 Algorithm
 

跳跃游戏

  • 描述：给定数组arr，arr[i]=k代表可以从位置i向右跳1 ~ k个距离。比如，arr[2]=3，代表从位置2可以跳到位置3、位置4或位置5。如果从位置0出发，返回最少跳几次能跳到arr最后的位置上。如果arr长度为N，要求实现时间复杂度为O(N)、额外空间复杂度为O(1)的解法。
  • 输入：

第一行输入一个正整数N，$1 \le N \le 100$，表示数组的元素数。

第二行输入N个数，用空格隔开，表示一个数组中的所有数。

  • 输出：

输出一个整数，表示最少跳几次。

  • 样例输入：

6
3 2 3 1 1 4

  • 样例输出：

2

  • 样例解释：

arr[0]=3，选择跳到位置2；arr[2]=3，可以跳到最后的位置。所以返回2。

  • 解题思路：

这道题是一道简单的不能再简单的“水题”，可以说是动态规划的入门题。会者不难，难者不会。

思路太简单，略，←_←。直接上代码。
感觉和剑指offer上“股票的最大利润”一题有点像。

  • 参考代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int jump(vector<int>& arr) {
            if(arr.empty()) return 0;
            int jump=0;
            int cur=0;
            int next=0;
            for(int i=0;i<arr.size();i++) {
                if(cur<i) {
                    jump++;
                    cur=next;
                }
                next=max(next,i+arr[i]);
            }
            return jump;
        }
    };
 Previous

Heap