目录
题目描述：
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
样例：
错误解法（无优化的单向bfs）：
class Solution {
public:
int minJumps(vector<int>& arr) {
int n = arr.size();
if (n == 1) return 0;
unordered_map<int, vector<int>> maps;
for (int i = 0; i < n; i++)
{
maps[arr[i]].push_back(i);
}
set<int> sets;
sets.insert(0);
queue<int> que;
que.push(0);
int ans = 0;
while (!que.empty())
{
int l = que.size();
for (int i = 0; i < l; i++)
{
int cur = que.front();
que.pop();
int next;
if (cur + 1 < n && !sets.count(cur + 1))
{
next = cur + 1;
if (next == n - 1) return ans + 1;
sets.insert(next);
que.push(next);
}
if (cur - 1 >= 0 && !sets.count(cur - 1))
{
next = cur - 1;
sets.insert(next);
que.push(next);
}
for (int j = 0; j < maps[arr[cur]].size(); j++)
{
next = maps[arr[cur]][j];
if (next == n - 1) return ans + 1;
if (!sets.count(next))
{
sets.insert(next);
que.push(next);
}
}
}
ans++;
}
return ans;
}
};一开始用的方法，看到数量级是4 ，以为直接用单向的bfs不会超时，但是对于以下这段代码：
for (int j = 0; j < maps[arr[cur]].size(); j++)
{
next = maps[arr[cur]][j];
if (next == n - 1) return ans + 1;
if (!sets.count(next))
{
sets.insert(next);
que.push(next);
}
}如果存在着大量值相等的元素，那么每次碰到这样一个元素都需要进行一次遍历，将会耗费大量的 时间，所以会超时。
方法一（双向bfs）：
class Solution {
public:
unordered_map<int, vector<int>> maps;
int n;
vector<int> arr;
int bfs(queue<int>& que, unordered_map<int, int>& curmap, unordered_map<int, int>& othermap)
{
int l = que.size();
for (int i = 0; i < l; i++)
{
int cur = que.front();
que.pop();
int next;
if (cur + 1 < n && !curmap.count(cur + 1))
{
next = cur + 1;
if (othermap.count(next)) return curmap[cur] + 1 + othermap[next];
curmap[next] = curmap[cur] + 1;
que.push(next);
}
if (cur - 1 >= 0 && !curmap.count(cur - 1))
{
next = cur - 1;
if (othermap.count(next)) return curmap[cur] + 1 + othermap[next];
curmap[next] = curmap[cur] + 1;
que.push(next);
}
for (int j = 0; j < maps[arr[cur]].size(); j++)
{
next = maps[arr[cur]][j];
if (othermap.count(next)) return curmap[cur] + 1 + othermap[next];
if (!curmap.count(next))
{
curmap[next] = curmap[cur] + 1;
que.push(next);
}
}
}
return -1;
}
int minJumps(vector<int>& arr) {
n = arr.size();
if (n == 1) return 0;
for (int i = 0; i < n; i++)
{
maps[arr[i]].push_back(i);
}
this->arr = arr;
unordered_map<int, int> startmap, targetmap;
startmap[0] = 0;
targetmap[n - 1] = 0;
queue<int> startque, targetque;
startque.push(0);
targetque.push(n - 1);
int ans = 0;
while (!startque.empty() && !targetque.empty())
{
if (startque.size() <= targetque.size())
{
ans = bfs(startque, startmap, targetmap);
if (ans != -1) return ans;
}
else
{
ans = bfs(targetque, targetmap, startmap);
if (ans != -1) return ans;
}
}
return ans;
}
};在单向bfs超时后，我还并未意识到是什么导致了超时，于是就自然用上了双向的bfs，勉强过了。
方法二（单向bfs+简单优化）：
class Solution {
public:
int minJumps(vector<int>& arr) {
int n = arr.size();
if (n == 1) return 0;
unordered_map<int, vector<int>> maps;
unordered_map<int, bool> visit; //判断某一个值是否有访问过
for (int i = 0; i < n; i++)
{
maps[arr[i]].push_back(i);
visit[arr[i]] = false;
}
set<int> sets;
sets.insert(0);
queue<int> que;
que.push(0);
int ans = 0;
while (!que.empty())
{
int l = que.size();
for (int i = 0; i < l; i++)
{
int cur = que.front();
que.pop();
int next;
if (cur + 1 < n && !sets.count(cur + 1))
{
next = cur + 1;
if (next == n - 1) return ans + 1;
sets.insert(next);
que.push(next);
}
if (cur - 1 >= 0 && !sets.count(cur - 1))
{
next = cur - 1;
sets.insert(next);
que.push(next);
}
//同一个值只要访问一次就够了
if (visit[arr[cur]])
{
continue;
}
for (int j = 0; j < maps[arr[cur]].size(); j++)
{
visit[arr[cur]] = true;
next = maps[arr[cur]][j];
if (next == n - 1) return ans + 1;
if (!sets.count(next))
{
sets.insert(next);
que.push(next);
}
}
}
ans++;
}
return ans;
}
};其实对单向bfs的改动很简单，因为某个值只需要访问一次就能够将所有值相等的元素都加入队列了，所以只要加一个避免多次访问同一个值的功能即可，这里使用了哈希。
版权声明：本文为weixin_52629904原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。