Vérifie si la fin d'une chaîne binaire donnée peut être atteinte en sélectionnant une valeur de saut dans la plage donnée

Une chaîne binaire est une chaîne contenant uniquement deux types de caractères différents, 0 et 1. Étant donné une chaîne binaire et deux entiers L et R. Nous pouvons faire un saut de taille entre 'L' et 'R' inclus, à partir de l'index où la valeur de la chaîne est '0'. Il faut repartir de l'indice zéro et découvrir si l'on peut atteindre le dernier indice.

Exemple Exemple

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

Explication

se traduit par :

Explication

Nous pouvons sauter trois fois de l'indice zéro puis deux autres sauts à 4 pour arriver à l'indice final souhaité.

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

Explication

se traduit par :

Explication

Nous pouvons faire deux sauts, chaque saut est 2 ou 3, si nous sautons du 0ème indice, nous atteignons soit le 2ème indice, soit le 3ème indice, alors nous ne pouvons sauter qu'à la valeur '1' de l'indice, aucun autre saut ne peut être fait.

Méthode 1

La traduction chinoise de

Idea

est :

Idea

L'idée est d'appliquer le concept de programmation dynamique. Nous pouvons maintenir un tableau indiquant si un emplacement est accessible.

Si nous pouvons atteindre une position, alors les positions suivantes de gauche à droite peuvent également être atteintes.

Mise en œuvre

Nous allons créer une fonction qui prendra une chaîne, une position à gauche et une position à droite comme paramètres et renverra une valeur booléenne.

Dans cette fonction, nous allons parcourir le tableau et utiliser une boucle for imbriquée pour parcourir la plage, vérifier si la position actuelle moins la position actuelle de la plage est accessible, si elle est accessible, alors la position peut être atteinte.

Finalement, nous renverrons le statut du dernier index du tableau DP, représentant la réponse finale.

La traduction chinoise de

Exemple

est :

Exemple

#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;
   }
}

Sortie

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

Complexité temporelle et complexité spatiale

La complexité temporelle du code ci-dessus est O(N^2), où N est la taille de la chaîne donnée. Nous avons utilisé des boucles for imbriquées, ce qui a abouti à une complexité temporelle de N ^ 2.

La complexité spatiale du code ci-dessus est O(N) car nous utilisons un tableau de longueur N pour stocker l'état DP.

Méthode 2

Cette méthode est une meilleure version de la précédente, dans cette méthode nous maintiendrons un nombre entier pour obtenir le nombre de sauts que nous pouvons faire. À chaque saut, nous pouvons incrémenter le décompte si le saut est possible, et décrémenter le décompte si le saut n'est possible à aucun endroit.

Nous stockerons les données dans chaque index du tableau DP et les utiliserons plus tard.

La traduction chinoise de

Exemple

est :

Exemple

#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;
   }
}

Sortie

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

Complexité temporelle et complexité spatiale

La complexité temporelle du code ci-dessus est O(N), où N est la taille de la chaîne donnée. Nous utilisons une seule boucle pour parcourir la chaîne afin que la complexité temporelle soit linéaire.

La complexité spatiale du code ci-dessus est O(N) car nous utilisons un tableau de longueur N pour stocker l'état DP.

Conclusion

Dans ce tutoriel, nous avons implémenté un code qui détermine si nous pouvons atteindre une chaîne donnée en commençant par le premier index et en déplaçant un nombre donné d'index à partir de l'index contenant « 0 » dans la chaîne donnée à la fin de. Nous avons adopté la méthode de programmation dynamique, la complexité temporelle est O(N^2) et O(N), et la complexité spatiale est O(N).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!