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

---

二進位制字串是指只包含兩種不同字元（0 和 1）的字串。給定一個二進位制字串和兩個整數 L 和 R。我們可以在長度為 ‘L’ 和 ‘R’（包括兩者）之間進行跳躍，並且只能從字串值為 ‘0’ 的索引處跳躍。我們必須從第零個索引開始，並找出我們是否可以到達最後一個索引。

示例

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

解釋

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

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

解釋

我們可以跳躍兩次，每次跳躍 2 或 3 步。如果我們從第零個索引跳躍，我們將到達第 2 個或第 3 個索引，從那裡我們只能到達值為 ‘1’ 的索引，並且無法再進行跳躍。

方法 1

思路

思路是應用動態規劃的概念。我們可以維護一個數組，該陣列指示某個位置是否可以到達。

如果我們可以到達某個位置，那麼接下來 l 到 r 個位置也可以到達。

實現

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

在函式中，我們將遍歷陣列，並使用巢狀迴圈遍歷範圍，並檢查當前位置減去當前範圍位置是否可達，然後我們也可以到達此位置。

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

示例

#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 是給定字串的大小。我們使用巢狀迴圈，這使得時間複雜度為 N^2。

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

方法 2

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

我們將儲存 DP 陣列中每個索引處的資料，並稍後使用它。

示例

#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) 空間複雜度的動態規劃方法。