Heim Backend-Entwicklung PHP-Tutorial Machen Sie einen String mithilfe zyklischer Inkremente zu einer Teilsequenz

Machen Sie einen String mithilfe zyklischer Inkremente zu einer Teilsequenz

Dec 08, 2024 pm 01:29 PM

Make String a Subsequence Using Cyclic Increments

2825. Machen Sie String mithilfe zyklischer Inkremente zu einer Teilsequenz

Schwierigkeit:Mittel

Themen:Zwei Zeiger, String

Sie erhalten zwei 0-indizierte Zeichenfolgen str1 und str2.

In einer Operation wählen Sie einen Satz von Indizes in str1 aus und erhöhen für jeden Index i im Satz str1[i] zyklisch zum nächsten Zeichen. Das heißt, „a“ wird zu „b“, „b“ wird zu „c“ usw. und „z“ wird zu „a“.

Gib true zurück, wenn es möglich ist, str2 zu einer Teilfolge von str1 zu machen, indem die Operation höchstens einmal ausgeführt wird, andernfalls false.

Hinweis: Eine Teilfolge einer Zeichenfolge ist eine neue Zeichenfolge, die aus der ursprünglichen Zeichenfolge gebildet wird, indem einige (möglicherweise keine) der Zeichen gelöscht werden, ohne die relativen Positionen der verbleibenden Zeichen zu beeinträchtigen.

Beispiel 1:

  • Eingabe: str1 = „abc“, str2 = „ad“
  • Ausgabe:wahr
  • Erklärung: Wählen Sie Index 2 in str1 aus.
    • Str1[2] erhöhen, um zu „d“ zu werden.
    • Daher wird str1 zu „abd“ und str2 ist jetzt eine Teilsequenz. Daher wird true zurückgegeben.

Beispiel 2:

  • Eingabe: str1 = "zc", str2 = "ad"
  • Ausgabe:wahr
  • Erklärung: Wählen Sie die Indizes 0 und 1 in str1 aus.
    • Str1[0] erhöhen, um zu „a“ zu werden.
    • Str1[1] erhöhen, um zu „d“ zu werden.
    • Daher wird str1 zu „ad“ und str2 ist jetzt eine Teilsequenz. Daher wird true zurückgegeben.

Beispiel 3:

  • Eingabe: str1 = „ab“, str2 = „d“
  • Ausgabe:false
  • Erklärung: In diesem Beispiel kann gezeigt werden, dass es unmöglich ist, str2 mit der Operation höchstens einmal zu einer Teilfolge von str1 zu machen.
    • Daher wird false zurückgegeben.

Einschränkungen:

  • 1 <= str1.length <= 105
  • 1 <= str2.length <= 105
  • str1 und str2 bestehen nur aus englischen Kleinbuchstaben.

Hinweis:

  1. Berücksichtigen Sie die Indizes, die wir separat erhöhen werden.
  2. Wir können zwei Zeiger beibehalten: Zeiger i für str1 und Zeiger j für str2, wobei wir sicherstellen, dass sie innerhalb der Grenzen der Zeichenfolgen bleiben.
  3. Wenn sowohl str1[i] als auch str2[j] übereinstimmen oder wenn das Erhöhen von str1[i] mit str2[j] übereinstimmt, erhöhen wir beide Zeiger; andernfalls erhöhen wir nur den Zeiger i.
  4. Es ist möglich, str2 zu einer Teilfolge von str1 zu machen, wenn j am Ende von str2 steht, nachdem wir keine Übereinstimmung mehr finden können.

Lösung:

Wir müssen prüfen, ob wir str2 zu einer Teilfolge von str1 machen können, indem wir höchstens eine zyklische Inkrementierungsoperation für alle Zeichen in str1 durchführen:

Erläuterung:

  • Wir werden zwei Zeiger verwenden, i für str1 und j für str2.
  • Wenn das Zeichen bei str1[i] mit str2[j] übereinstimmt, bewegen wir beide Zeiger nach vorne.
  • Wenn str1[i] erhöht werden kann, um mit str2[j] übereinzustimmen (zyklisch), versuchen wir, sie anzupassen und dann beide Zeiger zu verschieben.
  • Wenn keine der oben genannten Bedingungen zutrifft, bewegen wir nur den Zeiger i für str1.
  • Wenn wir schließlich alle Zeichen von str2 abgleichen können, ist es möglich, str2 zu einer Teilfolge von str1 zu machen, andernfalls nicht.

