C++ 检查给定二进制字符串的结尾是否可以通过选择给定范围内的跳跃值来达到

二进制字符串是一个只包含0和1两种不同类型字符的字符串。给定一个二进制字符串和两个整数L和R。我们可以从字符串值为0的索引处，以 ‚ÄòL‚Äô 和 ‚ÄòR‚Äô 的跳跃长度之间（包括两个边界）进行跳跃。我们必须从索引为0的位置开始，判断是否能够到达最后一个索引。

示例

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

解释

我们可以从零索引点跳3次，然后跳两次到4，这样我们就可以达到最后需要的索引。

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

解释

我们可以跳两步，也可以跳三步，如果我们从第零个索引跳跃，我们只能到达第二个或第三个索引，从那里我们只能跳到值为1的索引，不能再进行进一步的跳跃。

方法1

思路

思路是应用动态规划的概念。我们可以维护一个数组，表示某个位置是否可达。

如果我们可以到达某个位置，则后面的l到r个位置也可以到达。

实现

我们将创建一个函数，函数将接受字符串、左位置和右位置作为参数，并返回布尔值。

在函数中，我们将遍历数组，并使用嵌套的for循环遍历范围，检查当前位置减去当前范围位置是否可达，如果可达，则我们也可以到达该位置。

最后，我们将返回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是给定字符串的长度。我们使用了嵌套的for循环，这使得时间复杂度为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)空间复杂度的动态规划方法。