Überprüft, ob das Ende einer bestimmten Binärzeichenfolge erreicht werden kann, indem ein Sprungwert innerhalb des angegebenen Bereichs ausgewählt wird

Eine binäre Zeichenfolge ist eine Zeichenfolge, die nur zwei verschiedene Arten von Zeichen enthält, 0 und 1. Gegeben sei eine Binärzeichenfolge und zwei ganze Zahlen L und R. Wir können einen Größensprung zwischen „L“ und „R“ (einschließlich) von dem Index aus machen, bei dem der String-Wert „0“ ist. Wir müssen beim nullten Index beginnen und herausfinden, ob wir den letzten Index erreichen können.

Beispiel Beispiel

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

Erklärung

wird übersetzt als:

Erklärung

Wir können dreimal vom Index Null und dann zwei weitere Sprünge bis zum Index 4 springen, um zum endgültigen gewünschten Index zu gelangen.

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

Erklärung

wird übersetzt als:

Erklärung

Wir können zwei Sprünge machen, jeder Sprung ist 2 oder 3, wenn wir vom 0. Index springen, erreichen wir entweder den 2. Index oder den 3. Index, dann können wir nur zum Indexwert „1“ springen, es können keine weiteren Sprünge gemacht werden.

Methode 1

Die chinesische Übersetzung von

Idee

lautet:

Idee

Die Idee besteht darin, das Konzept der dynamischen Programmierung anzuwenden. Wir können ein Array verwalten, das angibt, ob ein Standort erreichbar ist.

Wenn wir eine Position erreichen können, können auch die nächsten Positionen von links nach rechts erreicht werden.

Umsetzung

Wir erstellen eine Funktion, die eine Zeichenfolge, eine linke Position und eine rechte Position als Parameter akzeptiert und einen booleschen Wert zurückgibt.

In dieser Funktion durchlaufen wir das Array und verwenden eine verschachtelte for-Schleife, um den Bereich zu durchlaufen. Überprüfen Sie, ob die aktuelle Position minus der aktuellen Bereichsposition erreichbar ist. Wenn sie erreichbar ist, kann die Position erreicht werden.

Schließlich geben wir den Status des letzten Index des DP-Arrays zurück, der die endgültige Antwort darstellt.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

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

Ausgabe

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

Zeitkomplexität und Raumkomplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N^2), wobei N die Größe der angegebenen Zeichenfolge ist. Wir verwendeten verschachtelte for-Schleifen, was zu einer zeitlichen Komplexität von N^2 führte.

Die räumliche Komplexität des obigen Codes beträgt O(N), da wir ein Array der Länge N verwenden, um den DP-Status zu speichern.

Methode 2

Diese Methode ist eine bessere Version der vorherigen. Bei dieser Methode behalten wir eine Ganzzahl bei, um die Anzahl der Sprünge zu ermitteln, die wir machen können. Bei jedem Sprung können wir die Anzahl erhöhen, wenn der Sprung möglich ist, und die Anzahl verringern, wenn der Sprung an keiner Stelle möglich ist.

Wir werden die Daten in jedem Index des DP-Arrays speichern und später verwenden.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

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

Ausgabe

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

Zeitkomplexität und Raumkomplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N die Größe der angegebenen Zeichenfolge ist. Wir verwenden eine einzelne Schleife, um die Zeichenfolge zu durchlaufen, sodass die zeitliche Komplexität linear ist.

Die räumliche Komplexität des obigen Codes beträgt O(N), da wir ein Array der Länge N verwenden, um den DP-Status zu speichern.

Fazit

In diesem Tutorial haben wir einen Code implementiert, der bestimmt, ob wir eine bestimmte Zeichenfolge erreichen können, indem wir beim ersten Index beginnen und eine bestimmte Anzahl von Indizes aus dem Index verschieben, der am Ende der angegebenen Zeichenfolge „0“ enthält. Wir haben die dynamische Programmiermethode übernommen, die zeitliche Komplexität beträgt O(N^2) und O(N) und die räumliche Komplexität beträgt O(N).

Das obige ist der detaillierte Inhalt vonÜberprüft, ob das Ende einer bestimmten Binärzeichenfolge erreicht werden kann, indem ein Sprungwert innerhalb des angegebenen Bereichs ausgewählt wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!