给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
思路1：用正向递归的方法来解决。
void rec(vector<int>& nums,int i,int temp,int &ans,int step)//i 是当前位置 temp为当前要跳的步长 ans记录最短路径 step计算下次要跳多远 { if(temp==0) return;//跳步为0，返回 if(i>=nums.size()) return;//i越界，返回 if(i+temp>=nums.size()-1)//下一次跳步到或者包含最后一个位置 { ans=step>=ans?ans:step; return; } //可以重新跳了 i=temp+i;//更新i temp=0;//更新temp step++;//更新步数 while(temp<nums[i]) { rec(nums,i,++temp,ans,step); } } int jump(vector<int>& nums) { if(nums.size()==0||nums.size()==1) return 0; int temp=0; int step=1; int ans=int32_max; while(temp<nums[0]) { rec(nums,0,++temp,ans,step); } return ans; }
方法是没问题的，只是时间超时了。。。
方法2：逆向思维，从后向前找
int rec(vector<int> &nums,int end,int &ans) { int temp=end; ans++; for(int i=end-1;i>=0;i--) { if(nums[i]>=(end-i))// 找到一个最小i，可以直接到达末尾的下标。 temp=i; } return temp; } int jump(vector<int>& nums) { int end=nums.size()-1; int ans=0; while(end>0) { end=rec(nums,end,ans); } return ans; }
还超时，牛皮。。。
方法3：贪心
int jump(vector<int>& nums) { int ans=0; int i=0; int left=0,right=0;//在这个区间内计算该选哪个跳步长度 while(right<nums.size()-1) { int next=0;//记录下一个要跳去的地方 for(i=left;i<=right;i++) next=max(i+nums[i],next); left=right+1; right=next; ans++; } return ans; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/604362.html