leetcode--55--跳跃游戏

题目描述：

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

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

解题思路1:

1、构建一个list来存储每一个索引位置最远能走到的位置
2、遍历nums，如果元素的索引位置比当前最长能走到的位置远，说明这个索引位置就已经到达不了了

代码1：

Python代码：

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums:  # 判断是否为空
            return True
        ls = []
        for index,num in enumerate(nums):
            ls.append(index+num)
        size = len(nums)

        longest = 0
        for index in range(size):
            if longest >= size-1:
                break
            if index > longest:  # 当前的位置下标已经超出了能够走到的最远位置
                break
            longest = max(longest, ls[index])

        return longest >= size-1   # 返回True或者False

s = Solution()
List = [2, 3, 1, 1, 4]
print(s.canJump(List))

结果为： True

代码精简：

class Solution:
    def canJump(self, nums):
        size, longest = len(nums), 0
        for i in range(size):
            if i <= longest:
                longest = max(longest, i + nums[i])
                if longest >= size - 1:
                    return True
        return False

C++代码：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int size = nums.size();
        if(size==0){
            return true;
        }
        vector<int> ls;
        for (int i=0; i<size; i++){
            ls.push_back(i+nums[i]);
        }

        int longest = 0;
        for (int j=0; j<size; j++){
            if (longest>=size-1){
                return true;
            }
            if(j > longest){
                break;
            }
            longest = max(longest, ls[j]);
        }
        return longest>=size-1;
    }
};

解题思路2:

  返回true有两种情况，一种是刚好跳到最后一个位置上，一种是超过最后一个位置。因为这题不需要求出每次跳的步数，只需要知道能否跳到最后。所以这两种情况其实就是一种。

1. 定义max用来存放当前能跳的最远距离。

2. i从0开始遍历，每到一个位置都判断max的值是否大于i。
2.1   如果小于 i 说明当前的最大步数不足以走到i位置，则直接返回false
2.2   否则，让当前i位置能走的最大步数和max比较。让max重新赋值。

代码2：

#include<iostream>
using namespace std;
bool canJump(int* nums, int numsSize) {
    int max=0;
    for(int i=0;i<numsSize;i++){
        if(i>max){
            return false;
        }else{
            max=max>(nums[i]+i)?max:(nums[i]+i);
        }
    }
    return true;
}
int main(){
	int nums[5] = { 2,3,1,1,4 };

	int len = sizeof(nums) / sizeof(nums[0]); // len = 20/4

	if (canJump(nums, len)){
		cout << "true" << endl;
	}
	else{
		cout << "false" << endl;
	}
	return 0;
}

代码3：

/*自顶向下的动态规划*/
#include<iostream>
using namespace std;
int *mark;//标记数组，表示mark[i]是否可以到达最后一个节点，是为1，否为-1
int min(int a, int b){
	return a < b ? a : b;
}
bool dfs(int *nums, int p,int len){
	if (mark[p] != 0){
		return mark[p] == 1 ? true : false;
	}
	int bigjump = min(nums[p] + p, len - 1);//可以跳到的下一个节点的下标最大值
	for (int next = p+1; next <= bigjump; next++){//next是下一个节点
		if (dfs(nums, next, len) == true){
			mark[next] = 1;
			return true;
		}
	}
	mark[p] = -1;//否则p不可以跳到结尾
	return false;
}
int main(){
	int nums[5] = { 3, 2, 1, 0, 4 };
	int len = sizeof(nums) / sizeof(nums[0]);  // len = 20/4
	mark = new int[len];
	for (int i = 0; i < len; i++){
		mark[i] = 0;
	}
	mark[len - 1] = 1; // mark数组为{0,0,0,0,1}
	if (dfs(nums, 0, len)){
		cout << "true" << endl;
	}
	else{
		cout << "false" << endl;
	}
	return 0;
}

参考链接:

[1]. LeetCode-55-跳跃游戏
[2]. LeetCode—55.跳跃游戏
[3]. leetcode–55–跳跃游戏

题目链接：https://leetcode-cn.com/problems/jump-game