---
# System prepended metadata

title: 1871. Jump Game VII
tags: [Leetcode, Line Sweep, Medium]

---

# 1871. Jump Game VII
###### tags: `Leetcode` `Medium` `Line Sweep`
Link: https://leetcode.com/problems/jump-game-vii/
## 思路
思路[参考](https://github.com/wisdompeak/LeetCode/tree/master/Others/1871.Jump-Game-VII)
从头开始遍历，如果这个点i能到达，说明[i+minJump, i+maxJump]都能到达
因为[i+minJump, i+maxJump]是一个array，所以可以用差分法，头+1， 尾-1，就能知道中间每个位置能否到达
## Code
```java=
class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        if(s.charAt(s.length()-1)!='0') return false;
        int[] diff = new int[s.length()+1];
        diff[minJump]++;
        diff[maxJump+1]--;
        int cnt = 0;
        for(int i=1; i<s.length(); i++){
            cnt += diff[i];
            if(cnt>0 && s.charAt(i)=='0'){
                if(i+minJump<s.length()) diff[i+minJump]++;
                if(i+maxJump+1<s.length()) diff[i+maxJump+1]--;
            }
        }
        return cnt>0;
    }
}
```