1345. Jump Game IV

题目信息

题号:

1345

难度:

Hard

主题:

数组、广度优先搜索、同值跳跃

原题:

LeetCode 1345

重点:

从下标 i 可跳到相邻下标或任意具有相同数值的下标;求从 0 到 n-1 的最少跳跃次数

题目重述

给定整数数组 arr。当前位于下标 i 时,一步可以到达 i-1、i+1,或任意满足 arr[j] == arr[i] 且 j != i 的下标 j,目标必须合法。

从下标 0 出发,请返回到达最后一个下标所需的最少步数。

1 <= arr.length <= 5 * 10^4,-10^8 <= arr[i] <= 10^8。

自建示例

相同数值可以直接跨越多个位置:

输入:arr = [5,1,5,2,5]
输出:1
解释:下标 0 与最后下标的值都为 5,可以一步直接跳到下标 4。

只有一个元素时已经到达终点:

输入:arr = [9]
输出:0
解释:起点和终点是同一个下标。