leetcode 跳跃游戏系列

55. 跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // index记录当前可以往前走的最大长度，每跳一步index--
        if (nums.size() == 1) {
            return true;
        }
        int index = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (index-- == 0) {
                return false;
            }
            index = max(index, nums[i]);
        }
        return true;
    }
};

45. 跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len, len);
        dp[0] = 0;
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < i; ++j) {
                if (j + nums[j] >= i) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[len - 1];
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        int step = 0, maxpos = 0, end = 0;
        for (int i = 0; i < len; ++i) {
            if (maxpos < i) {
                return -1;
            }
            maxpos = max(i + nums[i], maxpos);
            if (i == end && i != len - 1) {
                ++step;
                end = maxpos;
            } 
        }
        return step;
    }
};

1306. 跳跃游戏 III

class Solution {
public:
    vector<int> vis;
    bool flag = false;
    void dfs(vector<int>& arr, int idx) {
        if (vis[idx] || flag)    return;
        vis[idx] = 1;
        if (arr[idx] == 0)  {
            flag = true;
            return;
        }
        if (idx - arr[idx] >= 0)    dfs(arr, idx - arr[idx]);
        if (idx + arr[idx] < arr.size())    dfs(arr, idx + arr[idx]);
    }

    bool canReach(vector<int>& arr, int start) {
        int len = arr.size();
        vis.resize(len, 0);
        dfs(arr, start);
        return flag;
    }
};

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        // BFS
        int len = arr.size();
        vector<int> vis(len , 0);
        queue<int> q;
        q.push(start);
        vis[start] = 1;
        while (!q.empty()) {
            int temp = q.front();
            if (arr[temp] == 0) return true;
            q.pop();
            if (temp - arr[temp] >= 0 && !vis[temp - arr[temp]]) {
                q.push(temp - arr[temp]);
                vis[temp - arr[temp]] = 1;
            }
            if (temp + arr[temp] < len && !vis[temp + arr[temp]]) {
                q.push(temp + arr[temp]);
                vis[temp + arr[temp]] = 1;
            }
        }
        return false;
    }
};

1345. 跳跃游戏 IV

class Solution {
public:
    int ret = INT_MAX;
    unordered_map<int, vector<int>> mp;
    vector<int> vis;
    void DFS(vector<int>& arr, int step, int idx) {
        if (idx == arr.size() - 1) {
            ret = min(ret, step);
        }
        if (step > ret || vis[idx] <= step) return;
        vis[idx] = step;
        for (int& x : mp[arr[idx]]) {
            if (x == idx)   continue;
            DFS(arr, step + 1, x);
        }
        if (idx + 1 < arr.size()) {
            DFS(arr, step + 1, idx + 1);
        }
        if (idx - 1 >= 0) {
            DFS(arr, step + 1, idx - 1);
        }
    }

    int minJumps(vector<int>& arr) {
        // 仿记忆化搜索，vis用来保存idx最小访问跳跃次数
        // 超时
        int len = arr.size();
        ret = min(ret, len);
        vis.resize(len, len);
        for (int i = 0; i < len; ++i) {
            mp[arr[i]].push_back(i);
        }
        DFS(arr, 0, 0);
        return ret;
    }
};

为什么只能用bfs不能用dfs：

虽然对DFS进行了优化，避免用数组记录访问的最小次数，当前step>min_step时退出，但显然step的减少速度比不上BFS中step+1快，所以超时，只能采用BFS

因为BFS的更新step是+1递增，所以可以避免许多重复的idx加入queue，但为了避免重复元素过多对map的访问超时，直接将map.clear()

class Solution {
public:
    int minJumps(vector<int>& arr) {
        const int inf = 0x3f3f3f3f;
        int len = arr.size();
        unordered_map<int, vector<int>> mp;
        for (int i = len - 1; i >= 0; --i) {
            mp[arr[i]].push_back(i);
        }
        vector<int> dist(len, inf);
        queue<int> q;
        q.push(0);
        dist[0] = 0;
        while (!q.empty()) {
            int t= q.front();
            q.pop();
            if (t == len - 1) return dist[t];
            for (int& x : mp[arr[t]]) {
                if (dist[x] == inf) {
                    dist[x] = dist[t] + 1;
                    q.push(x);
                }
            }
            mp[arr[t]].clear();
            if (t + 1 < len && dist[t + 1] == inf) {
                q.push(t + 1);
                dist[t + 1] = dist[t] + 1;
            }
            if (t - 1 >= 0 && dist[t - 1] == inf) {
                q.push(t - 1);
                dist[t - 1] = dist[t] + 1;
            }
        }
        return -1;
    }
};