1345 Jump Game IV 跳跃游戏 IV
Description:
Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:
i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr == arr[j] and i != j.
Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
Example:
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
Example 2:
Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You do not need to jump.
Example 3:
Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
Constraints:
1 <= arr.length <= 5 * 10^4
-10^8 <= arr <= 10^8
标题形貌：
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 大概 j ：
i + 1 需满意：i + 1 < arr.length
i - 1 需满意：i - 1 >= 0
j 需满意：arr == arr[j] 且 i != j
请你返回到达数组末了一个元素的下标地方需的 最少利用次数 。
注意：任何时间你都不能跳到数组外面。
Constraints:
示例 1：
输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
表明：那你必要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的末了一个元素的下标。
示例 2：
输入：arr = [7]
输出：0
表明：一开始就在末了一个元素处，以是你不必要跳跃。
示例 3：
输入：arr = [7,6,9,6,9,6,9,7]
输出：1
表明：你可以直接从下标 0 处跳到下标 7 处，也就是数组的末了一个元素处。
提示：
1 <= arr.length <= 5 * 10^4
-10^8 <= arr <= 10^8
思绪：
BFS
将雷同值对应的下标到场哈希表, 一连多个雷同值可以跳过, 由于肯定用不上
将当前下标以及步数到场队列中, 遍历哈希表中的值, 这些值都可以一次到达
然后到场前一个下标和后一个下标
并用 visited 数组纪录访问过的下标
时间复杂度为 O(n), 空间复杂度为 O(n)
代码:
C++: |
