Leetcode每日一题 —— 1345. 跳跃游戏 IV

开发调优
,
1

思路
还挺明显的BFS，每次尝试移到当前位置所能跳转的所有位置，并做记录以便剪枝。这样时间复杂度就是O(n)。

代码

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 2) {
            return n - 1;
        }
        // 存储相同的值(可直接跳转)
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0});
        boolean[] vis = new boolean[n];
        vis[0] = true;
        // bfs
        while (!queue.isEmpty()) {
            int[] idxStep = queue.poll();
            int idx = idxStep[0], step = idxStep[1];
            if (idx == arr.length - 1) {
                return step;
            }
            step++;
            // 直接跳转
            List<Integer> sameValue = map.remove(arr[idx]);
            if (sameValue != null) {
                for (int i : sameValue) {
                    if (!vis[i]) {
                        vis[i] = true;
                        queue.offer(new int[]{i, step});
                    }
                }
            }
            // 左移
            if (idx - 1 >= 0 && !vis[idx - 1]) {
                vis[idx - 1] = true;
                queue.offer(new int[]{idx - 1, step});
            }
            // 右移
            if (idx + 1 < arr.length && !vis[idx + 1]) {
                vis[idx + 1] = true;
                queue.offer(new int[]{idx + 1, step});
            }
        }
        return -1;
    }
}
5 个赞
2

依旧 BFS 题，每个位置可以转移到相邻位置或者和其数值相同的其他位置。

[!NOTE]
会用到哈希表存 <数值, 下标列表> 的映射。每访问一个数字，我们会扫描对应的下标列表来找转移位置。

  • 注意访问完了后就可以从哈希表中移除掉这个数字了，不然后面遇到相同数字的话，重复扫描是无意义的，且会导致 TLE。
class Solution {
public:
    int minJumps(vector<int>& arr) {
        // 可以移动到相邻元素，或者跳到数值相同的其他元素
        // 看上去依旧是 BFS
        // 额外用哈希表去维护相同数字出现的下标
        unordered_map<int,vector<int>> lMap;
        int n=arr.size();

        for(int i=0;i<n;i++){
            lMap[arr[i]].emplace_back(i);
        }

        // (下标, 操作次数) 队列
        queue<pair<int,int>> q;
        vector<bool> visited(n,false);
        q.emplace(0,0);
        while(!q.empty()){
            int idx=q.front().first;
            int numOps=q.front().second;
            q.pop();
            if(idx==n-1){
                return numOps;
            }
            if(idx>0&&!visited[idx-1]){
                visited[idx-1]=true;
                q.emplace(idx-1,numOps+1);
            }
            if(idx<n-1&&!visited[idx+1]){
                visited[idx+1]=true;
                q.emplace(idx+1,numOps+1);
            }
            if(lMap.count(arr[idx])>0){
                for(int nextIdx:lMap[arr[idx]]){
                    if(nextIdx==idx){
                        continue;
                    }
                    if(!visited[nextIdx]){
                        visited[nextIdx]=true;
                        q.emplace(nextIdx,numOps+1);
                    }
                }
                // 我们不应该每次访问到和 arr[idx] 相同的数都去扫描一次列表
                // 第一次访问到后，后面再遇到 arr[idx] 就不需要这一步了
                lMap.erase(arr[idx]);
            }
        }
        return 0;
    }
};
1 个赞
3

没想到移除，让这次第二类跳转和上次跳转对应的值不一样。有点启发式，好像保证不了复杂度?，不过过了大吉。。 :smiling_face_with_tear:

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        std::unordered_map<int,std::vector<int>> e;
        for(int i = 0; i < n; i++) {
            e[arr[i]].emplace_back(i);
        }
        std::queue<int> q;
        std::vector<int> d(n,n);
        q.push(0);
        d[0] = 0;
        auto check = [&arr,&d,&q,n](int u, int v) -> bool {
            if(d[v] > d[u] + 1) {
                d[v] = d[u] + 1;
                q.push(v);
                if(v == n - 1) {
                    return true;
                }
            }
            return false;
        };
        int lastval = -1;
        while(q.size()) {
            auto u = q.front();
            q.pop();
            if((u - 1 >= 0 && arr[u - 1] != arr[u] && check(u, u - 1)) || (u + 1 < n && arr[u + 1] != arr[u] && check(u, u + 1))) {
                return d[n - 1];
            }
            if(arr[u] != lastval) {
                for(const auto& v : e[arr[u]]) {
                    if(check(u,v)) {
                        return d[n - 1];
                    }
                }
               
            }
            lastval = arr[u];
        }
        return d[n - 1];
    }
};
1 个赞
4 
impl Solution {
  pub fn min_jumps(arr: Vec<i32>) -> i32 {
    let n = arr.len();
    if n == 1 { return 0; }
    let mut queue = VecDeque::with_capacity(n);
    queue.push_back((0, 0));
    let mut tp_map = HashMap::with_capacity(n);
    for (i, &v) in arr.iter().enumerate() { tp_map.entry(v).or_insert_with(Vec::new).push(i); }
    let mut visited = vec![false; n];
    visited[0] = true;
    while let Some((idx, step)) = queue.pop_front() {
      let val = arr[idx];
      let mut neighbors = tp_map.remove(&val).unwrap_or(Vec::new());
      neighbors.push(idx + 1);
      neighbors.push(idx - 1);
      for next in neighbors.into_iter() {
        if next == n - 1 { return step + 1; }
        if next > 0 && next < n && !visited[next] {
          visited[next] = true;
          queue.push_back((next, step + 1));
        }
      }
    }
    -1
  }
}

minJumps :: [Int] -> Int
minJumps (UV.fromList -> arr) = step (Q [(0, 0)] []) (one 0) tpMap
 where
  n = UV.length arr
  tpMap = IM.fromListWith (++) $ zip (UV.toList arr) (map (: []) [0 .. n - 1])
  step queue !visited !tp = case pop queue of
    Nothing -> -1
    Just ((!i, !steps), rest)
      | i == n - 1 -> steps
      | (n - 1) `elem` neighbors -> steps + 1
      | otherwise -> step queue' visited' tp'
     where
      val = arr UV.! i
      valid j = j >= 0 && j < n && IS.notMember j visited
      neighbors = filter valid $ [i - 1, i + 1] ++ IM.findWithDefault [] val tp
      tp' = IM.delete val tp
      visited' = IS.union visited $ IS.fromList neighbors
      queue' = flipfoldl' (push . (,steps + 1)) rest neighbors

data Queue = Q [(Int, Int)] [(Int, Int)]

push :: (Int, Int) -> Queue -> Queue
push x (Q xs ys) = Q xs (x : ys)

pop :: Queue -> Maybe ((Int, Int), Queue)
pop (Q [] []) = Nothing
pop (Q [] ys) = pop (Q (reverse ys) [])
pop (Q (x : xs) ys) = Just (x, Q xs ys)

随橙想呢，这么一个左手倒右手的队列实现是摊还 O(1) 的。这题就是一个标准的bfs模板题，注意预处理传送表、用完传送把对应的键删了，建议改成传送不计次、就成了标准的 0-1 bfs。

1 个赞