跳跃游戏VII | Java刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目描述：

二、思路分析：

今天给大家分享的是一道本周力扣的周赛题目，题目是跳跃游戏(竟然这个系列都跳到第7部了，nb)。回到题目，题目现在给你一个字符串S,两个整数，一开始你位于字符串S索引0处，然后你可以进行跳跃，每次跳跃的条件是[i + minJump, min(len_s – 1, i + maxJump)] && s[j] == 0;然后让我们求能不能到达索引 len_s -1 处。
说实话，刚看到题目的时候，我寻思着可能是动态规划解法啊，不过搞了半天没啥思路。然后想了一会，突然发现，我直接枚举每个可以跳跃到的位置，看看能不能到达len_s – 1 的位置不就行了。搞个队列存起来，这不就是标准的BFS吗？开搞！

BFS 直接搞

先把位置0放入队列。
挨个取出队列中的元素，根据可跳跃的区间枚举下一步的位置$i = $top + $minJump; $i <= min($len_s - 1, $top + $maxJump)，如果下一个位置是0的话，表示可以从当前位置跳跃过去，直接入队列即可。
最后在把元素出队的时候判断一下当前位置是否是 len_s – 1 的位置即可。
如果循环结束还没找到，那么表示无法到达，返回false即可。
啪的一下，提交，直接超时。

想了一下，有些重复的位置可能存在重复遍历的情况，所以使用一个used数组保存已经遍历过的位置，提交，还是没通过.,……….

BFS && 剪枝

没办法，一直感觉BFS是比较好理解的思路，赛后翻了一下评论区，看到一个也是BFS的解法，思路差不多，不过他是用了一个last变量来做剪枝操作。

使用一个last变量表示上次遍历到的位置，每次要枚举下一个跳跃到的位置时选择的起始位置从max($last + 1, $top + $minJump)开始遍历，结束位置还是min($len_s - 1, $top + $maxJump)，然后需要注意的就是每次进入循环是的时候要先把last = i;不然也会超时。就很神奇的通过啦~~~~~

三、AC 代码：

//无剪枝的标准BFS，超时哦
class Solution {

    /**
     * @param String $s
     * @param Integer $minJump
     * @param Integer $maxJump
     * @return Boolean
     */
    function canReach($s, $minJump, $maxJump) {
    $len_s = strlen($s);
    $dp = array_fill(0, $len_s, false);
    $dp[0] = true;
    $start = 0;
    $queue = new SplQueue();
    $queue->enqueue(0);
    while (!$queue->isEmpty()) {
        $size = count($queue);
        for ($i = 0; $i < $size; $i++) {
            $top = $queue->dequeue();
            if ($top == $len_s - 1) {
                return true;
            }
            for ($i = $top + $minJump; $i <= min($len_s - 1, $top + $maxJump); $i++) {
                if ($s[$i] == 0) {
                    $queue->enqueue($i);
                }
            }
        }
    }
    
    return false;
}
}

//BFS && 剪枝
class Solution {

    /**
     * @param String $s
     * @param Integer $minJump
     * @param Integer $maxJump
     * @return Boolean
     */
    function canReach($s, $minJump, $maxJump) {
        $len_s = strlen($s);
        if ($s[$len_s - 1] != '0') {
            return false;
        }
        $queue = new SplQueue();
        $queue->enqueue(0);
        $last = 0;
        while (!$queue->isEmpty()) {
            $top = $queue->dequeue();
            for ($i = max($last + 1, $top + $minJump); $i <= min($len_s - 1, $top + $maxJump); $i++) {
                $last = $i;
                if ($s[$i] != 0) {
                    continue;
                }
                $queue->enqueue($i);
                if ($i == $len_s - 1) {
                    return true;
                }
            }
        }

        return false;
    }
}

复制代码