045.Jump Game I & II

虽然是 hard 类的题目，但其实也很简单。不过代码如果想要既美观又高效，可能就要费点功夫了。题目链接: Jump Game, Jump Game II。

原始代码

这个是我写的Jump 2的代码，Jump 1 和 2的代码基本就是一回事。

思路也比较直接，用max_pos记录从当前节点开始，可以到达的最远位置(end 或者max_pos)

若最远位置已经超出长度，那么直接返回就行了。

对于Jump 1，略微修改下代码，检测step的长度，如果step的数量超过数组长度，那么肯定是走重复了。

class Solution {
public:
	int jump(vector<int>& nums) {
		if (nums[0] == 0||nums.size()==1)
			return 0;
		int step = 0, max_pos = 0, temp, i;

		while (max_pos < nums.size()) {
			temp = 0;
			int start = max_pos + 1, end = max_pos + nums[max_pos] + 1;
			if (end > nums.size() - 1) {
				step++;
				break;
			}
			for (i = start; i < end; i++) {
				if (temp < i + nums[i]) {
					temp = i + nums[i];
					max_pos = i;
				}
			}

			step++;
		}

		if (max_pos >= nums.size()) {
			step++;
		}

		return step;
	}
};

可以看到这个代码比较挫，看起来就不够美观，于是到dicuss 看了看别的大佬的答案，感觉打开了新世界的代码..

Jump 2 的简短代码

class Solution {
public:
    int jump(int A[], int n) {
        int ret = 0;
        int last = 0;
        int curr = 0;
        for (int i = 0; i < n; ++i) {
            if (i > last) {
                last = curr;
                ++ret;
            }
            curr = max(curr, i+A[i]);
        }

        return ret;
    }
};

比如就是我们题目中的[2,3,1,1,4]。

初始状态是这样的：cur表示最远能覆盖到的地方，用红色表示。
last表示已经覆盖的地方，用箭头表示。它们都指在第一个元素上。

接下来，第一元素告诉cur，最远咱可以走2步。于是：

下一循环中，i指向1（图中的元素3），发现，哦，i小于last能到的范围，于是更新last（相当于说，进入了新的势力范围），步数ret加1.同时要更新cur。因为最远距离发现了。

接下来，i继续前进，发现i在当前的势力范围内，无需更新last和步数ret。更新cur。

i继续前进，接下来发现超过当前势力范围，更新last和步数。cur已然最大了。

最后，i到最后一个元素。依然在势力范围内，遍历完成，返回ret。

Jump 1 的简短代码

本题用一个数 reach 表示能到达的最远下标，一步步走下去，

如果发现在 reach 范围之内某处能达到的范围大于 reach，

那么我们就用更大的范围来替换掉原先的 reach，这样一个局部的最优贪心策略，在全局看来也是最优的

因为 局部能够到达的最大范围也是全局能够到达的最大范围：

class Solution {
public:
	bool canJump(vector<int>& nums) {
		int reach = nums[0];
		for (int i = 1; i < nums.size() && reach >= i; i++)
			if (i + nums[i] > reach) reach = i + nums[i];  //贪心策略
		return reach >= (nums.size() - 1) ? true : false;
	}
};

小结

Jump 2 的代码还是蛮神奇的…有点意思.