跳跃游戏系列

代码已在 leetcode 上验证通过。

55.跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxCnt = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (i > maxCnt)
                return false;
            maxCnt = max(maxCnt, i+nums[i]);
        }
        return true;
    }
};

45.跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

class Solution {
public:
    int jump(vector<int>& nums) {
        int step = 0, begin = 0, maxPos = 0;
        while (maxPos < nums.size()-1)
        {
            int t = maxPos;
            for (int i = begin;  i<= t; i++)
                maxPos = max(maxPos, nums[i]+i);
            begin = t+1;
            step++;
        }
        return step;
    }
};

1306.跳跃游戏 III

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。

当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的任一下标处。

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        if (arr.empty() || start<0 || start>=arr.size())  
            return false;
        vector<bool> canJump(arr.size(), false);
        stack <int> st;
        st.push(start);
        while (!st.empty())
        {
            int t = st.top();
            if (arr[t]==0)  return true;
            canJump[t] = true;
            st.pop();
            if (t+arr[t]<arr.size() && canJump[t+arr[t]]==false)
                st.push(t+arr[t]);
            if (t-arr[t] >= 0 && canJump[t-arr[t]]==false)
                st.push(t-arr[t]);
        }
        return false;
    }
};

1345.跳跃游戏 IV

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标：

i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

class Solution {
public:
    int minJumps(vector<int>& arr) {
        unordered_map<int, vector<int>> mp;
        for (int i = 0; i < arr.size(); i++)
            mp[arr[i]].push_back(i);
        vector<bool> canJump(arr.size(), false);
        queue <int> q;
        q.push(0);
        int step = 0, cntPre = 1, cntCur = 0;
        while (!q.empty())
        {
            int t = q.front();
            if (t==arr.size()-1)  return step;
            canJump[t] = true;
            q.pop();
            if (t+1<arr.size() && canJump[t+1]==false)
            {
                q.push(t+1);
                cntCur++;
            }   
            if (t-1>=0 && canJump[t-1]==false)
            {
                q.push(t-1);
                cntCur++;
            }   
            for (int i = 0; i < mp[arr[t]].size(); i++)
            {
                if (canJump[mp[arr[t]][i]]==false && mp[arr[t]][i]!=t+1 && mp[arr[t]][i]!=t-1)
                {
                    q.push(mp[arr[t]][i]);
                    cntCur++;
                }  
            }
            mp.erase(arr[t]);
            cntPre--;
            if (cntPre == 0)
            {
                step++;
                cntPre = cntCur;
                cntCur = 0;
            }
        }
        return -1;
    }
};

1340.跳跃游戏 V

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

i + x ，其中 i + x < arr.length 且 0 < x <= d 。
i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        int n = arr.size();
        int res = 1;
        vector<vector<int>> t;
        vector <int> dp(n,0);
        for (int i = 0; i < n; i++)
            t.push_back({arr[i],i});
        sort(t.begin(), t.end());
        for (int i = 0; i < n; i++)
        {
            int index = t[i][1];
            dp[index] = 1;
            for (int j = index-1; j>=index-d && j>=0; j--)
            {
                if (arr[j] >= arr[index])  break;
                dp[index] = max(dp[index], dp[j]+1);
            }
            for (int j = index+1; j<=index+d && j<n; j++)
            {
                if (arr[j] >= arr[index])  break;
                dp[index] = max(dp[index], dp[j]+1);
            }
            res = max(res, dp[index]);
        }
        return res;
    }
};