leetcode-55-跳跃游戏

题目描述：

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]

输出: true

解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]

输出: false

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

要完成的函数：

bool canJump(vector<int>& nums)

说明：

1、给定一个vector，里面存放着非负的int型整数，每一个整数代表在这个位置上可以跳跃的步数，要求判断最终能不能跳跃到vector的最后一位。

可以的话返回true，不行就返回false。

2、这道题其实写个递归就可以解决了，但是递归太耗费时间了，不断地试探。所以我们换个思路~

这道题保证了vector只会有正数和0，所以我们可以直接找到0的位置，判断0左边的元素能不能跳跃过0这个点。这样子比较快。

代码如下：（附详解）

    bool canJump(vector<int>& nums)

    {

        int i=0,j,t;

        bool flag;

        while(i<nums.size()-1)//一直找，找到0的位置，记录在i中

        {

            if(nums[i]==0)//找到了i这一位为0

            {

                j=i-1;//设置j为i的前一位

                while(j>=0)//一直找，找到能够跨越过i这一位的点，记为j

                {

                    if(nums[j]>(i-j))//可以跨过，但是要分多种情况

                    {

                        if(j+nums[j]>=nums.size()-1)//如果跨过了nums的长度或者直接到最后一位

                            return true;

                        else//如果还是在nums的长度范围里面，那我们修改i的值，继续找下一个0

                        {//修改i值为离j+nums[j]左边最近的非零值的索引，而不是j+nums[j]本身，

                            t=j+nums[j];

                            flag=false;

                            while(i<t)

                            {

                                if(nums[t]!=0)

                                {

                                    i=t;

                                    flag=true;

                                    break;

                                }

                                t--;

                            }

                            if(flag==true)

                                break;

                        }

                    }

                    j--;

                }

                if(j==-1)//一直找，都找不到可以跨越过当前i这一点的，那么返回false

                    return false;

            }

            i++;//i一直加

        }

        return true;//最终可以跑出循环，那么肯定是达到了最后一位，返回true

    }

上述代码中的修改 i 值部分，可能有的同学想直接把 i 修改为 j+nums[j]，比如[2,3,0,1,1,1]，步数是3，直接跨越到第二个1，可以更快地迭代。

但是如果是[2,3,0,2,0,1]，在3这个点跨越到最后一个0，我们并不想跨越到0，我们想跨越到非零值，从而可以不用再考虑前面的点。

所以这个地方我们要修改一下，跨越到离 j+nums[j] 左边最近的非零值，所以代码如上~

上述代码的整体思路是，先找到第一个零值记为a，接着找到这个零值左边的，可以跨越过这个零值，到达一个非零值c的点b。

如果没找到这个符合条件的点b，那就一直往前找，直到索引为-1，表示左边的所有数都不满足，此时返回false。

找到符合条件的点b之后，跨越到非零值点c，接着在非零值c的右边继续找下一个零值……

不断地重复这个操作，直到跨越到最后一个点或者直接超出vector的范围。

上述代码实测8ms，beats 98.00% of cpp submissions。

巴特西

leetcode-55-跳跃游戏

题目描述：

要完成的函数：

说明：

最新文章

热门文章