資料結構
網路
關係型資料庫管理系統 (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 次檢視
