|
6 | 6 | import java.util.Map;
|
7 | 7 | import java.util.Queue;
|
8 | 8 |
|
9 |
| -/** |
10 |
| - * 1345. Jump Game IV |
11 |
| - * |
12 |
| - * Given an array of integers arr, you are initially positioned at the first index of the array. |
13 |
| - * In one step you can jump from index i to index: |
14 |
| - * i + 1 where: i + 1 < arr.length. |
15 |
| - * i - 1 where: i - 1 >= 0. |
16 |
| - * j where: arr[i] == arr[j] and i != j. |
17 |
| - * Return the minimum number of steps to reach the last index of the array. |
18 |
| - * Notice that you can not jump outside of the array at any time. |
19 |
| - * |
20 |
| - * Example 1: |
21 |
| - * Input: arr = [100,-23,-23,404,100,23,23,23,3,404] |
22 |
| - * Output: 3 |
23 |
| - * Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array. |
24 |
| - * |
25 |
| - * Example 2: |
26 |
| - * Input: arr = [7] |
27 |
| - * Output: 0 |
28 |
| - * Explanation: Start index is the last index. You don't need to jump. |
29 |
| - * |
30 |
| - * Example 3: |
31 |
| - * Input: arr = [7,6,9,6,9,6,9,7] |
32 |
| - * Output: 1 |
33 |
| - * Explanation: You can jump directly from index 0 to index 7 which is last index of the array. |
34 |
| - * |
35 |
| - * Example 4: |
36 |
| - * Input: arr = [6,1,9] |
37 |
| - * Output: 2 |
38 |
| - * |
39 |
| - * Example 5: |
40 |
| - * Input: arr = [11,22,7,7,7,7,7,7,7,22,13] |
41 |
| - * Output: 3 |
42 |
| - * |
43 |
| - * Constraints: |
44 |
| - * 1 <= arr.length <= 5 * 10^4 |
45 |
| - * -10^8 <= arr[i] <= 10^8 |
46 |
| - * */ |
47 | 9 | public class _1345 {
|
48 | 10 | public static class Solution1 {
|
49 |
| - /**credit: https://leetcode.com/problems/jump-game-iv/discuss/502699/JavaC%2B%2B-BFS-Solution-Clean-code-O(N)*/ |
| 11 | + /** |
| 12 | + * credit: https://leetcode.com/problems/jump-game-iv/discuss/502699/JavaC%2B%2B-BFS-Solution-Clean-code-O(N) |
| 13 | + */ |
50 | 14 | public int minJumps(int[] arr) {
|
51 | 15 | Map<Integer, List<Integer>> valueToIndices = new HashMap<>();
|
52 | 16 | for (int i = 0; i < arr.length; i++) {
|
|
0 commit comments