Luobuyu's Blog

0%

45. 跳跃游戏 II

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 3.3k 阅读时长 ≈ 3 分钟
可以贪心也可以dp解决。

45.跳跃游戏 II

题目描述：

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

数据范围：

$1\le nums.len \le 10^4, 0\le nums[i] \le 10^3$

题解：

贪心法：

当前区间为 $[i, maxx]$ 。可以找出该区间里最大的 $i + nums[i]$ ，以及他的下标 $index$ 。然后下次从这个下标开始，区间变成了 $[index, maxx + index + nums[index]]$ 。如果区间的右端点到达了 $n - 1$ ，直接返回次数就行。

动态规划：

假设 $dp[i]$ 表示从 $0$ 跳到 $i$ 所需要的最小步，可以遍历 $j + nums[j] \ge i$ 的所有 $j$ ，然后用 $dp[j]$ 更新 $dp[i]$ 。

复杂度比较高，但是也能过。可以考虑使用单调队列优化，使用一个单调增队列，每次取队首的最小值 $dp[q[hh]]$ 。

代码：

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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static long long mod = 1e9 + 7;
    const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
    const int INF = 0x3f3f3f3f;
    int jump(vector<int> &nums)
    {
        int n = nums.size();
        int s = 0, maxx = nums[0];
        if (maxx >= n - 1)
            return 1;
        int ans = 0;
        while (true)
        {
            int mx = -1, index = -1;
            for (int i = s; i <= maxx; ++i)
            {
                if (i + nums[i] > mx)
                {
                    mx = i + nums[i];
                    index = i;
                }
            }
            ans++;
            maxx = mx;
            s = index;
            if (maxx >= n - 1)
                return ans;
        }
        return ans;
    }
};
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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static long long mod = 1e9 + 7;
    const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
    const int INF = 0x3f3f3f3f;
    int jump(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n, INF);
        dp[0] = 0;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] + j >= i)
                {
                    dp[i] = min(dp[j] + 1, dp[i]);
                }
            }
        }
        return dp[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
32
33
34
35
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static long long mod = 1e9 + 7;
    const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
    const int INF = 0x3f3f3f3f;
    int jump(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n, INF);
        dp[0] = 0;
        vector<int> q(n);
        int hh = 0, tt = -1;
        q[++tt] = 0; // 单调增
        for (int i = 1; i < n; ++i)
        {
            while (tt >= hh && i - q[hh] > nums[q[hh]])
                ++hh;
            dp[i] = dp[q[hh]] + 1;
            while (tt >= hh && dp[q[tt]] > dp[i])
                --tt;
            q[++tt] = i;
        }
        return dp[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
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return 0;
        int cur = 0;
        int cnt = 0;
        while(cur < n) {
            int maxx = -1, index = -1;
            if(cur + nums[cur] >= n - 1) return cnt + 1; // 需要先判断一下，下一步能不能走到。
            // 不能的话，下一步走最大值。
            for(int i = cur + 1; i < n && i <= cur + nums[cur]; ++i) {
                if(i + nums[i] > maxx) {
                    maxx = i + nums[i];
                    index = i;
                }
            }
            cnt++;
            cur = index;
        }
        return cnt;
    }
};

加上判定，如果不能到达最后一个，直接返回 $-1$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int solve(vector<int> &nums)
{
    int n = nums.size();
    int maxx = 0;
    int end = 0;
    int ans = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        maxx = max(maxx, i + nums[i]);
        if (i == end)
        {
            end = maxx;
            ans++;
        }
    }
    if(maxx >= n - 1)
        return ans;
    else
        return -1;
}