Heim Backend-Entwicklung PHP-Tutorial XOR-Abfragen eines Subarrays

XOR-Abfragen eines Subarrays

Sep 13, 2024 pm 10:17 PM

XOR Queries of a Subarray

1310. XOR-Abfragen eines Subarrays

Schwierigkeit:Mittel

Themen: Array, Bitmanipulation, Präfixsumme

Sie erhalten ein Array arr positiver Ganzzahlen. Sie erhalten auch die Array-Abfragen, wobei query[i] = [lefti, righti].

ist

Für jede Abfrage berechne ich das XOR von Elementen von linksi nach rechtsi (das heißt, arr[lefti] XOR arr[lefti 1] XOR ... XOR arr[righti] ).

Gib eine Array-Antwort zurück, wobei Antwort[i] die Antwort auf die iteAbfrage ist.

Beispiel 1:

  • Eingabe: arr = [1,3,4,8], Abfragen = [[0,1],[1,2],[0,3],[3,3]]
  • Ausgabe: [2,7,14,8]
  • Erklärung: Die binäre Darstellung der Elemente im Array ist:
  1 = 0001
  3 = 0011
  4 = 0100
  8 = 1000

Die XOR-Werte für Abfragen sind:

  [0,1] = 1 xor 3 = 2
  [1,2] = 3 xor 4 = 7
  [0,3] = 1 xor 3 xor 4 xor 8 = 14
  [3,3] = 8

Beispiel 2:

  • Eingabe: arr = [4,8,2,10], Abfragen = [[2,3],[1,3],[0,0],[0,3]]
  • Ausgabe: [8,0,4,4]

Einschränkungen:

  • 1 <= arr.length, query.length <= 3 * 104
  • 1 <= arr[i] <= 109
  • queries[i].length == 2
  • 0 <= linksi <= rechtsi < arr.länge

Hinweis:

  1. Was ist das Ergebnis von x ^ y ^ x ?
  2. Berechnen Sie die Präfixsumme für XOR.
  3. Verarbeiten Sie die Abfragen mit den Präfix-Summenwerten.

Lösung:

Wir können die Präfix-XOR-Technik verwenden. So funktioniert es:

Ansatz:

  1. Präfix-XOR-Array: Wir berechnen ein Präfix-XOR-Array, wobei prefix[i] das XOR aller Elemente vom Anfang des Arrays bis zum Index i darstellt. Dadurch können wir das XOR eines beliebigen Subarrays in konstanter Zeit berechnen.

  2. XOR eines Subarrays:

    • Um das XOR von Elementen zwischen den Indizes links und rechts zu berechnen:
      • Wenn links > 0 können wir das XOR von links nach rechts als prefix[right] ^ prefix[left - 1] berechnen.
      • Wenn links == 0, dann ist das Ergebnis einfach Präfix[rechts].

      Dadurch können wir jede Anfrage in konstanter Zeit beantworten, nachdem wir das Präfix-XOR-Array erstellt haben.

      Planen:

      1. Erstellen Sie das Präfix-XOR-Array.
      2. Verwenden Sie für jede Abfrage das Präfix-XOR-Array, um das XOR für den Bereich [left_i, right_i] zu berechnen.

      Lassen Sie uns diese Lösung in PHP implementieren: 1310. XOR-Abfragen eines Subarrays

      <?php
      /**
       * @param Integer[] $arr
       * @param Integer[][] $queries
       * @return Integer[]
       */
      function xorQueries($arr, $queries) {
          ...
          ...
          ...
          /**
           * go to ./solution.php
           */
      }
      
      // Example 1
      $arr1 = [1, 3, 4, 8];
      $queries1 = [[0, 1], [1, 2], [0, 3], [3, 3]];
      print_r(xorQueries($arr1, $queries1)); // Output: [2, 7, 14, 8]
      
      // Example 2
      $arr2 = [4, 8, 2, 10];
      $queries2 = [[2, 3], [1, 3], [0, 0], [0, 3]];
      print_r(xorQueries($arr2, $queries2)); // Output: [8, 0, 4, 4]
      ?>
      

      Erläuterung:

      1. Präfix-XOR-Konstruktion:

        • Das Array-Präfix ist so aufgebaut, dass prefix[i] das XOR aller Elemente von arr[0] bis arr[i] enthält.
        • Wenn beispielsweise arr = [1, 3, 4, 8] ist, lautet das Präfix-Array [1, 1^3, 1^3^4, 1^3^4^8] oder [1, 2 , 6, 14].
      2. Anfragen beantworten:

        • Für jede Abfrage [links, rechts] berechnen wir das XOR des Subarrays arr[links] bis arr[rechts] mit:
          • prefix[right] ^ prefix[left - 1] (wenn left > 0)
          • Präfix[rechts] (wenn links == 0)

      Zeitkomplexität:

      • Aufbau des Präfix-Arrays: O(n), wobei n die Länge des Arrays ist.
      • Verarbeitung der Abfragen: O(q), wobei q die Anzahl der Abfragen ist.
      • Gesamtzeitkomplexität: O(n q), was für die gegebenen Einschränkungen effizient ist.

      Dieser Ansatz stellt sicher, dass wir bis zu 30.000 Abfragen auf einem Array mit einer Größe von bis zu 30.000 effizient bearbeiten können.

      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 vonXOR-Abfragen eines Subarrays. 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

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

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.

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ß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)

