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.
Input1: string str = “01001110010” int L = 2, R = 4 Output: Yes, we can reach the last index.
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.
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.
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.
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
#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
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.
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#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
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.
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!
Wie man Bilder in ppt scrollen lässt
Eine vollständige Liste häufig verwendeter öffentlicher DNS
Der Unterschied zwischen Git und SVN
Nutzung der Bodenfunktion
Was beinhalten E-Commerce-Plattformen?
Datenbank-Er-Diagramm
Methoden zur Verhinderung von CC-Angriffen
So konfigurieren Sie JDK-Umgebungsvariablen
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
