算法设计与分析（七）

贪心算法更多技术博客 http://vilins.top/题目这次我们选择两题贪心算法作为练习这两道题目是有关系的一个是比较基础的贪心另一个是难一点的贪心。Jump GameGiven 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.Example 1:Input: [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.Example 2:Input: [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter what. Its maximumjump length is 0, which makes it impossible to reach the last index.Jump Game IIGiven 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: 2Explanation: 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.分析Jump Game题目的意思是给定一个数组一个人从起点小标为0出发然后最多走在当前下标的数组元素的步数到达下一个下标同样走最多当前下标元素对应数组值的步数到达下一个位置这里需要注意的是不必走完数组值的步数例如数值为3你可以选择走一步两步或者三步最后看看是否可以有路径到达最后一个顶点。在解决这个问题的时候我们通过维护一个当前可以到达的最远下标这也是这题贪心的体现所在然后遍历数组有下面几种情况如果遍历当前下标的值大于当前最大算力表面这个点是不可达的直接退出。如果当前的最大算力大于等于数组长度-1那么当前的算力可以到达目的返回true。如果遍历的当前数组元素的算力大于前一个下标为止的最大算力更新最大算力。Jump Game II这题是上面一题的加强版在原来的规则下找出能到达目的需要走的最小步数。我们也是维护一个算力值当我们遍历到某个下标假设当前元素值为k的时候我们遍历从k元素开始的k个元素值个元素找出接下来K个元素某个点的最大算力然后我们下一次遍历的起点就是这个最大算力的点重复上面步骤直到算力可以到达目标下标。这里的贪心算法的特点体现在当我们遍历到当前数组元素的时候我们总是找接下来k个元素最大算力的一个这样就保证了我们找到的路径是最短的。值得注意的是有些特殊的情况例如一步就能到达目的的我们的算法不适合必须从当中分离出来还有就是我们是以找到最大算力的点的时候记录步数那么说明最后到达目的的那一步我们没有记录在返回的时候要记得加上。源码Jump Gameclass Solution { public: bool canJump(vectorint nums) { int result 0; if(nums.size() 1) { return true; } for(int i 0; i nums.size() - 1; i) { if(i result) { return false; } if(result nums[i] i) { result nums[i] i; } //cout result endl; if(result nums.size() - 1) { return true; } } return false; } };Jump Game IIclass Solution { public: int jump(vectorint nums) { int result 0, count 0; if(nums.size() 1) { return 0; } if(nums.size() ! 0) { if(nums[0] 0 nums.size() - 1) { return 1; } } int max 0; for(int i 0; i nums.size() - 1;) { //cout i endl; result nums[i] i; int tag 0; int index i; for(int j i 1; j nums[i] i ; j) { if((nums[j] j max)) { max nums[j] j; index j; tag 1; } } //cout max endl; if(tag 1) { count; result max; i index; } else { i; } //cout result endl; if(result nums.size() - 1) { break; } } return count 1; } };算法复杂度分析在Jump Game中在一次遍历必定能找出来所以最大的复杂度是O(n);对于Jump Game II这个算法的复杂度是不稳定的在O(n)基础上增加最好的情况是O(n)这是最好的情况也就是每次找最大算力的总是最后一个的时候。更多技术博客 http://vilins.top/