IVN
0%

JumpGame

Posted on Edited on In
Symbols count in article: 7.2k Reading time ≈ 7 mins.

Jump Game全家福

1340. Jump Game V

dfs + memo

注意逻辑：

  • 一旦出现跳不到的值，则break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int[] dp;
public int maxJumps(int[] arr, int d) {
    int n=arr.length;
    dp=new int[n];
    int max=0;
    for (int i = 0; i < n; i++) {
        max=Math.max(max,dfs(arr,i,d));
    }
    return max;
}

int dfs(int[] arr, int cur, int d){
    if(dp[cur]!=0){
        return dp[cur];
    }
    int res=1;
    //jump right
    for(int j=cur+1; j<=Math.min(cur+d,arr.length-1) && arr[j]<arr[cur]; j++){
        res=Math.max(res,1+dfs(arr,j,d));
    }
    //jump left
    for(int j=cur-1; j>=Math.max(cur-d,0) && arr[j]<arr[cur]; j--){
        res=Math.max(res,1+dfs(arr,j,d));
    }
    return dp[cur]=res;
}

55. Jump Game

思路：

  • lastGoodIndex, 倒叙考察
1
2
3
4
5
6
7
8
9
public boolean canJump(int[] nums) {
    int lastGood=nums.length-1;
    for (int i = nums.length - 1; i >= 0; i--) {
        if(i+nums[i]>=lastGood){
            lastGood=i;
        }
    }
    return lastGood==0;
}

45. Jump Game II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int jump(int[] nums) {
    // The starting range of the first jump is [0, 0]
    int answer = 0, n = nums.length;
    int curEnd = 0, curFar = 0;
    
    for (int i = 0; i < n - 1; ++i) {
        // Update the farthest reachable index of this jump.
        curFar = Math.max(curFar, i + nums[i]);

        // If we finish the starting range of this jump,
        // Move on to the starting range of the next jump.
        if (i == curEnd) {
            answer++;
            curEnd = curFar;
        }
    }
    
    return answer;
}

1306. Jump Game III

dfs也可以用visited[]去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean[] visited;
public boolean canReach(int[] arr, int start) {
    visited=new boolean[arr.length];
    return dfs(arr,start);
}

boolean dfs(int[] arr, int cur){
    if(cur<0 || cur>=arr.length || visited[cur]){
        return false;
    }
    visited[cur]=true;
    boolean res=arr[cur]==0 || dfs(arr,cur+arr[cur]) || dfs(arr,cur-arr[cur]);
    return res;
}

1345. Jump Game IV

TLE: 26 / 33 test cases passed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public int minJumps(int[] arr) {
    int n=arr.length;
    Map<Integer, List<Integer>> map=new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.putIfAbsent(arr[i],new ArrayList<>());
        map.get(arr[i]).add(i);
    }
    int d=0;
    boolean[] visited=new boolean[n];
    Deque<Integer> q=new LinkedList<>();
    q.offer(0);
    visited[0]=true;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int cur=q.poll();
            if(cur==n-1){
                return d;
            }
            if(cur-1>=0 && !visited[cur-1]){
                q.offer(cur-1);
                visited[cur-1]=true;
            }
            if(cur+1<n && !visited[cur+1]){
                q.offer(cur+1);
                visited[cur+1]=true;
            }
            for (Integer next : map.get(arr[cur])) {
                if(!visited[next]){
                    q.offer(next);
                    visited[next]=true;
                }
            }
        }
        d++;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public int minJumps(int[] arr) {
    int n=arr.length;
    Map<Integer, List<Integer>> map=new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.putIfAbsent(arr[i],new ArrayList<>());
        map.get(arr[i]).add(i);
    }
    int d=0;
    boolean[] visited=new boolean[n];
    Deque<Integer> q=new LinkedList<>();
    q.offer(0);
    visited[0]=true;
    while(!q.isEmpty()){
        int size=q.size();
        while(size-->0){
            int cur=q.poll();
            if(cur==n-1){
                return d;
            }
            if(cur-1>=0 && !visited[cur-1]){
                q.offer(cur-1);
                visited[cur-1]=true;
            }
            if(cur+1<n && !visited[cur+1]){
                q.offer(cur+1);
                visited[cur+1]=true;
            }
            for (Integer next : map.get(arr[cur])) {
                if(!visited[next]){
                    q.offer(next);
                    visited[next]=true;
                }
            }
            //one small step makes a huge difference
            map.get(arr[cur]).clear();
        }
        d++;
    }
    return -1;
}

1696. Jump Game VI

TLE: 60 / 72 test cases passed.

