跳跃游戏系列(LeetCode Jump Game I-V)

跳跃游戏系列(LeetCode Jump Game I-V)

用到的思路包括:贪心、广搜、递归。

题目较多,就不贴原题了,点击标题直接跳转查看。

LeetCode 55. Jump Game I

这道题给出的数组元素表示当前位置最大可跳距离,问能否从第一个位置到达最后一个位置。

BFS 是会超时的,需要 O(N) 的解法,贪心就是。
直接用一个变量记录最大可达到的范围,然后不断更新这个值。如果到达末尾前就卡在某一个下标无法前进,则最后一个位置不可达。

参考代码:

/*
 * @lc app=leetcode id=55 lang=cpp
 *
 * [55] Jump Game
 */

// @lc code=start
class Solution {
public:
    bool canJump(vector<int>& nums) {
        assert(!nums.empty());

        int n = nums.size();
        int canReach = 0;
        for (int i = 0; i < n; i++) {
            if (canReach < i) return false;
            if (canReach >= n-1) return true;
            canReach = max(canReach, i + nums[i]);
        } // greedy algorithm
        return canReach >= n-1;
    }
};
// @lc code=end

LeetCode 45. Jump Game II

这一题给出了最大跳跃能力,问从第一个位置到达最后一个位置至少需要跳几次。

这道题用 DP 和 BFS 都超时了,需要的是 O(N) 复杂读的做法。贪心可以。
用一个变量 nextMaxReach 记录下一步可以到达的最远距离,通过访问 curMaxReach 以内的所有点来更新这个距离得到最大值;然后 step++ 进入下一步,切换到 nextMaxReach 里继续进行。

参考代码:

/*
 * @lc app=leetcode id=45 lang=cpp
 *
 * [45] Jump Game II
 */

// @lc code=start
class Solution {
    //  assume that you can always reach the last index.
public:
    int jump(vector<int>& nums) {
        assert(!nums.empty());
        if (nums.size() == 1) return 0;

        size_t n = nums.size();
        int curMaxReach = 0;
        int nextMaxReach = 0;
        int step = 0;
        int i = 0; 
        while (i < n) {
            while (i <= curMaxReach) {
                nextMaxReach = max(nextMaxReach, i + nums[i]);
                if (nextMaxReach >= n-1) return step+1;
                i++;
            }
            step++;
            curMaxReach = nextMaxReach;
        } // greedy, find max dist can reach in given steps
        return -1;
    } // AC
};
// @lc code=end

LeetCode 1306. Jump Game III

这道题固定了跳跃距离只能是给定的距离,可以选择往前跳还是往后跳。问是否可以跳转到元素0所在位置。

简单 BFS 即可,类似走迷宫问题。所有位置最多访问一次,时间复杂度 O(N)。

参考代码:

/*
 * @lc app=leetcode id=1306 lang=cpp
 *
 * [1306] Jump Game III
 */

// @lc code=start
class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        assert(0 <= start && start < arr.size());
        if (arr[start] == 0) return true;

        size_t n = arr.size();
        queue<int> q;
        vector<bool> vis(n, false);
        q.push(start);
        vis[start] = true;
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            if (i + arr[i] < n && !vis[i + arr[i]]) {
                if (arr[ i+arr[i] ] == 0) return true;
                q.push(i+arr[i]);
                vis[i+arr[i]] = true;
            }
            if (0 <= i - arr[i] && !vis[i - arr[i]]) {
                if (arr[ i-arr[i] ] == 0) return true;
                q.push(i-arr[i]);
                vis[i-arr[i]] = true;
            }
        }
        return false;
    } // AC, BFS
};
// @lc code=end

LeetCode 1345. Jump Game IV

这道题加了一个“任意门”,可以选择往前跳一格、往后跳一格,或者跳转到与当前元素值相同的位置上。问从第一个位置到达最后一个位置至少需要跳几次。

