论坛 › C\C++交流 › LeetCode 1345. 跳跃游戏 IV

798236606 发表于 2020-3-3 16:46:13

LeetCode 1345. 跳跃游戏 IV

本帖最后由 798236606 于 2020-3-5 10:12 编辑

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

BFS + 哈希表剪枝
class Solution {
public:
    int minJumps(vector<int>& arr) {
      //这一步for循环可以不加，可以规避掉大量连续相同值造成的时间浪费
      for (int i = 1; i < arr.size() - 1; ++i)
      {
            int j= i + 1;
            
            while (j < arr.size() && arr == arr) ++j;
            arr.erase(arr.begin() + i + 1, arr.begin() + j);
      }

      struct Node{
            int id, step;
      };      

      int n = arr.size();
      unordered_map<int, vector<int>> m;
      
      for (int i = 0; i < n; ++i) m].push_back(i);

      vector<bool> vis(n, false);
      queue<Node> q;
      
      q.push({0, 0});
      vis = true;
      
      while (!q.empty())
      {
            Node now = q.front();
            q.pop();
            
            if (now.id == arr.size() - 1) return now.step;
            
            if (!vis)
            {
                q.push({now.id + 1, now.step + 1});
                vis = true;
            }
            
            if (now.id > 0 && !vis)
            {
                q.push({now.id - 1, now.step + 1});
                vis = true;
            }

            if (m.find(arr) != m.end())
            {
                for (int i: m])
                {
                  if (!vis)
                  {
                        q.push({i, now.step + 1});
                        vis = true;
                  }                  
                }

                m.erase(m.find(arr));//找到一个相同值，则所有同值的位置都不可再通过同值的规则跳            
            }
      }
      
      return -1;//若未找到路径，返回-1
    }
};

查看完整版本: LeetCode 1345. 跳跃游戏 IV