神马都会亿点点的毛毛张

一万次悲伤，依然会有Dream

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 163 阅读时长 ≈ 1 分钟
🌈大家好！我是神马都会亿点点的毛毛张👋
🍏本站发布的全部博客是毛毛张整理的笔记，内容全部根据互联网上可以检索到的资源整理而来！🍒
🥝毛毛张在写博客的过程中尽量标注全部应用的参考文献或者资源！🍓
🥑如果在文章中引用的内容涉及到侵权、版权问题、或者应用内容禁止被转载了🍎
🍉请通过首页的邮箱📩联系毛毛张，立马修改！🍊
阅读全文 »

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 2.1k 阅读时长 ≈ 4 分钟

贪心练习题

题目1：55. 跳跃游戏

1.题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • $1 <= nums.length <= 10^4$
  • $0 <= nums[i] <= 10^5$

2.题解

2.1 贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canJump(int[] nums) {
        int cover = 0; // 记录当前可以到达的最远位置
        // 遍历数组，直到当前索引超过 cover
        for (int i = 0; i <= cover; i++) {
            // 更新可以到达的最远位置
            cover = Math.max(i + nums[i], cover);
            // 如果可以到达或超过最后一个位置，直接返回 true
            if (cover >= nums.length - 1) return true;
        }
        // 如果遍历完后仍然无法到达最后位置，返回 false
        return false;
    }
}

题目2：45. 跳跃游戏 II

1.题目描述

给定一个长度为 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:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • $1 <= nums.length <= 10^4$
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

2.题解

2.1 贪心算法-写法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(int[] nums) {
        // 如果数组长度为 1，已经在最后一个位置，无需跳跃，返回 0
        if (nums.length == 1) return 0;
        int curDistance = 0; // 当前跳跃覆盖的最远距离下标
        int count = 0; // 跳跃次数
        int nextDistance = 0; // 下一跳能覆盖的最远距离下标
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 更新下一跳能覆盖的最远距离
            nextDistance = Math.max(i + nums[i], nextDistance);
            // 如果遍历到当前跳跃覆盖的最远距离
            if (i == curDistance) {
                count++; // 增加跳跃次数
                curDistance = nextDistance; // 更新当前跳跃覆盖的最远距离

                // 如果下一跳覆盖的最远距离已经达到或超过最后一个位置，直接跳出循环
                if (nextDistance >= nums.length - 1) break;
            }
        }
        return count; // 返回跳跃次数
    }
}

2.2 贪心算法-写法2

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 int jump(int[] nums) {
        // 初始化跳跃次数
        int result = 0;
        // 当前跳跃范围的最远距离
        int curDistance = 0;
        // 下一跳的最大范围
        int nextDistance = 0;

        // 遍历数组（不包括最后一个元素，因为跳跃到最后一个元素即结束）
        for (int i = 0; i < nums.length - 1; i++) {
            // 更新下一跳的最远距离
            nextDistance = Math.max(i + nums[i], nextDistance);

            // 当到达当前跳跃的最远距离时，需要进行跳跃
            if (i == curDistance) {
                result++;               // 增加跳跃次数
                curDistance = nextDistance;  // 更新当前跳跃的最远距离
            }
        }

        // 返回最少跳跃次数
        return result;
    }
}