Susunan Khas II

3152. Susunan Khas II

Kesukaran: Sederhana

Topik: Tatasusunan, Carian Perduaan, Jumlah Awalan

Suatu tatasusunan dianggap istimewa jika setiap pasangan elemen bersebelahannya mengandungi dua nombor dengan pariti berbeza.

Anda diberi tatasusunan nombor integer dan pertanyaan matriks integer 2D, di mana untuk pertanyaan[i] = [dari_i, hingga_i] tugas anda adalah untuk menyemaknya subaray¹ nums[from_i..to_i] adalah istimewa atau tidak.

Kembalikan tatasusunan jawapan boolean supaya jawapan[i] adalah benar jika nums[dari_i..ke_i] adalah istimewa.

Contoh 1:

• Input: nombor = [3,4,1,2,6], pertanyaan = [[0,4]]
• Output: [salah]
• Penjelasan: Subarray ialah [3,4,1,2,6]. 2 dan 6 kedua-duanya genap.

Contoh 2:

• Input: nombor = [4,3,1,6], pertanyaan = [[0,2],[2,3]]
• Output: [salah, benar]
• Penjelasan:

1. Subarray ialah [4,3,1]. 3 dan 1 kedua-duanya ganjil. Jadi jawapan kepada pertanyaan ini adalah palsu.
2. Subarray ialah [1,6]. Terdapat hanya satu pasangan: (1,6) dan ia mengandungi nombor dengan pariti yang berbeza. Jadi jawapan kepada pertanyaan ini adalah benar.

Kekangan:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁵
• 1 <= queries.length <= 10⁵
• pertanyaan[i].panjang == 2
• 0 <= pertanyaan[i][0] <= pertanyaan[i][1] <= nums.length - 1

Petunjuk:

1. Cuba bahagikan tatasusunan kepada beberapa subarray khas berterusan yang tidak bersilang.
2. Untuk setiap pertanyaan, semak bahawa elemen pertama dan terakhir pertanyaan itu berada dalam subbaris yang sama atau tidak.

Penyelesaian:

Kita perlu menentukan sama ada subarray nombor adalah "istimewa", iaitu, setiap pasangan elemen bersebelahan dalam subarray mesti mempunyai pariti yang berbeza (satu mesti ganjil, dan satu lagi mesti genap).

Pendekatan:

1. Kenal pasti Peralihan Pariti: Kita boleh praproses tatasusunan untuk menandakan kedudukan di mana pariti berubah. Contohnya:
   • 0 mewakili nombor genap.
   • 1 mewakili nombor ganjil.

Ideanya adalah untuk mengenal pasti semua kedudukan yang unsur-unsur bersebelahan mempunyai pariti yang berbeza. Ini akan membantu kami menentukan dengan cekap sama ada subarray adalah istimewa dengan menyemak sama ada kedudukan dalam pertanyaan adalah sebahagian daripada blok "istimewa" yang sama.

1. Prapemprosesan:
   Cipta pariti_perubahan tatasusunan binari di mana setiap elemen ialah 1 jika elemen bersebelahan mempunyai pariti berbeza, jika tidak 0. Contohnya:

   • Jika nums[i] dan nums[i 1] mempunyai pariti yang berbeza, tetapkan pariti_change[i] = 1, jika tidak 0.

2. Susun Susun Awalan:
   Bina prefix sum array prefix_sum di mana setiap entri pada indeks i mewakili bilangan terkumpul peralihan pariti sehingga indeks tersebut. Ini membantu menyemak dengan cepat sama ada semua pasangan dalam subarray mempunyai pariti yang berbeza.

3. Pemprosesan Pertanyaan:
   Untuk setiap pertanyaan [dari, kepada], semak sama ada terdapat sebarang kedudukan dalam julat [dari, kepada-1] di mana pariti tidak berubah. Ini boleh dilakukan dengan menyemak perbezaan dalam nilai jumlah awalan: prefix_sum[to] - prefix_sum[from].

Mari laksanakan penyelesaian ini dalam PHP: 3152. Susunan Khas II

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

// Example usage
$nums1 = [3,4,1,2,6];
$queries1 = [[0, 4]];
print_r(specialArray($nums1, $queries1)); // [false]

$nums2 = [4,3,1,6];
$queries2 = [[0, 2], [2, 3]];
print_r(specialArray($nums2, $queries2)); // [false, true]
?>




<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li><p><strong>Memproses Peralihan Pariti:</strong><br>
Kami mengira pariti_perubahan[i] = 1 jika unsur nums[i] dan nums[i 1] mempunyai pariti yang berbeza. Jika tidak, kami tetapkan kepada 0.</p></li>
<li><p><strong>Susun Susun Awalan:</strong><br>
Prefix_sum[i] menyimpan kiraan kumulatif peralihan pariti dari permulaan tatasusunan sehingga indeks i. Ini membolehkan kami mengira bilangan peralihan yang berlaku dalam mana-mana subarray [dari, kepada] dalam masa tetap menggunakan formula:<br>
</p></li>
</ol>

<pre class="brush:php;toolbar:false">   $transition_count = $prefix_sum[$to] - $prefix_sum[$from];

1. Penilaian Pertanyaan: Untuk setiap pertanyaan, jika bilangan peralihan adalah sama dengan panjang subarray tolak 1, subarray adalah istimewa dan kami kembalikan benar. Jika tidak, kami membalas palsu.

Kerumitan Masa:

• Praproses peralihan pariti memerlukan O(n).
• Membina tatasusunan jumlah awalan memerlukan O(n).
• Setiap pertanyaan boleh dijawab dalam O(1) menggunakan tatasusunan jumlah awalan.
• Oleh itu, jumlah kerumitan masa ialah O(n q), dengan n ialah panjang tatasusunan dan q ialah bilangan pertanyaan.

Penyelesaian ini cekap mengendalikan kekangan masalah dengan pendekatan yang dioptimumkan.

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

1. Subarray subarray ialah jujukan unsur bersebelahan dalam tatasusunan. ↩

Atas ialah kandungan terperinci Susunan Khas II. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!