3.3 跳跃问题(Jump Game)

3.3.1 问题描述

给定一个非负整数数组，初始状态你在数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。请判断，你最后是否能够抵达最后一个位置？

3.3.2 暴力求解

算法思路：设置一个新数组，遍历原数组，把元素能到达的位置都在新数组里标为1，最后看最后一位是否为1。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean canJump(int[] nums){
	int [] reachable=new int [nums.length];
	reachable[0]=1;//初始状态站在数组的第一个位置
	for(int i=0;i<nums.length-1;i++){
		/*核心代码*/
		if(reachable==1){//如果前面的位置可以到达当前位置
			for(int j=1;j<=nums[i]&&j+i<nums.length;j++){//保证数字是多少就走多少步，同时保证不能走越界
				reachable[i+j]=1;
			}
		}
	}
	return nums[nums.length-1]==1;
}

时间复杂度：O(mn)，n为元素组的元素个数，m为数组内元素值的最大值，也就是每次走的步数的最大值。

缺陷：子问题存在重复地判断或写入1，导致速度变慢。

3.3.3 动态规划

算法思路：如果第i个元素可以到达终点，则在它之前的元素，只要能到达i，就必然能到达终点。本着这个原则，我们把数组的后面往前看，逐个遍历数组元素，如果某个元素可以到达终点，就把它设置为终点，看在它前面的元素能不能到达这里。这样就形成了一个新的子问题，这个子问题跟原问题是一样的。所以我们使用递归的方法实现。
动态规划的思想

  • 问题分阶段(Multiple stage)：每个子问题的递归就是分阶段的体现
  • 阶段有依赖(Optimal sub-structure)：每一个子问题的都有一个前提，即依赖条件，就是子问题的终点能够到达父问题的终点
  • 依赖有重叠(Overlapping sub-problem)：我们解决了暴力求解中存在的重复操作

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean canJump(int[] nums){
	return canJump(nums,nums.length-1);
}

public boolea canJumps(int[] nums,int last){
	/*核心代码*/
	if(last==0)return true;//如果last指向首元素，则可以到达终点
	for(int i=last-1;i>0;i--){//从后往前遍历查找
		if(nums[i]+i>=last){//如果该元素可以到达终点，则在它前面的元素，只要能到达这里，就必然能到达终点。
			return canJump(nums,i);//把该元素设置为终点，开始递归
		}
	}
	return false;
}

时间复杂度：Θ(n)

3.3.4 解法三

算法思路：如果数组元素全为正数，则必然可以到达终点。所以问题的本质在于是否可以走过值为0的元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean canJump(int[] nums){
	int n=nums.length;
	int zeroPoint=-1;//指出值为0的元素
	for(int i=n-1;i>=0;i--){
		if(nums[i]==0){//如果元素值为0
			if(zeroPoint==-1){//如果该元素前面没有不可越过的0点
				zeroPoint =i;
			}
		}
		else if(zeroPoint!=-1){//前面存在不可越过的0点
			if(i+nums[i]>zeroPoint){//判断这个点能否越过0点
				zeroPoint=-1;
			}
		}
	}
	return zeroPoint==-1;
}