温州网站设计公司_上海正规装修公司排名_百度搜索推广_搜索引擎营销的实现方法有哪些

标签：#贪心 #数组 #动态规划

Ⅰ. 题目

给定一个长度为 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:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

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

0. 个人方法

与上一题相似，只是这一题对跳跃过程有些要求。我们可以观察到，如果要实现最小的跳跃次数，那么我每次都要从当前的可跳范围内，选一个能让我下一次跳的最远的位置去跳。
比如说，目前有一个数组是 [3, 2, 3, 1, 1, 4, 2]，我当前的位置是3，那么后面三个可跳的位置是[2, 3, 1]，而这里面选择“3”这个位置，能让我下一次跳的更远。并且在这三个位置里一定是必跳的。
因此可以找一个边界条件，持续令 位置 = max（当前可跳最远距离，接下来能跳的最远距离），直到 i = border 的时候，对边界进行更新，并且step++

class Solution {
public:int jump(vector<int>& nums) {int length = nums.size();int position = 0;       // 更新位置int border = 0;     // 局部能跳的最远距离int step = 0;           // 次数for (int i=0; i<length-1; i++){position = max(position, i + nums[i]);if (i == border){border = position;step++;}}return step;}
};