这几天在复习算法。所以把以前看过的《算法导论》又看了一遍。不是每章节都看了，挑了有点忘记的，今天正好看了“贪心算法” 。所以在leetcode上找了关于“贪心算法”

　的题。

Jump Game

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.

For example: A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

从第一个开始，一步一步往上跳。看是否可以到达或者越过最后一个，可以的话返回True。

1 class Solution { 2 public: 3     bool canJump(int A[], int n) { 4          int reach = 1; // 可以达到的最大右边 5         for (int i = 0; i < reach && reach < n; ++i) 6             reach = max(reach,  i + 1 + A[i]); 7         return reach >= n; 8   9     }10 };

Jump Game II

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.

For example: Given array A = [2,3,1,1,4]

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.

1 // LeetCode, Jump Game II 2 // 时间复杂度O(n)，空间复杂度O(1) 3 class Solution { 4 public: 5     int jump(int A[], int n) { 6         int step = 0; // 最小步数 7         int left = 0; 8         int right = 0;  // [left, right]是当前能覆盖的区间 9         if (n == 1) return 0;10 11         while (left <= right) { // 尝试从每一层跳最远12             ++step;13             const int old_right = right;14             for (int i = left; i <= old_right; ++i) {15                 int new_right = i + A[i];16                 if (new_right >= n - 1) return step;17 18                 if (new_right > right) right = new_right;19             }20             left = old_right + 1;21         }22         return 0;23     }24 };