未来，未来。
——2024年6月17日
题目描述
给定一个含n（1≤n≤1000）个非负整数数组nums（0≤nums[i]≤1000），数组中的每个元素表示在该位置可以跳跃的最大长度，假设总是可以从初始位置0到达最后一个位置n-1，设计一个算法求最少的跳跃次数。
例如nums={2，3，1，1，4}，n=5，从位置0可以跳一步到达位置1，再从位置1跳3步到位置4，所以结果为2。
题解思路
贪心法
1. 当n=1时，不需要跳跃，跳跃步数为0；
2. 当n>1时，用steps表示跳跃步数；
错误思路：
- 在i=0时会跳出第一步，那它能达到最远的位置就是end=i+nums[i]，那是不是说每次都跳跃最远的距离（即nums[i]）就能跳跃最少的步数呢？答案是否定的，那题目的例子来说：
- 此时nums[0]=2，能跳跃的最远距离是2，能达到的最远位置是0+nums[0]=2，到达2号位；
- 此时nums[2]=1，能跳跃的最远距离就是1，能达到的最远位置是2+nums[2]=3，到达3号位；
- 此时nums[3]=1，能跳跃的最远距离就是1，能达到的最远位置是3+nums[3]=4，到达4号位；
- 可以看到一共跳跃了3步，而它明明只需要两步就能到达最后的位置。
正确思路：多考虑一步，既要考虑当前跳跃能达到的最远位置，还需要考虑从i到最远位置之间的nums[k]（k∈[i, i+nums[i]]）能达到的最远位置k+nums[k]，即使它最终超过了nums.size()-1。
再举个例子
当前nums[] = {2，1，3，2，2，1，4} ，pos的位置变化从0→2→4→末尾（甚至超过末尾），只需要三步即可。
注：可以好好体会一下这个思路，考试周结束我会继续完善这篇博客。
代码实现
// 提前向前看两个位置, 找到最远跳跃距离
int minStep(vector<int> &num){int len = num.size();int ans = 0;if(len == 1){return 0;}for(int i = 0; i < len; ){int maxstep1 = i + num[i];//记录当前能达到的最远位置int maxstep2;int max = 0;int pos = 0;for(int j = i + 1; j <= i + num[i] && j < len; j++){//在该区间中找第二个能达到的最远位置对应的jmaxstep2 = j + num[j];//记录j能达到的最远位置if(maxstep2 > max){max = maxstep2;pos = j;}if(maxstep2 >= len - 1){break;//如果已经超过len-1，说明已经能跳出最后一个位置了，那么就不需要找j了}}cout<<"从"<<i<<"位置跳跃到"<<pos<<"位置"<<endl;ans++;if(maxstep2 >= len - 1){cout<<"从"<<pos<<"位置跳跃到末尾"<<endl;ans++;break;}i = pos;//更新i作为下一次的起点}return ans;
}代码简化
int minStep(vector<int> &v){int len = v.size();int maxDistance = 0;int end = 0;int steps = 0;// 最后一个位置不需要向前跳跃了哦for(int i = 0; i < len - 1; i++){maxDistance = max(maxDistance, v[i] + i);if(i == end){//说明能走到最远的位置,那么后面仍然有数字end = maxDistance;steps++;}}return steps;
}运行结果
