|
6 | 6 | importjava.util.Map; |
7 | 7 | importjava.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 | publicclass_1345 { |
48 | 10 | publicstaticclassSolution1 { |
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 | publicintminJumps(int[]arr) { |
51 | 15 | Map<Integer,List<Integer>>valueToIndices =newHashMap<>(); |
52 | 16 | for (inti =0;i <arr.length;i++) { |
|