首页 > 代码库 > [LeetCode]Jump Game

[LeetCode]Jump Game

2024-09-12 03:50:22   218人阅读

以数组下标为表示，数组的值为可前进范围，判断是否能到数组的最后。

这个问题非常简单，将下标和数组值加起来，找到大于数组长度的值为止，此时，是可以；如果找不到，就表示不可以。

/***************************************************************************************************
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
***************************************************************************************************/
#include<stdio.h>
#include<stdbool.h>

bool canJump(int* nums, int numsSize) {
        bool flag = false;
    int i = 0;
    int range = nums[i] + i;
    if(range >= numsSize)return true;
    i++;
    while(range >= i && i < numsSize){
        range = range > nums[i] + i ? range : nums[i] + i;
        if(range >= numsSize){
            flag = true;
            break;
        }
        i++;
    }
    return flag;
}

void main(){
    //int nums[] = {2,3,1,1,4};
    //int nums[] = {3,2,1,0,4};
    //int nums[] = {3,2,1,3,4};
    printf("%d",canJump(nums,5));
}

自己考虑了一下，如果要求正好到数组的末尾才算能够到达，没个数组的值不再是范围内的下标都可以，而是必须到对应的下标位置，该怎么解。

思路如下：遍历数组验证能否到达末尾，并标记访问过的值；遍历时，遇到访问过的跳过。

失败的情况：

访问的值+当前下标超过了数组的长度时，失败；

访问的值+当前下标等于已访问过的下标时，失败；

/***************************************************************************************************
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
***************************************************************************************************/
#include<stdio.h>
#include<stdbool.h>

/**
 *严格判定，只要不能正好跳到最后就为false
 */
bool checkRoad(int *indexs,int *visit,int size,int step){
    if(step == size - 1)return true;
    if(step >= size)return false;
    if(visit[step] == 1)return false;
    visit[step] = 1;
    return checkRoad(indexs,visit,size,indexs[step]);
}

bool canJump(int* nums, int numsSize) {
    int *newNums = (int *)malloc(numsSize*sizeof(int));
    for(int i = 0;i < numsSize;i++){
        newNums[i] = nums[i] + i;
    }

        int *visit = (int *)malloc(numsSize*sizeof(int));
        memset(visit,0,numsSize*sizeof(int));
        bool ret = checkRoad(newNums,visit,numsSize,newNums[0]);
    //for(int i = 0);

    free(visit);
    free(newNums);
    return ret;
}

void main(){
    //int nums[] = {2,3,1,1,4};
    //int nums[] = {3,2,1,0,4};
    int nums[] = {3,2,1,3,4};
    printf("%d",canJump(nums,5));
}

如果要求找最小的调数，考虑扩张的思路。

思路如下：

1.首先找起始位能到达的范围是否覆盖了最终位置，并记录下搜索中的最远能到达的位置值，即max{nums[i] + i};

2.如果无法到达最终位置，则跳数加一，并从上一次搜索的最后位置开始，向后搜索到上一次记录的最大值所在的位置。

3.重复上面两步，直到找到最终跳数。

注意：

当数组元素只有1个时，跳数是0；

跳数的初值应该是1。

int jump(vector<int>& nums){
    if (nums.size() < 2)return 0;//数组长度小于2
    int start = 0, next = nums.at(0),end = nums.size() - 1;
    int jump = 1,cur = next;//jump记录跳数，cur记录当前的最大范围
    while (cur < end){
        jump++;
        for (int i = start + 1; i <= next; i++)
        {
            if (nums.at(i) + i >= end)return jump;
            else if (nums.at(i) + i > cur)cur = nums.at(i) + i;
        }
        start = next;//start是搜索的开始位置
        next = cur;//next是搜索的结束位置
    }
    return jump;
}

 

[LeetCode]Jump Game


联系
我们