algo / LeetCode / 系列合集 17 分钟读完 (大约2558个字) 0次访问

[LeetCode]跳跃游戏合集

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

跳跃游戏

题目描述

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

思路

  • 我们可以把每个下标看成一个点, 每次在i号点跳跃认为是从i连边到j, 且$j\in [max(1, i - nums[i]),\ min(n, i + nums[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 + nums[i])$. 我们从R倒着向i遍历:
      • 若该点没被访问过, 置为True, 继续向前遍历.
      • 若该点已经被访问过了, 则可由观察1得到, 该点左边的点全被访问过, 退出循环即可.
  • 最终对于每个点, 我们至多遍历一次.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 写法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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 
写法2:稍微优化上述写法
      记录可行的跳的最远的位置 Mx 是哪
      利用观察1, 只要当前点i <= Mx, 则当前点一定可达.
*/
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> f(n, false);
        f[0] = true;
        int Mx = nums[0];
        for (int i = 1; i < n; i ++ ) {
            if (Mx >= i) {
                f[i] = true; 
                Mx = max(Mx, i + nums[i]);                
            }
        }
        return f[n - 1];
    }
};

复杂度分析

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

跳跃游戏 II

题目描述

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

思路

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 解法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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*  解法2：
    简单提一下另外一种思路: dp或者最短路的想法
    使用优先队列记录所有可达的点的信息: 最短距离以及它所能跳到的最远点
    当遍历到i的时候, 贪心的从优先队列中取最短距离最小的点：
        若它能到到达i, 则更新i
        否则直接弹出优先队列, 因为它不可能更新i之后的任意一个点.
    这样每个点最多 入/出 优先队列一次.
    时间复杂度为 O(N * logN)
    空间复杂度为 O(N)
*/
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = size(nums);
        vector<int> f(n, 1e9);
        priority_queue<pair<int, int>> heap;
        heap.emplace(0, nums[0]);
        f[0] = 0;
        for (int i = 1; i < n; i ++ ){
            auto [t, ed] = heap.top();
            while (heap.size() && ed < i){
                heap.pop();
                t = heap.top().first;
                ed = heap.top().second;
            }
            f[i] = -t + 1;
            heap.emplace(-f[i], i + nums[i]);
        }
        return  f[n - 1]; 
    }
};

复杂度分析

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

跳跃游戏 III

题目描述

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

思路

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)$

跳跃游戏 IV

题目描述

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

思路

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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)$

跳跃游戏 V

题目描述

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

  1. arr[i] > arr[j]
  2. $abs(i - j) <= d$
  3. $i - j$ 之间除i以外的点的值均小于$arr[i]$

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

思路

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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)$

跳跃游戏 VI

题目描述

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

思路

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 * logN)$(优先队列)
  • 空间复杂度$O(N)$

跳跃游戏 VII

题目描述

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

思路

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)$

[LeetCode]跳跃游戏合集

https://csjsss.github.io/2021/11/17/algo/LeetCode/系列合集/[LeetCode]跳跃游戏合集/

作者

Jsss

发布于

2021-11-17

更新于

2022-01-16

许可协议

 

喜欢这篇文章？打赏一下作者吧

评论

最新文章

标签

0-1BFS1
AcWing Cup1
BFS2
DFS1
LeetCode3
Linux1
RAII1
STL1
Spdlog1
cpp4
enable_shared_from_this1
二分1
二分搜索3
优先队列1
八股文1
共享主存1
前缀和5
动态规划14
区间最值1
匿名管道1
单调队列1
双指针1
同步原语1
周赛4
命名管道1
哈希表1
字符串分割1
工具软件1
差分1
平衡树1
并查集1
思维2
拓扑排序1
数据结构2
无锁队列1
最短路1
枚举8
树状数组2
模拟14
深度优先搜索1
状态压缩1
状态压缩动态规划1
状态机2
生产者-消费者1
语言基础2
贪心8
资源管理类2
进程通信1
连通性1
递推1
链表1

订阅更新

follow.it

×