1
2
3
4
5
6
7
8
9
10
11
12
public int maxResult(int[] nums, int k) {
    int n=nums.length;
    int[] dp=new int[n]; //maximum score when arriving i
    Arrays.fill(dp,Integer.MIN_VALUE);
    dp[0]=nums[0];
    for (int i = 0; i < n; i++) {
        for(int j=i+1; j<n && j<=i+k; j++){
            dp[j]=Math.max(dp[j],dp[i]+nums[j]);
        }
    }
    return dp[n-1];
}

Priority Queue Approcah:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxResult(int[] nums, int k) {
    int n=nums.length;
    int[] dp=new int[n]; //maximum score when arriving i
    Arrays.fill(dp,Integer.MIN_VALUE);
    dp[0]=nums[0];
    PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->(dp[b]-dp[a]));
    pq.offer(0);
    for (int i = 1; i < n; i++) {
        while(pq.peek()+k<i){
            pq.poll();
        }
        dp[i]=nums[i]+dp[pq.peek()];
        pq.offer(i);
    }
    return dp[n-1];
}

https://leetcode.com/problems/jump-game-vi/discuss/1260843/C%2B%2BJavaPython-DP-and-Decreasing-Deque-Clean-and-Concise-Time-O(N)-Space-O(K)

In Decreasing Deque approach:

  • We used a deque to store indices of nums elements, elements is in decreasing order, the front is the maximum element.
  • When adding a new number nums[i], we eliminate elements which is less or equal to nums[i] in deque, which will never be chosen in the future.
  • Push index of current nums[i] to back of the deque.
  • If the last element in deque is out of range K then remove it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxResult(int[] nums, int k) {
    int n=nums.length;
    int[] dp=new int[n];
    Deque<Integer> q=new LinkedList<>();
    q.offerLast(0);
    dp[0]=nums[0];
    for (int i = 1; i < n; i++) {
        while(q.peekFirst()+k<i){
            q.pollFirst();
        }
        dp[i]=nums[i]+dp[q.peekFirst()];
        while(!q.isEmpty() && dp[q.peekLast()]<=dp[i]){
            //older and lesser -> inferior, won't be used in future
            q.pollLast();
        }
        q.offerLast(i);
    }
    return dp[n-1];
}

1871. Jump Game VII

经典O(n^2)超时的”10^5”

107 / 142 test cases passed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean canReach(String s, int minJump, int maxJump) {
    char[] chars=s.toCharArray();
    int n=s.length();
    if(chars[n-1]=='1'){
        return false;
    }
    Deque<Integer> q=new LinkedList<>();
    q.offer(0);
    boolean[] visited=new boolean[n];
    visited[0]=true;
    while(!q.isEmpty()){
        int cur=q.poll();
        if(cur==n-1){
            return true;
        }
        for(int i=cur+minJump; i<=cur+maxJump && i<n; i++){
            if(!visited[i] && chars[i]=='0'){
                visited[i]=true;
                q.offer(i);
            }
        }
    }
    return false;
}

(hint: Use partial sums to mark the intervals as reachable.)

https://leetcode.com/problems/jump-game-vii/discuss/1224804/JavaC%2B%2BPython-One-Pass-DP

dp + sliding window 太妙了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean canReach(String s, int minJump, int maxJump) {
    //i: [i-maxJump,i-minJump]
    //i-1: [i-maxJump-1, i-minJump-1]
    //from i-1 to i: increase i-minJump, decrease i-maxJump-1
    int n=s.length();
    char[] chars=s.toCharArray();
    boolean[] dp=new boolean[n];
    int pre=0;
    dp[0]=true;
    for (int i = 1; i < n; i++) {
        if(i-minJump>=0 && dp[i-minJump]){
            pre++;
        }
        if(i-maxJump-1>=0 && dp[i-maxJump-1]){
            pre--;
        }
        dp[i]= pre>0 && chars[i]=='0';
    }
    return dp[n-1];
}

2297. Jump Game VIII

反思：

  • 当给定条件看似杂乱时，尝试通过反证法等数学推理转化条件为基本模板

https://leetcode.com/problems/jump-game-viii/discuss/2140361/Java-or-Monostack-%2B-DP-or-Concise-and-Short-or-Explained

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public long minCost(int[] nums, int[] costs) {
    int n= nums.length;
    long[] dp=new long[n];
    Arrays.fill(dp,Long.MAX_VALUE);
    dp[0]=0;
    Deque<Integer> stack1=new LinkedList<>();
    Deque<Integer> stack2=new LinkedList<>();
    for (int i = 0; i < n; i++) {
        while(!stack1.isEmpty() && nums[stack1.peek()]<=nums[i]){
            dp[i]=Math.min(dp[i],dp[stack1.pop()]+costs[i]);
        }
        while(!stack2.isEmpty() && nums[stack2.peek()]>nums[i]){
            dp[i]=Math.min(dp[i],dp[stack2.pop()]+costs[i]);
        }
        stack1.push(i);
        stack2.push(i);
    }
    return dp[n-1];
}