檢查是否可以透過在給定範圍內選擇跳躍值來到達給定二進位字串的末尾

二進位字串是只包含0和1兩種不同類型字元的字串。給定一個二進位字串和兩個整數L和R。我們可以從字串值為'0'的索引處進行大小在'L'和'R'之間的跳躍，包括'L'和'R'。我們必須從第零個索引開始，找出是否能夠到達最後一個索引。

範例範例

Input1:
string str = “01001110010”
int L = 2, R = 4
Output: Yes, we can reach the last index.

Explanation

的翻譯為：

解釋

我們可以從零索引跳躍三次，然後再跳躍兩次到達4，這樣我們就能到達最終所需的索引。

Input2:
string str = “01001110010”
int L = 2, R = 3
Output: No, we cannot reach the last index. 

Explanation

的翻譯為：

解釋

我們可以進行兩次跳躍，每次跳躍為2或3，如果我們從第0個索引跳躍，我們要么到達第2個索引，要么到達第3個索引，然後我們只能跳到值為'1'的索引，無法再進行進一步的跳躍。

方法一

Idea

的中文翻譯為：

Idea

這個想法是應用動態規劃的概念。我們可以維護一個數組，表示一個位置是否可以到達。

如果我們能夠達到一個位置，那麼接下來的l到r個位置也可以實現。

實作

我們將建立一個函數，該函數將以字串、左位置和右位置作為參數，並傳回布林值。

在這個函數中，我們將遍歷數組，並使用嵌套的for循環遍歷範圍，檢查當前位置減去當前範圍位置是否可達，如果可達，則可以到達該位置。

最終，我們將傳回DP陣列的最後一個索引的狀態，表示最終答案。

Example

的中文翻譯為：

範例

#include <bits/stdc++.h>
using namespace std;
// function to implement the DP concepts 
bool check(string str, int l, int r){
   int len = str.length(); // length of the string     
   vector<int>dp(len); // vector to store the states results 
   
   // Initiating the first index 
   dp[0] = str[0] == '0'; 
   
   // traversing over the array 
   for(int i=1; i<len; i++ ){
      for(int j = l; j <= r ; j++){
         if(i-j < 0){
            break;
         }
         if(str[i-j] == '1' || dp[i-j] == 0){
            continue;
         }
         else{
            dp[i] = 1;
            break;
         }
      }
   }
   return dp[len-1];
}
int main(){
   string str = "01001110010";
   int l = 2, r = 4; 
   
   // calling the function 
   int res = check(str, l, r);    
   if(res > 0){
      cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
   else{
      cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
}

輸出

Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range

時間複雜度與空間複雜度

以上程式碼的時間複雜度為O(N^2)，其中N是給定字串的大小。我們使用了嵌套的for循環，這使得時間複雜度為N^2。

上述程式碼的空間複雜度為O(N)，因為我們使用了長度為N的陣列來儲存DP狀態。

方法二

這種方法是前一個版本的更好版本，在這種方法中，我們將維護一個整數來獲得我們可以進行的跳躍次數。在每次跳躍時，如果可以跳躍，我們可以增加計數，如果在任何位置跳躍不可能，我們可以減少計數。

我們將把資料儲存在DP數組的每個索引中，並稍後使用它。

Example

的中文翻譯為：

範例

#include <bits/stdc++.h>
using namespace std;
bool check(string str, int l, int r){
   int len = str.length(); // length of the string     
   vector<int>dp(len); // vector to store the states results     
   // initiating the first index 
   dp[0] = str[0] == '0';    
   int count = 0; // variable to maintain the count of the jump 
   
   // traversing over the array 
   for(int i=1; i<len; i++ ){
      if (i >= l) {
         count += dp[i - l];
      }
      if (i > r) {
         count -= dp[i -r- 1];
      }
      dp[i] = (count > 0) and (str[i] == '0');
   }
   return dp[len-1];
}

// main function 
int main(){
   string str = "01001110010";
   int l = 2, r = 4;  
   
   // calling the function 
   int res = check(str, l, r);    
   if(res > 0){
      cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   } else {
      cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
}

輸出

Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range

時間複雜度與空間複雜度

上述程式碼的時間複雜度為O(N)，其中N是給定字串的大小。我們使用單一循環遍歷字串使得時間複雜度是線性的。

上述程式碼的空間複雜度為O(N)，因為我們使用了長度為N的陣列來儲存DP狀態。

結論

在本教程中，我們實作了一個程式碼，透過從第一個索引開始，並從給定字串中包含'0'的索引移動給定數量的索引，來判斷我們是否可以到達給定字串的末尾。我們採用了動態規劃的方法，時間複雜度為O(N^2)和O(N)，空間複雜度為O(N)。

以上是檢查是否可以透過在給定範圍內選擇跳躍值來到達給定二進位字串的末尾的詳細內容。更多資訊請關注PHP中文網其他相關文章！