每天一道LeetCode-----数组序列,每个元素的值表示最多可以向后跳多远,计算最少跳多少次可以到达末尾

xiaoxiao2021-02-28  8

Jump Game II

原题链接Jump Game II 给定一个数组序列,序列中每一个元素的值表示最多可以向后跳多远,初始时从下标0开始,计算最少跳多少次可以到达末尾的元素位置。

刚开始是想用深度优先(dfs)+ 动态规划解决的,结果竟然超时了,看到答案后真是….哎╮(╯▽╰)╭


对于每个位置,它跳一次可以到达的位置是一个范围,而对于这个范围,跳一次可以到达的位置仍然是一个范围。以示例序列[2,3,1,1,4]为例。 初始时,在下标为0的位置上,可以到达的下标范围是[1,2] 对于下标1,可以到达的下标范围是[2,4]。对于下标2,可以到达的下标范围是[3,4]。所以范围[1,2]可以到达的范围是[3,4]。

所以如果每次移动的都是一个范围,那么直到这个范围包含最后一个位置,就说明已经到达末尾了。而移动的次数,就是移动范围的次数。 代码如下

class Solution { public: int jump(vector<int>& nums) { int n = nums.size(); int steps = 0; /* [start, end]记录当前达到的范围,初始为0 */ int start = 0; int end = 0; while(end < n - 1) { /* 找下次可以到达的最远位置 */ int max_pos = 0; for(int i = start; i <= end; ++i) max_pos = std::max(max_pos, i + nums[i]); /* 对于可以到达最远位置的那个下标i,它可以到达的位置为[i+1, max_pos],即 * start, ..., i, i+1, i+2, end, ... ,max_pos * 下次的范围就是[end + 1, max_pos] */ start = end + 1; end = max_pos; ++steps; } return steps; } };

Jump Game

原题链接 Jump Game 这个就是判断能不能到达最右边,方法和上面一样,转换为广度优先解决 代码如下

class Solution { public: bool canJump(vector<int>& nums) { int left = 0; int right = 0; while(right < nums.size() - 1) { int max_pos = right; for(int i = left; i <= right; ++i) max_pos = std::max(max_pos, nums[i] + i); if(max_pos <= right) return false; left = right; right = max_pos; } return true; } };

上面两道题主要是将题目转换为广度优先(bfs)进行解决。因为每个位置可以达到的位置都是一个范围,那么就导致不确定应该将它跳到哪,从而会有很多中可能,深度优先是依次考虑每种可能,会比较慢。而广度优先将所有的可能一起考虑,每次都移动一个范围,从而不需要那么多的迭代(递归)次数。

转载请注明原文地址: https://www.6miu.com/read-1400200.html

最新回复(0)