给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：
i + 1 需满足：i + 1 < arr.length，
i - 1 需满足：i - 1 >= 0，
j 需满足：arr[i] == arr[j] 且 i != j。
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
存在左跳的可能。宽度优先遍历，层次遍历。
代码用rust编写。代码如下：
use std::collections::HashMap;
fn main() {
let mut arr: Vec<i32> = vec![100, -23, -23, 404, 100, 23, 23, 23, 3, 404];
let ans = min_jumps(&mut arr);
println!("ans = {}", ans);
}
fn min_jumps(arr: &mut Vec<i32>) -> i32 {
let n = arr.len() as i32;
// 为了找某个值，有哪些位置，能快一些
// key : 某个值9，
// value : 列表：0，7，19
let mut value_index: HashMap<i32, Vec<i32>> = HashMap::new();
for i in 0..n {
if !value_index.contains_key(&arr[i as usize]) {
value_index.insert(arr[i as usize], vec![]);
}
value_index.get_mut(&arr[i as usize]).unwrap().push(i);
}
// i会有哪些展开：左，右，i通过自己的值，能蹦到哪些位置上去
// 宽度优先遍历，遍历过的位置，不希望重复处理
// visited[i] == false：i位置，之前没来过，可以处理
// visited[i] == true : i位置，之前来过，可以跳过
let mut visited: Vec<bool> = vec![];
for _ in 0..n {
visited.push(false);
}
let mut queue: Vec<i32> = vec![];
for _ in 0..n {
queue.push(0);
}
let mut l: i32 = 0;
let mut r: i32 = 0;
// 0位置加到队列里去
queue[r as usize] = 0;
r += 1;
visited[0] = true;
let mut jump = 0;
// 宽度优先遍历
// 一次，遍历一整层！
// 该技巧，多次出现！
while l != r {
// 队列里还有东西的意思！
// 此时的r记录！
// 0 1 2 | 3 4 5 6 7 8
// 当前层的终止位置
let tmp = r;
while l < tmp {
// 遍历当前层！
let cur = queue[l as usize];
if cur == n - 1 {
return jump;
}
if cur + 1 < n && !visited[(cur + 1) as usize] {
visited[(cur + 1) as usize] = true;
queue[r as usize] = cur + 1;
r += 1;
}
// cur > 0 cur - 1 >=0
if cur > 0 && !visited[(cur - 1) as usize] {
visited[(cur - 1) as usize] = true;
queue[r as usize] = cur - 1;
r += 1;
}
// i -> 9
// 值同样为9的那些位置，也能去
for next in value_index.get(&arr[cur as usize]).unwrap().iter() {
if !visited[*next as usize] {
visited[*next as usize] = true;
queue[r as usize] = *next;
r += 1;
}
}
// 重要优化！
value_index.insert(arr[cur as usize], vec![]);
l += 1;
}
jump += 1;
}
return -1;
}执行结果如下：
