[LeetCode]跳跃游戏合集

acvv_Jsss

3093

2021.11.17

2021.12.01

发布于未知归属地

动态规划前缀和最短路优先队列 BFS 单调队列学习分享

简介

简单整理一下LeetCode上跳跃游戏系列题目. 包含跳跃游戏、跳跃游戏II、跳跃游戏III、跳跃游戏IV、跳跃游戏V、跳跃游戏VI、跳跃游戏VII共七题.

1 跳跃游戏

题目描述

开始位于1号点, 每次在i号点最远可以跳跃nums[i]单位距离, 判断能否跳到n号点.

思路

我们可以把每个下标看成一个点, 每次在i号点跳跃认为是从i连边到j, 且 $j \in [ma x (1, i - n u m s [i]), min (n, i + n u m s [i])]$ .
这样问题转化成判断是否存在至少一条从1号点到n号点的路径, 即1号点与n号点是否联通.
暴力使用BFS等算法求解的时候, 正确性是毫无疑问的, 但时间复杂度过高 $O (N^{2})$ , 会TLE.
暴力时间复杂度高的原因是: 每个点会被遍历多次, 如果优化每个点被遍历的次数, 那么问题就得到了解决.
结合题意, 有以下观察:
1. 如果当前位于i号点, 那么1 - i之间的所有点已经可达了(即被遍历过了). 假设是从j点跳到了i点( $j < i$ ), 那么j - i之间的所有点可以被j遍历到, 问题规模减小到1 - j, 归纳下去即可证明.
2. 有了观察1, 当我们位于i号点的时候, 只需关心它向右能跳到的点. i向右最远能跳到 $R = min (n, i + n u m s [i])$ . 我们从R倒着向i遍历:
  - 若该点没被访问过, 置为True, 继续向前遍历.
  - 若该点已经被访问过了, 则可由观察1得到, 该点左边的点全被访问过, 退出循环即可.
最终对于每个点, 我们至多遍历一次.

Code

C++

// 写法1
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> f(n, false);
        f[0] = true;
        for (int i = 0; i < n; i ++ )
            if (f[i]){
                int j = min(n - 1, nums[i] + i);
                while (f[j] == false)
                    f[j --] = true;
            }
        return f[n - 1];
    }
};

复杂度分析

时间复杂度 $O (N)$
空间复杂度 $O (N)$

2 跳跃游戏 II

题目描述

开始位于1号点, 每次在i号点最远可以跳跃nums[i]单位距离, 判断跳到n号的最少跳跃次数(保证可以到达).

思路

有了第一题的分析过程, 这题可以很自然的使用第一题的分析思路: 只需求1号点到n号点的最短路.

利用BFS的性质: 每个点第一次被遍历的时候一定是该点的最短距离. 用第一题思路实现即可.

Code

C++

// 解法1: 上述思路的实现
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, -1);
        f[0] = 0;
        
        for (int i = 0; i < n; i ++ ) {
            int R = min(n - 1, i + nums[i]);
            while (f[R] == -1)
                f[R --] = f[i] + 1;
        }
        return f[n - 1];
    }
};

复杂度分析

时间复杂度 $O (N)$
空间复杂度 $O (N)$

3 跳跃游戏 III

题目描述

开始位于start号点, 每次在i号点可以跳到i + nums[i]或i - nums[i], 判断能否跳到nums[k] = 0的某个点.

思路

有了前面题目的分析, 这题就是简单的BFS. 每个点最多出去两条边, 暴力BFS即可.

Code

class Solution {
public:
    bool canReach(vector<int>& arr, int st) {
        int n = arr.size();
        vector<bool> f(n, false);
        queue<int> qu;
        f[st] = true;
        qu.push(st);
        
        while (qu.size()) {
            auto t = qu.front();
            qu.pop();
            if (t + arr[t] < n and t + arr[t] >= 0 and f[t + arr[t]] == false)
                f[t + arr[t]] = true, qu.push(t + arr[t]); 
            if (t - arr[t] < n and t - arr[t] >= 0 and f[t - arr[t]] == false)
                f[t - arr[t]] = true, qu.push(t - arr[t]); 
        }
        bool flag = false;
        for (int i = 0; i < n; i ++ ) {
            if (arr[i] == 0 and f[i])
                flag = true;
        }
        
        return flag;
    }
};

复杂度分析

时间复杂度 $O (N)$
空间复杂度 $O (N)$

4 跳跃游戏 IV

题目描述

开始位于1号点, 每次在i号点可以跳到i + 1、i - 1、j(满足nums[i] == nums[j]), 求解跳到n号点的最短步数.

思路

题目求解的是最短路, 自然就往最短路算法上想(BFS、Dijkstra等). 由于本题边权均为1, 因此考虑使用BFS算法求解.

由题目可知, 所有值相同的点之间存在一条代价为1的边. 因此我们先使用哈希表得到所有值相同的点, 接着BFS即可.
注意优化的一点: BFS第一次遍历到的时候, 其最短路就已经确定了. 因此我们遍历了一遍某一个值相同的集合后, 直接从哈希表删除该集合即可.

Code

const int INF = 1e8;
class Solution {
public:
    int minJumps(vector<int>& arr) {
        unordered_map<int, vector<int>> mp;
        int n = arr.size();
        for (int i = 0; i < n; i ++ ) {
            int c = arr[i];
            mp[c].push_back(i);
        }
        vector<int> f(n, INF);
        queue<int> qu;
        f[0] = 0;
        qu.push(0);
        
        while (qu.size()) {
            auto t = qu.front();
            qu.pop();
            if (t + 1 < n and f[t + 1] == INF)
                f[t + 1] = f[t] + 1, qu.push(t + 1);
            if (t - 1 >= 0 and f[t - 1] == INF)
                f[t - 1] = f[t] + 1, qu.push(t - 1);
            for (auto& c : mp[arr[t]]) {
                if (f[c] == INF)
                    f[c] = f[t] + 1, qu.push(c);
            }
            mp.erase(arr[t]);
        }
        return f[n - 1];
    }
};

