1345. Jump Game IV¶
题目信息¶
- 题号:
1345
- 难度:
Hard
- 主题:
数组、广度优先搜索、同值跳跃
- 原题:
- 重点:
从下标
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
解释:起点和终点是同一个下标。