C++ 检查从给定位置是否可以达到数组的末尾

在这个问题中，我们将检查是否可以通过从当前位置向后或向前移动nums[p]个位置来达到数组的末尾。

解决这个问题的朴素方法是检查所有移动到数组中的可能性，并看是否可以达到数组的末尾。

另一种方法是使用队列和BFS遍历数组。在本教程中，我们将学习两种方法来检查是否可以到达数组的末尾。

问题陈述 - 我们有一个包含正整数的nums[]数组。还有一个起始值，表示移动的起始索引。我们需要检查是否可以从起始索引执行多个操作后到达给定数组的末尾。在每个操作中，我们可以从当前索引跳到curr_index − nums[curr_index]或curr_index + nums[curr_index]。

示例

输入

nums[] = {5, 4, 3, 2, 1, 6}, start = 1

输出

Yes

解释 − 当我们从第一个索引开始时，我们可以通过从m1st索引跳跃4个单位来到达末尾。

输入

nums[] = {5, 0, 3, 2, 1, 6}, start = 1

输出

No

解释 - 开始索引为0。所以，我们不能从第一个索引移动。

输入

nums[] = {6, 5, 3, 2, 1, 4, 7}; start = 2;

输出

Yes

说明 - 我们可以按照以下步骤进行操作。

从第2个索引开始，我们可以到达第(2 + 3) 5个索引。
从第5个索引开始，我们可以向后移动并到达第(5 – 4), 1个索引。
从第1个索引开始，我们可以直接移动到数组的末尾。

方法1

这种方法使用递归函数来解决问题。我们将使用递归函数检查所有可能的移动方式。如果我们可以在任何移动中到达数组的末尾，我们将打印Yes。否则，我们将打印No。

步骤

步骤1 - 如果起始索引小于0或大于N，则返回false。

步骤2 - 如果起始索引等于N – 1，则返回true。

步骤3 - 如果当前索引处的元素为0，则返回false。

步骤4 - 对当前位置进行递归函数调用，向后或向前移动。

步骤5 - 取两个递归函数调用的返回值的OR操作，并从当前函数调用返回。

示例

#include <bits/stdc++.h>
using namespace std;

bool reachToEnd(int nums[], int N, int start) {
    if (start < 0 || start > N) {
        return false;
    }
    // When we reach at the end
    if (start == N - 1) {
        return true;
    }
    // When we can't move from the current position
    if (nums[start] == 0) {
        return false;
    }
    return reachToEnd(nums, N, start - nums[start]) || reachToEnd(nums, N, start + nums[start]);
}
int main(){
    int nums[] = {5, 4, 3, 2, 1, 6};
    int start = 1;
    int N = sizeof(nums) / sizeof(nums[0]);
    bool res = reachToEnd(nums, N, start);
    if(res) {
        cout << "Yes, we can reach to the end node!";
    } else {
        cout << "No, we can't reach to the end node!";
    }
    return 0;
}

输出

Yes, we can reach to the end node!

时间复杂度 – O(2 N )，因为我们每个元素进行两次移动。

空间复杂度 – O(1)，因为我们不使用任何额外的空间。

方法2

在这种方法中，我们将使用队列数据结构，并对数组进行BFS遍历。同时，我们将使用vis[]数组来跟踪已访问的数组元素。我们将每个可能的移动从当前位置插入队列，并以BFS方式遍历。

步骤

第1步 - 定义名为”que”的队列数据结构。同时，定义大小为n的vis[]数组，并初始化为”false”布尔值。同时，将”isEnd”变量初始化为false，以便跟踪是否到达终点。

第2步 - 将起始索引插入队列中。

第3步 - 使用while循环进行迭代，直到队列为空。

第4步 - 从队列中取出第一个元素，并将其存储在”temp”变量中。如果vis[temp]为true，则继续下一次迭代。否则，将vis[temp]设为true。

第5步 - 如果temp等于n-1，则将”isEnd”更新为true，并使用break关键字跳出循环。

第6步 - 如果temp + nums[temp]小于N，则将其插入队列。

第7步 - 如果temp – nums[temp]大于或等于-1，则将其插入队列。

第8步 - 在循环迭代完成后，根据”isEnd”值打印输出。

示例

#include <bits/stdc++.h>
using namespace std;

void reachToEnd(int nums[], int n, int start) {
    queue<int> que;
    // Make all nodes as not visited
    bool vis[n] = {false};
    // To track whether we reached at the end
    bool isEnd = false;
    que.push(start);
    while (!que.empty()) {
        int temp = que.front();
        que.pop();
        // When the node is visited
        if (vis[temp] == true)
            continue;
        // Mark the current node as visited
        vis[temp] = true;
        // When we reach at the end
        if (temp == n - 1) {
            isEnd = true;
            break;
        }
        // Check the possibility to reach
        if (temp + nums[temp] < n) {
            que.push(temp + nums[temp]);
        }
        if (temp - nums[temp] >= 0) {
            que.push(temp - nums[temp]);
        }
    }
    if (isEnd == true) {
        cout <<"Yes, we can reach to the end node!";
    } else {
        cout << "No, we can't reach to the end node!";
    }
}
int main() {
    // Given array arr[]
    int nums[] = {5, 4, 3, 2, 1, 6};
    int start = 1;
    int N = sizeof(nums) / sizeof(nums[0]);
    reachToEnd(nums, N, start);
    return 0;
}