55. 跳跃游戏

问题55 跳跃游戏 ★☆☆☆☆

https://leetcode.cn/problems/jump-game/

我的思路是这样的，分析题目，这个题目的关键在于0元素点，如果除结尾元素外，没有0元素点，那么肯定是能从开始元素跳到结尾元素的。所以可以倒序循环找0元素点，如果找到了，那么需要判断在它前面是否有某个元素可以跳过这个0元素点，如果没有，那说明跳不到结尾元素了，循环结束；如果有，那么继续上述循环处理即可。看了眼官方题解，官方题解代码简洁很多，但思路我觉得是差不多的，都可以看作贪婪算法的思路。

这个题目可以看作问题45的前置题目，问题55是判断有没有可能从起点跳到终点，问题45是限定可以从起点跳到终点而计算最小跳数。

	public boolean canJump(int[] nums) {
		int len = nums.length;

		int idx = len - 1;
		int lastZeroIdx;
		while ((lastZeroIdx = lastZero(nums, idx)) != -1) {
			idx = canJumpZeroLastIdx(nums, lastZeroIdx);
			if (idx == -1) {
				return false;
			}
		}

		return true;
	}

	private int lastZero(int[] nums, int idx) {
		for (int i = idx - 1; i >= 0; i--) {
			if (nums[i] == 0) {
				return i;
			}
		}

		return -1;
	}

	private int canJumpZeroLastIdx(int[] nums, int zeroIdx) {
		for (int i = zeroIdx - 1; i >= 0; i--) {
			if (nums[i] > (zeroIdx - i)) {
				return i;
			}
		}

		return -1;
	}

在 LeetCode 查看