LeetCode 1345. 跳跃游戏 IV

798236606

传送门：https://leetcode-cn.com/problems/jump-game-iv/

BFS + 哈希表剪枝

1. class Solution {
   
2. public:
   
3.     int minJumps(vector<int>& arr) {
   
4.         //这一步for循环可以不加，可以规避掉大量连续相同值造成的时间浪费
   
5.         for (int i = 1; i < arr.size() - 1; ++i)
   
6.         {
   
7.             int j  = i + 1;
   
8.             
   
9.             while (j < arr.size() && arr[j] == arr[i]) ++j;
   
10.             arr.erase(arr.begin() + i + 1, arr.begin() + j);
    
11.         }
    
12. 
    
13.         struct Node{
    
14.             int id, step;
    
15.         };        
    
16. 
    
17.         int n = arr.size();
    
18.         unordered_map<int, vector<int>> m;
    
19.         
    
20.         for (int i = 0; i < n; ++i) m[arr[i]].push_back(i);
    
21. 
    
22.         vector<bool> vis(n, false);
    
23.         queue<Node> q;
    
24.         
    
25.         q.push({0, 0});
    
26.         vis[0] = true;
    
27.         
    
28.         while (!q.empty())
    
29.         {
    
30.             Node now = q.front();
    
31.             q.pop();
    
32.             
    
33.             if (now.id == arr.size() - 1) return now.step;
    
34.             
    
35.             if (!vis[now.id + 1])
    
36.             {
    
37.                 q.push({now.id + 1, now.step + 1});
    
38.                 vis[now.id + 1] = true;
    
39.             }
    
40.             
    
41.             if (now.id > 0 && !vis[now.id - 1])
    
42.             {
    
43.                 q.push({now.id - 1, now.step + 1});
    
44.                 vis[now.id - 1] = true;
    
45.             }
    
46. 
    
47.             if (m.find(arr[now.id]) != m.end())
    
48.             {
    
49.                 for (int i: m[arr[now.id]])
    
50.                 {
    
51.                     if (!vis[i])
    
52.                     {
    
53.                         q.push({i, now.step + 1});
    
54.                         vis[i] = true;
    
55.                     }                    
    
56.                 }
    
57. 
    
58.                 m.erase(m.find(arr[now.id]));//找到一个相同值，则所有同值的位置都不可再通过同值的规则跳            
    
59.             }
    
60.         }
    
61.         
    
62.         return -1;//若未找到路径，返回-1
    
63.     }
    
64. };

复制代码