数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学检查能否从给定位置到达数组末尾
在这个问题中，我们将检查是否可以通过从当前位置向前或向后移动 nums[p] 步来到达数组的末尾。
解决这个问题的简单方法是检查所有可能的数组内移动，看看是否可以到达数组的末尾。
另一种方法是使用队列和数组中的 BFS 遍历。在本教程中，我们将学习这两种方法来检查是否可以到达数组的末尾。
问题陈述 - 我们给定一个包含正整数的 nums[] 数组。我们还给定一个 start 值，表示移动的起始索引。我们需要检查是否可以从起始索引执行多次操作后到达给定数组的末尾。在每次操作中，我们可以从当前索引跳转到 curr_index − nums[curr_index] 或 curr_index + nums[curr_index]。
示例
输入
nums[] = {5, 4, 3, 2, 1, 6}, start = 1
输出
Yes
解释 - 当我们从第 1 个索引开始时，我们可以通过从第 1 个索引进行 4 步的跳跃来到达末尾。
输入
nums[] = {5, 0, 3, 2, 1, 6}, start = 1
输出
No
解释 - 起始索引包含 0。因此，我们无法从第 1 个索引移动。
输入
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(2N)，因为我们对每个元素进行两次移动。
空间复杂度 - O(1)，因为我们没有使用任何额外的空间。
方法 2
在这种方法中，我们将使用队列数据结构并在数组中进行 BFS 遍历。此外，我们将使用 vis[] 数组来跟踪已访问的数组元素。我们将把当前位置的每个可能的移动插入到队列中，并以 BFS 的方式进行遍历。
算法
步骤 1 - 定义名为 'que' 的队列数据结构。此外，定义大小为 n 的 vis[] 数组并用布尔值 'false' 初始化。还用 false 初始化 'isEnd' 变量来跟踪我们是否到达末尾。
步骤 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;
}
输出
Yes, we can reach to the end node!
时间复杂度 - O(N)，因为我们只处理每个节点一次。
空间复杂度 - O(N)，用于将节点存储到队列中。
在第一种方法中，我们多次重新访问数组元素，但在第二种方法中，我们只重新访问数组元素一次，这提高了代码的时间复杂度。
77 次查看