一道典型的 BFS 题目,类似于走迷宫问题。使用 queue 来保存顺序,先到的一定是最快的。
注意这里原始的 BFS 会超时,应该注意优化:连续 [7,7,7,7,7] 之类其实只有首尾两个位置是有用的;同一个任意门只有第一次跳转是有用的。
unordered_map 套 vector 也是很有趣的用法,比 unordered_multimap 好用。

参考代码:

/*
 * @lc app=leetcode id=1345 lang=cpp
 *
 * [1345] Jump Game IV
 */

// @lc code=start
class Solution {
public:
    int minJumps(vector<int>& arr) {
        assert(!arr.empty());
        if (arr.size() == 1) return 0;

        size_t n = arr.size();
        queue<pair<int, int>> q;
        vector<bool> vis(n, false);
        
        // unordered_map<vector> is better than unordered_multimap in
        // insert elements & for-range specified key & erase key
        unordered_map<int, vector<int>> val2idx;
        for (int i = 0; i < n; i++) {
            if (0 <= i-1 && arr[i-1] == arr[i]
                && i+1 < n && arr[i] == arr[i+1]) {
                    vis[i] = true;
                    continue;
            } // [7,7,7] only 1st and last useful, or TLE
            val2idx[arr[i]].push_back(i);            
        }
        q.push({0, 0});
        vis[0] = true;
        while (!q.empty()) {
            auto&& p = q.front();;
            int i = p.first;
            int step = p.second;
            q.pop();
            if (0 <= i-1 && !vis[i-1]) {
                q.push({i-1, step+1});
                vis[i-1] = true;
            }
            if (i+1 < n && !vis[i+1]) {
                if (i+1 == n-1) return step+1;
                q.push({i+1, step+1});
                vis[i+1] = true;
            }

            for (int x : val2idx[arr[i]]) {
                if (x == i || vis[x]) continue;
                if (x == n-1) return step+1;
                q.push({x, step+1});
                vis[x] = true;
            }
            val2idx[arr[i]] = {}; // key optimization
        }
        return -1;
    }
};
// @lc code=end

另一种写法

注意到 queue 中其实 step 是有规律的,有一种写法可以 queue 只保存 index 而不用保存 step,节省一半空间。参考 花花酱的解答

  • 只用一个 int 变量保存当前 step
  • 每次检查 while(!q.empty()) 之后记录 k=q.size(),然后把队列中前 k 个元素弹出做计算。这 k 个元素的步数 其实都是 step,下一轮的元素都是 step+1。

LeetCode 1340. Jump Game V

这道题把数组元素值设定为台阶高度,然后指定横向最大跳远能力,并限制跳远时只能往下落,不能跳到或经过更高的台阶。问从任意位置出发,最多能踩到几个台阶。

这就是一道典型的 DP 问题了。以每个台阶为起点的最大跳台阶数目,由左右两边 d 以内比自己低的台阶决定。由于高台阶依赖于低台阶的结果,我们需要先做一个排序的预处理,由此来决定计算顺序。时间复杂度 O(d*N+NlogN)。

/*
 * @lc app=leetcode id=1340 lang=cpp
 *
 * [1340] Jump Game V
 */

// @lc code=start
class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        assert(!arr.empty() && d >= 1);

        size_t n = arr.size();
        vector<pair<int,int>> v;
        for (int i = 0; i < n; i++) {
            v.push_back({arr[i], i});
        }
        sort(v.begin(), v.end()); // sort by height

        vector<int> dp(n, 1);
        for (auto&& [h, i] : v) {
            for (int k = 1; k <= d; k++) { // ->
                int j = i + k;
                if (j >= n || arr[j] >= arr[i]) break;
                dp[i] = max(dp[i], dp[j] + 1);
            }
            for (int k = 1; k <= d; k++) { // <-
                int j = i - k;
                if (0 > j || arr[j] >= arr[i]) break;
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        int res = 1;
        for (int x : dp) {
            res = max(res, x);
        }
        return res;
    } // AC, DP
};
// @lc code=end
上一篇:Human Resource Machine 全成就通关 第31关


下一篇:【贪心算法】leetcode55. 跳跃游戏