手机网页及网站设计 pdf,软文生成器,企业内部网站建设方案,做网站网页兼容性45. 跳跃游戏 II 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处: 0 j nums[i]i j n 返回到达 num…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]。 先分析题目给的第一个例子
输入: nums [2,3,1,1,4]
输出: 2从起点开始i0,nums[i]2可以跳到i1或i2的位置。
如果跳到i1处由于nums[i]3那么接下来最远可以跳到i4处。如果跳到i2处由于nums[i]1,那么接下来最远可以跳到i3处。
显然我们要跳到i1处接着跳到i4处此时到达终点。在每一步中我们都尝试找到能让我们跳得最远的位置从而确保在最少的跳跃次数内到达数组的最后一个位置。
那么这道题的贪心策略可以这样描述
在任意一个起始点i上我们不仅要考虑从该点可以直接跳跃的最大长度nums[i]还要考虑在这个范围内所有可能的下一步跳跃位置并从中选择一个使得我们能够到达最远距离的位置进行跳跃。也就是 i j n u m s [ i j ] , 其中 1 j n u m s [ i ] ijnums[ij],其中1jnums[i] ijnums[ij],其中1jnums[i]的最大值。
代码
int jump(vectorint nums) {int time 0;int n nums.size(), i 0;while (i n - 1) {if (i nums[i] n - 1) {time;break;}int max 0, maxIndex 0;for (int j 1; j nums[i]; j) {if (i j nums[i j] max) {max i j nums[i j];maxIndex i j;}}i maxIndex;time;}return time;
}除此之外还有一种贪心解法我们的目标是到达数组最后一个位置因此我们可以考虑最后一步跳跃前所在的位置从起点往终点开始搜索显然会出现有多个位置都可以跳跃到数组的最后一个位置的情况那么我们选取距离最远的那个位置找到一次跳跃前的位置后继续按照这样的步骤一直找到开始位置为止。
代码
int jump(vectorint nums) {int time0;int positionnums.size()-1;while(position0){for(int i0;iposition;i){if(inums[i]position){time;positioni;break;}}}return time;
}