Lassen Sie uns diese Lösung in PHP implementieren: 2825. Machen Sie einen String mithilfe zyklischer Inkremente zu einer Teilsequenz






Erläuterung:

  1. Zwei Zeiger: i und j werden auf den Anfang von str1 bzw. str2 initialisiert.
  2. Matching-Logik: Innerhalb der Schleife prüfen wir, ob die Zeichen bei str1[i] und str2[j] gleich sind oder ob wir str1[i] zyklisch erhöhen können, um mit str2[j] übereinzustimmen.
    • Die zyklische Inkrementierungsbedingung wird mit (ord($str1[$i]) 1 - ord('a')) % 26 behandelt, das prüft, ob str1[i] inkrementiert werden kann, um mit str2[j] übereinzustimmen.
  3. Teilsequenzprüfung: Wenn wir str2 vollständig durchlaufen haben (d. h. j == m), bedeutet dies, dass str2 eine Teilfolge von str1 ist. Sonst ist es das nicht.

Zeitkomplexität:

  • Der Algorithmus durchläuft str1 einmal und jedes Zeichen in str2 wird nur einmal überprüft, sodass die zeitliche Komplexität O(n) beträgt, wobei n die Länge von str1 ist.

Raumkomplexität:

  • Die Raumkomplexität ist O(1), da wir nur wenige Zeiger verwenden und keinen zusätzlichen Raum benötigen, der von der Eingabegröße abhängt.

Diese Lösung prüft effizient, ob es möglich ist, str2 mit höchstens einer zyklischen Inkrementierungsoperation zu einer Teilfolge von str1 zu machen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

  • LinkedIn
  • GitHub

Das obige ist der detaillierte Inhalt vonMachen Sie einen String mithilfe zyklischer Inkremente zu einer Teilsequenz. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

Video Face Swap

Video Face Swap

Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heißer Artikel

<🎜>: Bubble Gum Simulator Infinity - So erhalten und verwenden Sie Royal Keys
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Nordhold: Fusionssystem, erklärt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Mandragora: Flüstern des Hexenbaum
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

Java-Tutorial
1672
14
PHP-Tutorial
1276
29
C#-Tutorial
1256
24
Erklären Sie sicheres Kennwort -Hashing in PHP (z. B. password_hash, password_verify). Warum nicht MD5 oder SHA1 verwenden? Erklären Sie sicheres Kennwort -Hashing in PHP (z. B. password_hash, password_verify). Warum nicht MD5 oder SHA1 verwenden? Apr 17, 2025 am 12:06 AM

In PHP sollten die Funktionen für Passwort_Hash und passwart_verify verwendet werden, um sicheres Passwort -Hashing zu implementieren, und MD5 oder SHA1 sollte nicht verwendet werden. 1) Passwort_hash generiert einen Hash, der Salzwerte enthält, um die Sicherheit zu verbessern. 2) Passwort_Verify prüfen Sie das Passwort und sicherstellen Sie die Sicherheit, indem Sie die Hash -Werte vergleichen. 3) MD5 und SHA1 sind anfällig und fehlen Salzwerte und sind nicht für die Sicherheit der modernen Passwort geeignet.

Wie funktioniert der Php -Typ -Hinweis, einschließlich Skalartypen, Rückgabetypen, Gewerkschaftstypen und nullbaren Typen? Wie funktioniert der Php -Typ -Hinweis, einschließlich Skalartypen, Rückgabetypen, Gewerkschaftstypen und nullbaren Typen? Apr 17, 2025 am 12:25 AM

PHP -Typ -Eingabeaufforderungen zur Verbesserung der Codequalität und der Lesbarkeit. 1) Tipps zum Skalartyp: Da Php7.0 in den Funktionsparametern wie int, float usw. angegeben werden dürfen. 3) Eingabeaufforderung für Gewerkschaftstyp: Da Php8.0 in Funktionsparametern oder Rückgabetypen angegeben werden dürfen. 4) Nullierstyp Eingabeaufforderung: Ermöglicht die Einbeziehung von Nullwerten und Handlungsfunktionen, die Nullwerte zurückgeben können.

PHP und Python: Verschiedene Paradigmen erklärt PHP und Python: Verschiedene Paradigmen erklärt Apr 18, 2025 am 12:26 AM

