本周的两道题目同样也来自LeetCode。分别是一道为难度为Medium的55题Jump Game，以及它的升级版–难度为Hard的45题Jump Game II。本次之所以选择这两道题，是因为本周算法课刚好学了贪心算法(Greedy)，而这两道题恰巧用的就是贪心算法。

55题

一、问题描述

二、问题分析

题目给定一个数组(其实真正使用vector存的)，要求我们判定可否从第一个元素位置经过n步跳跃到达最后一个元素位置，其中每次可跳跃的最大步数就是这个位置所存储的值，而跳跃的总步数n是不限的。如何判断能否到达最后的位置呢？我们可以考虑设置一个最大位置maxStep来记录此时此刻可以达到的最远距离，并且遍历Input量，不断更新maxStep，看看是否存在“上个时间可达到的最远距离小于此时所处的节点位置“的情况(maxStep < currentSetp)，如果存在这种情况，说明跳跃中间存在断档，有个位置无法从先前的位置跳到，因此本题答案也即为否定。而对于maxStep的更新也是简单的，只需要遍历之时看看此时位置+此位置的可跳步数是否大于之前的maxStep，如是，则更新它。

三、问题求解

针对问题分析，以下是c++源代码：

---

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.size() == 1) return true;
        int maxStep = 0;
        int currentSetp = 0;
        for (auto it = nums.begin(); it != nums.end(); it++, currentSetp++) {
        	if (maxStep < currentSetp) return false;
        	int tempStep = currentSetp + (*it);
        	if (tempStep > maxStep) maxStep = tempStep;
        }
        return true;
    }
};

45题

一、问题描述

二、问题分析

这道题虽说是上一道题的升级版，问法也差不多，但在解题思路上却跟上题很大的不同。55题是问能否到达最后一个元素位置，而45题问的是最少多少步能到达最后的位置(前提是已经确定能够到达)。本题所有的算法就是贪心算法，每次访问一个位置，看看它能到达的最远位置之内的其他位置所能到达的最远位置是多少。每次偶读贪心的选择最远的位置，这样能保证总步数最小。主要原因是这个数组是二维的，因此每次选最远即可。因此这个问题有两个循环。外循环看看此位置可达的最远位置是多少，内循环在此位置与标记的最远位置之间进行遍历，而每个内循环也被我称作一层。

三、问题求解

针对问题分析，以下是c++源代码：

---

class Solution {
public:
    int jump(vector<int>& nums) {
    	if (nums.size() == 1) return 0;
    	int steps = 0;
        int maxStep = 0;
        int currentSetp = 0;
        int n = nums.size();

        while (currentSetp < n) {
        	steps++;
        	int tempStep = currentSetp + nums[currentSetp];
        	if (tempStep > maxStep) maxStep = tempStep;
        	if (maxStep >= n - 1) {
        		return steps;
        	}
        	currentSetp++;

        	int layer = maxStep;
        	while (currentSetp < layer) {
        		int tempStep2 = currentSetp + nums[currentSetp];
        		if (tempStep2 > maxStep) maxStep = tempStep2;
        		if (maxStep >= n - 1) {
        			return ++steps;
        		}
        		currentSetp++;
        	}
        }
    }
};