#include <iostream>
#include <vector>
using namespace std;
//数组跳问题，给一个非负整数数组（数组中的每个元素代表在该位置可以跳跃的最大长度），使用最少的跳跃次数到数组的最后一个人位置。
int MaxCount(vector<int> arr)
{
if (arr.size() == 0 || arr.size() == 1) //如果数组个数为0或者为1，则不需要跳
{
return 0;
}
if (arr[0] > arr.size()) //如果第一个数大于数组个数，则一步直接可以到达
{
return 1;
}
int cur = 0, pre = 0; //当前能到达的最远位置和之前能到达的最远位置
int jums = 0;
int i = 0; //当前遍历的数组下标
while (cur < arr.size() - 1) //如果当前能到达最后一个位置，则结束循环
{
jums++;
pre = cur; //更新之前所能到达的最远位置
for (; i <= pre; i++) //遍历在上次可以跳到的范围内，当前能跳到的最远的范围
{
cur = max(cur, i + arr[i]); //更新当前能够跳的最远的位置
}
if (cur == pre) //如果当前能到达的位置和上次没有变化，则到不了最后一个位置
return -1;
}
return jums;
}
int main(int argc, char** argv)
{
//vector<int> arr = { 2,3,1,1,4 };
vector<int> arr = { 3,2,1,0,4 };
int jumps = MaxCount(arr);
cout << jumps << endl;
return 0;
}
数组跳
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 1用两个栈实现队列 【题目】用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 ...
- 一些常用的redis结构,底层实现及方法 哈希表 在redis当中，使用哈希表作为字典的底层实现，底层是数组+链表...
- 最新字节跳动面试题与答案 1.算法题一：无序数组的中位数 (快排思想O(N) 时间复杂度) 2.算法题二：给一数组...
- 数组 定义数组变量： list = [] （以python举例）可以是空数组，也可以直接存放初始值。当然也可以存放...
