cari
Rumahpembangunan bahagian belakangtutorial phpXOR Maksimum untuk Setiap Pertanyaan

Maximum XOR for Each Query

1829. XOR Maksimum untuk Setiap Pertanyaan

Kesukaran: Sederhana

Topik: Tatasusunan, Manipulasi Bit, Jumlah Awalan

Anda diberi diisih nombor tatasusunan bagi n integer bukan negatif dan integer maximumBit. Anda mahu melaksanakan pertanyaan berikut n kali:

  • Cari integer bukan negatif k maximumBit supaya nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k ialah maksimum. k ialah jawapan kepada pertanyaan ith.
  • Alih keluar elemen terakhir daripada nombor tatasusunan semasa.

Kembalikan jawapan tatasusunan, dengan jawapan[i] ialah jawapan kepada pertanyaan ike.

Contoh 1:

  • Input: nums = [0,1,1,3], maximumBit = 2
  • Output: [0,3,2,3]
  • Penjelasan: Pertanyaan dijawab seperti berikut:
    • 1stpertanyaan pertama: nums = [0,1,1,3], k = 0 sejak 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
    • 2nd pertanyaan: nums = [0,1,1], k = 3 sejak 0 XOR 1 XOR 1 XOR 3 = 3.
    • 3rd pertanyaan: nums = [0,1], k = 2 sejak 0 XOR 1 XOR 2 = 3.
    • 4th pertanyaan: nums = [0], k = 3 sejak 0 XOR 3 = 3.

Contoh 2:

  • Input: nums = [2,3,4,7], maximumBit = 3
  • Output: [5,2,6,5]
  • Penjelasan: Pertanyaan dijawab seperti berikut:
    • 1stpertanyaan pertama: nums = [2,3,4,7], k = 5 sejak 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
    • 2nd pertanyaan: nums = [2,3,4], k = 2 sejak 2 XOR 3 XOR 4 XOR 2 = 7.
    • 3rd pertanyaan: nums = [2,3], k = 6 sejak 2 XOR 3 XOR 6 = 7.
    • 4th pertanyaan: nums = [2], k = 5 sejak 2 XOR 5 = 7.

Contoh 3:

  • Input: nombor = [0,1,2,2,5,7], maksimumBit = 3
  • Output: [4,3,6,4,6,7]

Kekangan:

  • bilangan panjang == n
  • 1 5
  • 1
  • 0 maksimumBit
  • nums​​​ diisih dalam susunan menaik.

Petunjuk:

  1. Perhatikan bahawa keputusan XOR maksimum yang mungkin adalah sentiasa 2(Bit maksimum) - 1
  2. Jadi jawapan untuk awalan ialah XOR awalan itu XORed dengan 2(maksimumBit)-1

Penyelesaian:

Kita perlu mengira XOR unsur dalam tatasusunan dengan cekap dan memaksimumkan hasilnya menggunakan nilai k supaya k kurang daripada 2^maximumBit. Berikut ialah pendekatan untuk menyelesaikan masalah ini:

Pemerhatian dan Pendekatan

  1. Memaksimumkan XOR:
    Nombor maksimum yang boleh kita XOR dengan sebarang jumlah awalan untuk bit maksimumBit ialah ( 2^{text{maximumBit}} - 1 ). Ini kerana XORing dengan nombor semua 1s (iaitu, 111...1 dalam binari) akan sentiasa memaksimumkan hasil.

  2. Pengiraan XOR Awalan:
    Daripada mengira semula XOR untuk setiap pertanyaan, kita boleh mengekalkan XOR terkumpul untuk keseluruhan tatasusunan. Memandangkan XOR mempunyai sifat A XOR B XOR B = A, mengalih keluar elemen terakhir daripada tatasusunan boleh dicapai dengan XOR mengeluarkan elemen itu daripada XOR terkumpul.

  3. Algoritma:

    • Kira XOR semua elemen dalam nombor pada mulanya. Jom panggil currentXOR ini.
    • Untuk setiap pertanyaan (dari yang terakhir hingga yang pertama):
      • Kira nilai optimum k untuk pertanyaan itu dengan XORing currentXOR dengan maxNum dengan maxNum = 2^maximumBit - 1.
      • Lampirkan k pada senarai keputusan.
      • Alih keluar elemen terakhir daripada nums dengan XORing keluar daripada currentXOR.
    • Senarai keputusan akan mengandungi jawapan dalam susunan terbalik, jadi terbalikkannya pada penghujungnya.

