跳跃游戏 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`变量的初始值,并确保它能正确地表示初始可达起点的数量?
▷🦆
为什么在遍历时从`minJump`开始,而不是从1或0开始?
▷🦆
在更新`dp[i]`的条件中,`count`必须大于0的原因是什么?
▷