复杂度分析

时间复杂度 $O (N)$
空间复杂度 $O (N)$

5 跳跃游戏 V

题目描述

在i号点可以跳到j号的要求是:

arr[i] > arr[j]
$ab s (i - j) <= d$
$i - j$ 之间除i以外的点的值均小于 $a rr [i]$

可以从任意点开始, 求解最多能跳多少个点.

思路

观察到数据范围为1000, 因此使用 $O (N^{2})$ 的算法求解即可.
依然利用前面题目的思路, 将每个下标视作一个点. i号点能跳到j号点, 则认为存在i指向j的一条有向边.
关键的约束条件为 $a rr [i] > a rr [j]$ , 这样的话构建出的图一定为有向无环图(DAG).
问题转化成求有向无环图上的一条最长路径. 因为存在拓扑序, 因此按照序列递推(动态规划, DP)求解即可.
定义f[u]为走到u点时的最大值. 若存在有向边 $v \to u$ , 则有:
$f [u] = ma x (f [u], f [v] + 1)$
因为按照拓扑序的顺序递推, 因此当计算u点时, 其所依赖的点v已经全部被计算过了, 保证了正确性.

Code

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        int n = arr.size();
        vector<vector<int>> g(n, vector<int>(n, 0));
        vector<int> in(n, 0), f(n, 1);
        // O(n^2)预处理有向边
        for (int i = 0; i < n; i ++ ) {
            // L 
            for (int j = i - 1, Mx = arr[i] - 1; j >= max(0, i - d); j -- ) {
                Mx = max(Mx, arr[j]);
                if (Mx >= arr[i])
                    break;
                g[i][j] = 1;
                in[j] ++ ;
            }
            // R
            for (int j = i + 1, Mx = arr[i] - 1; j <= min(n - 1, i + d); j ++ ) {
                Mx = max(Mx, arr[j]);
                if (Mx >= arr[i])
                    break;
                g[i][j] = 1;
                in[j] ++ ;
            }
        }
        // 拓扑排序 + 递推(DP)
        queue<int> qu;
        for (int i = 0; i < n; i ++ ) {
            if (in[i] == 0)
                qu.push(i);
        }
        
        while (qu.size()) {
            auto t = qu.front();
            qu.pop();
            for (int i = 0; i < n; i ++ ) {
                // t 能走到 i 点
                if (g[t][i]) {
                    f[i] = max(f[i], f[t] + 1);
                    if (-- in[i] == 0)
                        qu.push(i);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i ++ )
            ans = max(ans, f[i]);
        return ans;
    }
};

复杂度分析

时间复杂度 $O (N^{2})$
空间复杂度 $O (N^{2})$

6 跳跃游戏 VI

题目描述

开始位于1号点, 每次最多往前跳k步, 求跳到n时的最大得分(最大数字之和).

思路

动态规划:
1. 状态表示: 定义f[i]为走到i点时的最大得分. 答案即位f[n].
2. 状态计算：依据题目要求, 最多跳k步, 因此
  $f [i] = ma x (f [j] + n u m s [i]), j \in [ma x (1, i - k), i - 1]$
3. 朴素状态转移复杂度是 $O (K)$ , 会超时. 注意到转移要求的是滑动窗口内的最大值. 因此可以利用单调队列或优先队列(类似第二题解法2)优化.

Code

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n, 0);
        deque<int> dq;
        
        for (int i = 0; i < n; i ++ ) {
            if (dq.size() and i - dq.front() > k)
                dq.pop_front();
            f[i] = nums[i];
            if (dq.size())
                f[i] = nums[i] + f[dq.front()];
            while (dq.size() and f[dq.back()] < f[i])
                dq.pop_back();
            dq.push_back(i);
        }
        return f[n - 1];
    }
};

复杂度分析

时间复杂度 $O (N)$ (单调队列)、 $O (N * l o g N)$ (优先队列)
空间复杂度 $O (N)$

7 跳跃游戏 VII

题目描述

开始位于1号点, 每次向前跳的距离有限制, 判断能否跳到n号点.

思路

使用动态规划解决. 定义f[i]为是否能够跳到i位置, 只需判断是否存在 $j \in [i - ma x J u m p, i - min J u m p]$ , 使得 $f [j] = T r u e$ 成立.
为了快速判断是否存在j, 使用前缀和的思想. 记 $s [i] = \sum_{j = 0}^{i} f [i]$ .
这样每次只需判断是否有 $s [i - min J u m p] - s [i - ma x J u m p - 1] > 0$ 成立即可.

Code

class Solution {
public:
    bool canReach(string str, int Mn, int Mx) {
        int n = str.size();
        vector<int> f(n + 1, 0), s(n + 1, 0);
        f[1] = s[1] = 1;
        for (int i = 2; i <= n; i ++ ) {
            if (str[i - 1] == '0') {
                if (s[max(0, i - Mn)] - s[max(0, i - Mx - 1)])
                    f[i] = 1;
            }
            s[i] = s[i - 1] + f[i];
        }
        return f[n];
    }
};

复杂度分析

时间复杂度 $O (N)$
空间复杂度 $O (N)$

结语

跳跃游戏系列主要包含了BFS、最短路、动态规划、拓扑排序、单调队列、优先队列、前缀和等高频算法, 值得反复学习, 细细品味.