PHP ist hauptsächlich prozedurale Programmierung, unterstützt aber auch die objektorientierte Programmierung (OOP). Python unterstützt eine Vielzahl von Paradigmen, einschließlich OOP, funktionaler und prozeduraler Programmierung. PHP ist für die Webentwicklung geeignet, und Python eignet sich für eine Vielzahl von Anwendungen wie Datenanalyse und maschinelles Lernen.

Wie verhindern Sie die SQL -Injektion in PHP? (Vorbereitete Aussagen, PDO) Wie verhindern Sie die SQL -Injektion in PHP? (Vorbereitete Aussagen, PDO) Apr 15, 2025 am 12:15 AM

Die Verwendung von Vorverarbeitungsanweisungen und PDO in PHP kann SQL -Injektionsangriffe effektiv verhindern. 1) Verwenden Sie PDO, um eine Verbindung zur Datenbank herzustellen und den Fehlermodus festzulegen. 2) Erstellen Sie Vorverarbeitungsanweisungen über die Vorbereitungsmethode und übergeben Sie Daten mit Platzhaltern und führen Sie Methoden aus. 3) Abfrageergebnisse verarbeiten und die Sicherheit und Leistung des Codes sicherstellen.

PHP und Python: Code Beispiele und Vergleich PHP und Python: Code Beispiele und Vergleich Apr 15, 2025 am 12:07 AM

PHP und Python haben ihre eigenen Vor- und Nachteile, und die Wahl hängt von den Projektbedürfnissen und persönlichen Vorlieben ab. 1.PHP eignet sich für eine schnelle Entwicklung und Wartung großer Webanwendungen. 2. Python dominiert das Gebiet der Datenwissenschaft und des maschinellen Lernens.

PHP: Datenbanken und serverseitige Logik bearbeiten PHP: Datenbanken und serverseitige Logik bearbeiten Apr 15, 2025 am 12:15 AM

PHP verwendet MySQLI- und PDO-Erweiterungen, um in Datenbankvorgängen und serverseitiger Logikverarbeitung zu interagieren und die serverseitige Logik durch Funktionen wie Sitzungsverwaltung zu verarbeiten. 1) Verwenden Sie MySQLI oder PDO, um eine Verbindung zur Datenbank herzustellen und SQL -Abfragen auszuführen. 2) Behandeln Sie HTTP -Anforderungen und Benutzerstatus über Sitzungsverwaltung und andere Funktionen. 3) Verwenden Sie Transaktionen, um die Atomizität von Datenbankvorgängen sicherzustellen. 4) Verhindern Sie die SQL -Injektion, verwenden Sie Ausnahmebehandlung und Schließen von Verbindungen zum Debuggen. 5) Optimieren Sie die Leistung durch Indexierung und Cache, schreiben Sie hochlesbarer Code und führen Sie die Fehlerbehandlung durch.

Zweck von PHP: Erstellen dynamischer Websites Zweck von PHP: Erstellen dynamischer Websites Apr 15, 2025 am 12:18 AM

PHP wird verwendet, um dynamische Websites zu erstellen. Zu den Kernfunktionen gehören: 1. Dynamische Inhalte generieren und Webseiten in Echtzeit generieren, indem Sie eine Verbindung mit der Datenbank herstellen; 2. Verarbeiten Sie Benutzerinteraktions- und Formulareinreichungen, überprüfen Sie Eingaben und reagieren Sie auf Operationen. 3. Verwalten Sie Sitzungen und Benutzerauthentifizierung, um eine personalisierte Erfahrung zu bieten. 4. Optimieren Sie die Leistung und befolgen Sie die Best Practices, um die Effizienz und Sicherheit der Website zu verbessern.

Wählen Sie zwischen PHP und Python: Ein Leitfaden Wählen Sie zwischen PHP und Python: Ein Leitfaden Apr 18, 2025 am 12:24 AM

PHP eignet sich für Webentwicklung und schnelles Prototyping, und Python eignet sich für Datenwissenschaft und maschinelles Lernen. 1.PHP wird für die dynamische Webentwicklung verwendet, mit einfacher Syntax und für schnelle Entwicklung geeignet. 2. Python hat eine kurze Syntax, ist für mehrere Felder geeignet und ein starkes Bibliotheksökosystem.

See all articles