Mari laksanakan penyelesaian ini dalam PHP: 1829. XOR Maksimum untuk Setiap Pertanyaan

<?php /**
 * @param Integer[] $nums
 * @param Integer $maximumBit
 * @return Integer[]
 */
function getMaximumXor($nums, $maximumBit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [0,1,1,3];
$maximumBit = 2;
print_r(getMaximumXor($nums, $maximumBit));  // Output should be [0, 3, 2, 3]
?>

Penjelasan:

  1. Kira maxNum:

    • maxNum dikira sebagai 2^maximumBit - 1, iaitu nombor dengan semua 1 dalam binari untuk panjang bit yang ditentukan.
  2. Pengiraan XOR Awal:

    • Kami XOR semua elemen dalam nombor untuk mendapatkan XOR terkumpul (XOR semasa), mewakili XOR semua nombor dalam tatasusunan.
  3. Lelaran Ke Belakang:

    • Kami bermula dari elemen terakhir dalam nombor dan mengira XOR maksimum untuk setiap langkah:
      • currentXOR ^ maxNum memberikan k maksimum untuk keadaan semasa.
      • Lampirkan k untuk menjawab.
    • Kami kemudian XOR elemen terakhir nombor dengan currentXOR untuk "mengalihkannya" daripada jumlah XOR untuk lelaran seterusnya.
  4. Kembalikan Jawapan:

    • Memandangkan kami memproses senarai secara terbalik, jawapan akan mengandungi nilai dalam susunan terbalik, jadi senarai akhir sudah disusun dengan betul untuk keperluan kami.

Analisis Kerumitan

  • Kerumitan Masa: O(n), kerana kita mengira XOR awal dalam O(n) dan setiap pertanyaan diproses dalam masa yang tetap.
  • Kerumitan Angkasa: O(n), untuk menyimpan jawapan.

Kod ini cekap dan harus mengendalikan had atas kekangan dengan baik.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

  • LinkedIn
  • GitHub

Atas ialah kandungan terperinci XOR Maksimum untuk Setiap Pertanyaan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
11 skrip pemendek URL terbaik PHP (percuma dan premium)11 skrip pemendek URL terbaik PHP (percuma dan premium)Mar 03, 2025 am 10:49 AM

URL panjang, sering berantakan dengan kata kunci dan parameter penjejakan, boleh menghalang pelawat. Skrip pemendekan URL menawarkan penyelesaian, mewujudkan pautan ringkas yang sesuai untuk media sosial dan platform lain. Skrip ini sangat berharga untuk laman web individu a

Pengenalan kepada API InstagramPengenalan kepada API InstagramMar 02, 2025 am 09:32 AM

Berikutan pengambilalihan berprofil tinggi oleh Facebook pada tahun 2012, Instagram mengadopsi dua set API untuk kegunaan pihak ketiga. Ini adalah API Grafik Instagram dan API Paparan Asas Instagram. Sebagai pemaju membina aplikasi yang memerlukan maklumat dari a

Bekerja dengan Data Sesi Flash di LaravelBekerja dengan Data Sesi Flash di LaravelMar 12, 2025 pm 05:08 PM

Laravel memudahkan mengendalikan data sesi sementara menggunakan kaedah flash intuitifnya. Ini sesuai untuk memaparkan mesej ringkas, makluman, atau pemberitahuan dalam permohonan anda. Data hanya berterusan untuk permintaan seterusnya secara lalai: $ permintaan-

Bina aplikasi React dengan hujung belakang Laravel: Bahagian 2, ReactBina aplikasi React dengan hujung belakang Laravel: Bahagian 2, ReactMar 04, 2025 am 09:33 AM

Ini adalah bahagian kedua dan terakhir siri untuk membina aplikasi React dengan back-end Laravel. Di bahagian pertama siri ini, kami mencipta API RESTful menggunakan Laravel untuk aplikasi penyenaraian produk asas. Dalam tutorial ini, kita akan menjadi dev

Respons HTTP yang dipermudahkan dalam ujian LaravelRespons HTTP yang dipermudahkan dalam ujian LaravelMar 12, 2025 pm 05:09 PM

Laravel menyediakan sintaks simulasi respons HTTP ringkas, memudahkan ujian interaksi HTTP. Pendekatan ini dengan ketara mengurangkan redundansi kod semasa membuat simulasi ujian anda lebih intuitif. Pelaksanaan asas menyediakan pelbagai jenis pintasan jenis tindak balas: Gunakan Illuminate \ Support \ Facades \ http; Http :: palsu ([ 'Google.com' => 'Hello World', 'github.com' => ['foo' => 'bar'], 'forge.laravel.com' =>

Curl dalam PHP: Cara Menggunakan Pelanjutan PHP Curl dalam API RESTCurl dalam PHP: Cara Menggunakan Pelanjutan PHP Curl dalam API RESTMar 14, 2025 am 11:42 AM

Pelanjutan URL Pelanggan PHP (CURL) adalah alat yang berkuasa untuk pemaju, membolehkan interaksi lancar dengan pelayan jauh dan API rehat. Dengan memanfaatkan libcurl, perpustakaan pemindahan fail multi-protokol yang dihormati, php curl memudahkan execu yang cekap

12 skrip sembang php terbaik di codecanyon12 skrip sembang php terbaik di codecanyonMar 13, 2025 pm 12:08 PM

Adakah anda ingin memberikan penyelesaian segera, segera kepada masalah yang paling mendesak pelanggan anda? Sembang langsung membolehkan anda mempunyai perbualan masa nyata dengan pelanggan dan menyelesaikan masalah mereka dengan serta-merta. Ia membolehkan anda memberikan perkhidmatan yang lebih pantas kepada adat anda

Pengumuman Penyiasatan Situasi PHP 2025Pengumuman Penyiasatan Situasi PHP 2025Mar 03, 2025 pm 04:20 PM

Tinjauan Landskap PHP 2025 menyiasat trend pembangunan PHP semasa. Ia meneroka penggunaan rangka kerja, kaedah penempatan, dan cabaran, yang bertujuan memberi gambaran kepada pemaju dan perniagaan. Tinjauan ini menjangkakan pertumbuhan dalam PHP Versio moden

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Alat panas

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Penyesuai Pelayan SAP NetWeaver untuk Eclipse

Penyesuai Pelayan SAP NetWeaver untuk Eclipse

Integrasikan Eclipse dengan pelayan aplikasi SAP NetWeaver.

mPDF

mPDF

mPDF ialah perpustakaan PHP yang boleh menjana fail PDF daripada HTML yang dikodkan UTF-8. Pengarang asal, Ian Back, menulis mPDF untuk mengeluarkan fail PDF "dengan cepat" dari tapak webnya dan mengendalikan bahasa yang berbeza. Ia lebih perlahan dan menghasilkan fail yang lebih besar apabila menggunakan fon Unicode daripada skrip asal seperti HTML2FPDF, tetapi menyokong gaya CSS dsb. dan mempunyai banyak peningkatan. Menyokong hampir semua bahasa, termasuk RTL (Arab dan Ibrani) dan CJK (Cina, Jepun dan Korea). Menyokong elemen peringkat blok bersarang (seperti P, DIV),

Muat turun versi mac editor Atom

Muat turun versi mac editor Atom

Editor sumber terbuka yang paling popular