1345. 跳跃游戏 IV
摘要
Title: 1345. 跳跃游戏 IV
Tag: 哈希、BFS
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1345. 跳跃游戏 IV
-
题意
略
-
思路
先用哈希表将每个相同元素的位置记下来，每个形成一个链表，再进行BFS，入队的话，就让前一个、后一个、链表的元素入队即可
其中减少复杂度的操作，就是当遍历完自己的链表后，将其从哈希表中删去，因为再遍历肯定是不优的 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/*
* @Author: NEFU AB-IN
* @Date: 2022-09-05 21:10:01
* @FilePath: \LeetCode\1345\1345.cpp
* @LastEditTime: 2022-09-06 14:06:02
*/
using namespace std;
// ---------------------
typedef pair<int, int> PII;
// #undef N
// const int N = 1e5 + 10;
// #undef int;
static int IOS = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
int minJumps(vector<int> &arr)
{
int n = SZ(arr);
queue<PII> q;
unordered_map<int, vector<int>> g;
for (int i = 0; i < n; ++i)
{
g[arr[i]].push_back(i);
}
vector<int> st(n);
st[0] = 1;
q.push({0, 0});
while (SZ(q))
{
auto t = q.front();
q.pop();
int id = t.first, cnt = t.second;
if (id == n - 1)
{
return cnt;
}
if (g.count(arr[id]))
{
for (auto v : g[arr[id]])
{
if (!st[v])
q.push({v, cnt + 1}), st[v] = 1;
}
g.erase(arr[id]); // 遍历完一遍了，直接就可以删掉了
}
if (id >= 1 && !st[id - 1])
q.push({id - 1, cnt + 1}), st[id - 1] = 1;
if (id <= n - 1 && !st[id + 1])
q.push({id + 1, cnt + 1}), st[id + 1] = 1;
}
return 0;
}
};
// ---------------------
signed main()
{
Solution solution;
return 0;
}