欢迎访问==> 【考研OR保研】机试题
给你一个整数数组 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
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意:任何时候你都不能跳到数组外面。
示例 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[i] <= 10^8
C++代码
/*
使用BFS即可
需要优化的是【跳到j】这一步, 每次访问完一个坐标点之后,后面一定不会被访问,
如果后面再次访问了这个坐标,则后访问的步数一定大于先访问的步数
*/
class Solution {
public:
bool st[50010] = {false};
int d[50010] = {0};
unordered_map<int, vector<int> > h;
int minJumps(vector<int>& arr) {
int n = arr.size();
queue<int> q;
q.push(0);
st[0] = true;
//记录值为arr[i]的所有下标点
for(int i = 0; i < n; i ++) h[arr[i]].push_back(i);
while(q.size())
{
int t = q.front();
q.pop();
if(t == n - 1) return d[t];
//加1
if(t + 1 < n && !st[t + 1])
{
st[t + 1] = true;
q.push(t + 1);
d[t + 1] = d[t] + 1;
}
//减1
if(t - 1 >= 0 && !st[t - 1])
{
st[t - 1] = true;
q.push(t - 1);
d[t - 1] = d[t] + 1;
}
//跳到j
for(int i = h[arr[t]].size() - 1; i >= 0; i --)
{
int j = h[arr[t]][i];
if(j != t && !st[j])
{
st[j] = true;
q.push(j);
d[j] = d[t] + 1;
h[arr[t]].pop_back(); //访问之后删除掉,防止重复访问浪费时间
}
}
}
return d[n - 1];
}
};