CY-Left

LeetCode基本功底

55. Jump Game 跳跃游戏

Jump Game 跳跃游戏

原题&翻译

Given an array of non-negative integers, you are initially positioned at the first index of the array.
给出一个非负数组, 你被默认初始化到数组的第一个元素上

Each element in the array represents your maximum jump length at that position.
你脚下的数组中每一个元素, 都意味着此时你的最大跳跃数

Determine if you are able to reach the last index.
判断是否可以调到终点

示例 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
分析: 你在 2 元素上, 最多可以跳两步, 然后这里先跳一步, 到 3 上, 然后跳三步到 4, 成功

示例 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.
分析: 无论如何, 你都会抵达 0 元素上, 动弹不得, 失败

解题思路

  1. 动态规划

|0,1,2,3,4|
[2,3,1,1,4]
从后往前判断, 第四个元素是终点,计做第四号元素为 true, 第三号元素最多可以跳三步, 三步范围内, 有元素为 true, 所以自身也可以跳跃到终点, 几所第三号元素为 true, 同理判断 2,1,0元素步数范围内是否有 true

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<bool> dp(nums.size());
        for (int i=nums.size()-1; i>=0; i--) {
            //cout<<nums[i]<<endl;
            for(int j = 0; j<=nums[i];++j)
            {
                if((i+j) >= nums.size()-1) {
                    dp[i] = true;
                    //cout<<"|A|"<<dp[i]<<endl;;
                    break;
                }else if( dp[i+j] == true ) {
                    dp[i] = true;
                    //cout<<"|B|"<<dp[i]<<endl;
                    break;
                }
            }
        }
        if(dp[0] == true) {
            return true;
        } else {
            return false;
        }
    }
};

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=922