Schritte zur Konfiguration einer PHP -Entwicklungsumgebung unter Linux Schritte zur Konfiguration einer PHP -Entwicklungsumgebung unter Linux Jun 30, 2025 am 01:57 AM

TosetupaphpDevelvenvironmentonLinux, InstallPandRequiredEXTENSSSS, SetupawebserverlikeAnginx, testwithaphpFile und optionalinstallmysqlandComposer.1.installphpandextensViaPackagemanager (E. G., SudoaptalphpPhphphphphphphphphphphphphphp-MysqLphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpphpmbphp

Wie kombinieren Sie zwei einzigartige Werte für PHP -Arrays? Wie kombinieren Sie zwei einzigartige Werte für PHP -Arrays? Jul 02, 2025 pm 05:18 PM

Um zwei PHP -Arrays zusammenzuführen und eindeutige Werte zu behalten, gibt es zwei Hauptmethoden. 1. Verwenden Sie für Index -Arrays oder nur Deduplizierung Array_merge und Array_unique -Kombinationen: Zuerst merge array_merge ($ array1, $ array2) und verwenden Sie dann Array_unique (), um sie endgültig zu erhalten, um ein neues Array zu erhalten, das alle eindeutigen Werte enthält. 2. Verwenden Sie für assoziative Arrays und möchten im ersten Array Schlüsselwertepaare beibehalten: $ result = $ array1 $ array2, was sicherstellt, dass die Schlüssel im ersten Array vom zweiten Array nicht überschrieben werden. Diese beiden Methoden gelten für verschiedene Szenarien, je nachdem, ob der Schlüsselname beibehalten wird oder nur der Fokus liegt

PHP Regex für Passwortstärke PHP Regex für Passwortstärke Jul 03, 2025 am 10:33 AM

Um die Stärke des Kennworts zu bestimmen, muss die regelmäßige und logische Verarbeitung kombiniert werden. Die grundlegenden Anforderungen umfassen: 1. Die Länge beträgt mindestens 8 Ziffern; 2. Enthaltende Kleinbuchstaben, Großbuchstaben und Zahlen; 3.. Spezielle Charakterbeschränkungen können hinzugefügt werden; In Bezug auf fortgeschrittene Aspekte müssen eine kontinuierliche Vervielfältigung von Zeichen und inkrementelle/abnehmende Sequenzen vermieden werden, was eine PHP -Funktionserkennung erfordert. Gleichzeitig sollten Blacklists vorgestellt werden, um gemeinsame schwache Passwörter wie Passwort und 123456 zu filtern. Schließlich wird empfohlen, die ZXCVBN -Bibliothek zu kombinieren, um die Bewertungsgenauigkeit zu verbessern.

Wie behandle ich Datei -Uploads sicher in PHP? Wie behandle ich Datei -Uploads sicher in PHP? Jul 08, 2025 am 02:37 AM

Um PHP -Datei -Uploads sicher zu verarbeiten, müssen Sie die Quelle und die Type und die Eingabe des Dateinamens und des Pfades überprüfen, Serverbeschränkungen festlegen und Mediendateien zweimal verarbeiten. 1. Überprüfen Sie die Upload -Quelle, um CSRF durch Token zu verhindern, und erkennen Sie den realen MIME -Typ über die Finfo_file mithilfe der Whitelist -Steuerung. 2. Benennen Sie die Datei in eine zufällige Zeichenfolge um und bestimmen Sie die Erweiterung, um sie gemäß dem Erkennungstyp in einem Verzeichnis ohne Web zu speichern. 3. Die PHP -Konfiguration begrenzt die Hochladengröße und das temporäre Verzeichnis Nginx/Apache verbietet den Zugriff auf das Upload -Verzeichnis. 4. Die GD -Bibliothek stellt die Bilder neu, um potenzielle böswillige Daten zu löschen.

Variabler PHP -Bereich erklärt Variabler PHP -Bereich erklärt Jul 17, 2025 am 04:16 AM

Häufige Probleme und Lösungen für den variablen PHP -Umfang umfassen: 1. Die globale Variable kann innerhalb der Funktion nicht zugegriffen werden, und sie muss bei der Verwendung des globalen Schlüsselworts oder Parameters übergeben werden. 2. Die statische Variable wird statisch deklariert und nur einmal initialisiert und der Wert wird zwischen mehreren Aufrufen beibehalten. 3.. Hyperglobale Variablen wie $ _get und $ _post können direkt in jedem Bereich verwendet werden, aber Sie müssen auf eine sichere Filterung achten. 4. Die anonymen Funktionen müssen über das Schlüsselwort verwenden, und wenn Sie externe Variablen ändern, müssen Sie eine Referenz übergeben. Das Beherrschen dieser Regeln kann dazu beitragen, Fehler zu vermeiden und die Code -Stabilität zu verbessern.

Code in PHP aus dem Code ausgehen Code in PHP aus dem Code ausgehen Jul 18, 2025 am 04:57 AM

Es gibt drei gängige Methoden für den PHP -Kommentarcode: 1. Verwenden Sie // oder #, um eine Codezeile zu blockieren, und es wird empfohlen, // zu verwenden. 2. Verwenden Sie /.../, um Codeblöcke mit mehreren Zeilen zu wickeln, die nicht verschachtelt werden können, aber gekreuzt werden können. 3.. Kombinationskenntnisse Kommentare wie die Verwendung / if () {} / Um Logikblöcke zu steuern oder um die Effizienz mit Editor -Verknüpfungsschlüssel zu verbessern, sollten Sie auf die Schließung von Symbolen achten und das Verschachteln bei der Verwendung vermeiden.

Tipps zum Schreiben von PHP -Kommentaren Tipps zum Schreiben von PHP -Kommentaren Jul 18, 2025 am 04:51 AM

Der Schlüssel zum Schreiben von PHP -Kommentaren liegt in der Klärung des Zwecks und der Spezifikationen. Kommentare sollten "Warum" und nicht "was getan" erklären, um Redundanz oder zu Einfachheit zu vermeiden. 1. Verwenden Sie ein einheitliches Format wie Docblock (/*/) für Klassen- und Methodenbeschreibungen, um die Lesbarkeit und die Kompatibilität der Werkzeuge zu verbessern. 2. Betonen Sie die Gründe für die Logik, z. B. warum JS -Sprünge manuell ausgeben müssen. 3. Fügen Sie eine Übersichtsbeschreibung vor komplexem Code hinzu, beschreiben Sie den Prozess in Schritten und helfen Sie, die Gesamtidee zu verstehen. V. Gute Anmerkungen können die Kommunikationskosten senken und die Effizienz der Code -Wartung verbessern.

Wie arbeiten Generatoren in PHP? Wie arbeiten Generatoren in PHP? Jul 11, 2025 am 03:12 AM

AgneeratorinphpiSamemory-effizientes WaytoiterateOverlargedatasetsByyieldingValueatimeinsteadofReturningThemallatonce.1.GeneratorsusetheyieldKeywordtoproduktenvaluesonDemand, ReducingMemoryUsage.2.TheyareusefulforfulforfulfordlingBiglopploups, Lesebiglochen, Leselungen, Lesebigs, Leselung, oder

See all articles