leetcode
leetcode 1651 ~ 1700
跳跃游戏 VII

跳跃游戏 VII

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.3 MB


// Java Stream Solution

// 思路:
// 使用Java Stream来优化代码,这次我们使用IntStream来处理范围的遍历。
// 使用IntStream来生成索引范围,并使用filter来筛选符合条件的索引。

import java.util.*;
import java.util.stream.IntStream;

public class SolutionStream {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int furthest = 0;
        while (!queue.isEmpty()) {
            int i = queue.poll();
            int currentFurthest = furthest;
            furthest = Math.min(i + maxJump, n - 1);
            boolean found = IntStream.rangeClosed(Math.max(i + minJump, currentFurthest + 1), furthest)
                .filter(j -> s.charAt(j) == '0')
                .peek(j -> {
                    if (j == n - 1) {
                        throw new RuntimeException("found");
                    }
                })
                .mapToObj(j -> j)
                .peek(queue::offer)
                .findAny()
                .isPresent();
            if (found) return true;
        }
        return false;
    }
}

解释

方法:

该题解采用了动态规划的方法,其中dp数组用于记录从起点至每个位置是否可达。dp[i]为True表示可以到达位置i,初始状态是dp[0]为True(起点),其余为False。接着,使用变量count来记录在当前位置i可达时,有效的可以作为跳跃起点的位置的数目。当遍历到某个位置i时,如果该位置为'0'且count大于0,说明存在至少一个位置j(j < i)使得从j跳到i是可行的,因此将dp[i]设置为True。在遍历的过程中,如果i超过了maxJump,需要从count中减去不再在范围内的dp[i-maxJump],同时,每当向前移动一个位置,就需要检查是否有新的位置成为有效的起跳点,并更新count。通过这种方式,可以有效地更新dp数组,最终dp[n-1]的值即为结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在动态规划解法中,如何确定`count`变量的初始值,并确保它能正确地表示初始可达起点的数量?
在此题解中,`count`变量用于记录在当前遍历的位置`i`时,位于`[i-maxJump, i-minJump]`区间内的可达起点数量。由于起始位置0是确定可达的(`dp[0]`为True),所以`count`的初始值设为1。这表示在开始时,有一个确定的起跳点(即位置0),后续的遍历会根据`dp`数组的更新来调整`count`的值,确保其反映当前可用的起跳点数量。
🦆
为什么在遍历时从`minJump`开始,而不是从1或0开始?
由于玩家从位置0出发,并且每次跳跃至少需要`minJump`的距离,因此从位置0到`minJump-1`的距离内是无法直接到达的,没有必要检查这部分位置。因此,直接从`minJump`开始遍历,可以减少不必要的计算,并且遍历的起始点是根据题目给定的最小跳跃距离确定的。
🦆
在更新`dp[i]`的条件中,`count`必须大于0的原因是什么?
`count`表示当前位置`i`前可以作为起跳点的位置数量,如果`count`大于0,意味着至少有一个位置(在`[i-maxJump, i-minJump]`范围内)是可达的,并且可以从那里跳到当前位置`i`(假设`s[i]`为'0'),这使得当前位置也变为可达。如果`count`为0,则表示没有可用的起跳点到达当前位置,当前位置`i`不可达。因此,`count > 0`是`dp[i] = True`的必要条件。

相关问题