每周一道算法题(四十二)

本周题目难度级别'Medium',使用语言'C'

题目：给你一组非负数组成的集合，然后从第一个索引中的数开始往下‘跳’，看能否‘跳’到最后一个数。eg：[2,3,1,1,4]，第一个索引是2，所以从第一个索引开始‘跳’两步，当‘跳’到第二个索引3的时候又能跳‘3’步，很显然能够跳完。再eg：[3,2,1,0,4]，第一个索引是3，从第一个索引开始‘跳’3步，当跳到0的时候，前面的3，2，1，0都已经跳完，就不能跳了，所以返回false。

思路：就是跳一跳么，一个索引一个索引的走，第一个索引能跳几步就往下继续跳，跳到下一个索引的时候更新所能够跳的步数，看最后能否跳完。不难，看代码吧：

bool canJump(int* nums, int numsSize) {
    //如果只有一个数，直接返回true（0也是true）
    if (numsSize == 1) return true;
    //获取能够跳的步数
    int temp = nums[0];
    //从第一个索引开始遍历
    int i = 0;
    //能跳的步数不为0就继续跳
    while (temp != 0) {
        //当跳完了集合返回true
        if (nums[i] +i >= numsSize - 1) return true;
        //步数减一
        temp--;
        //跳到下一个索引
        i++;
        //更新能跳的步数
        if (temp < nums[i]) temp = nums[i];  
    }
    return false;
}

效率还行吧，while可以换成for，for一般用于已知遍历次数的，while一般用于未知遍历次数的，这个题明显的知道最大遍历次数不超过numsSize，所以用for更好些，我就不改了。另外这个题用到了“贪心算法”也叫“贪婪算法”，有兴趣的小伙伴可以自己了解下。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!