3152。スペシャルアレイ II

難易度: 中

トピック: 配列、二分探索、接頭辭合計(jì)

隣接する要素のすべてのペアに異なるパリティを持つ 2 つの數(shù)値が含まれている場合、配列は 特別とみなされます。

整數(shù)の配列と 2D 整數(shù)行列のクエリが與えられます。クエリ[i] = [from_i, to_i] の場合、あなたのタスクはそれをチェックすることです。部分配列¹ nums[from_i..to_i] は特別かどうか。

nums[fromi_..toi_{] が特別な場合に、answer[i] が true となるようなブール値の配列を返します}。

例 1:

• 入力: 數(shù)値 = [3,4,1,2,6]、クエリ = [[0,4]]
• 出力: [false]
• 説明: 部分配列は [3,4,1,2,6] です。 2 と 6 は両方とも偶數(shù)です。

例 2:

• 入力: 數(shù)値 = [4,3,1,6]、クエリ = [[0,2],[2,3]]
• 出力: [false,true]
• 説明:

部分配列は [4,3,1] です。 3と1はどちらも奇數(shù)です。したがって、このクエリに対する答えは false です。
部分配列は [1,6] です。 (1,6) のペアは 1 つだけあり、これには異なるパリティを持つ數(shù)値が含まれています。したがって、このクエリに対する答えは true です。

制約:

1 5 1 5 1 5 クエリ[i].length == 2
0

ヒント:

配列を、交差しない連続した特殊な部分配列に分割してみます。
各クエリについて、そのクエリの最初と最後の要素が同じサブ配列內(nèi)にあるかどうかを確認(rèn)します。

解決策:

nums の部分配列が「特別」であるかどうかを判斷する必要があります。つまり、部分配列內(nèi)の隣接する要素のすべてのペアが異なるパリティを持つ必要があります (1 つは奇數(shù)で、もう 1 つは偶數(shù)である必要があります)。

アプローチ：

1. パリティ遷移の特定: 配列を前処理して、パリティが変更される位置をマークできます。例えば：
   0 は偶數(shù)を表します。
   1 は奇數(shù)を表します。

そのアイデアは、隣接する要素が異なるパリティを持つすべての位置を識(shí)別することです。これは、クエリ內(nèi)の位置が同じ「特別な」ブロックの一部であるかどうかをチェックすることで、サブ配列が特別であるかどうかを効率的に判斷するのに役立ちます。

1. 前処理: バイナリ配列 parity_change を作成します。隣接する要素のパリティが異なる場合は各要素が 1、それ以外の場合は 0 になります。例:
   

   • nums[i] と nums[i 1] のパリティが異なる場合は、parity_change[i] = 1 に設(shè)定し、それ以外の場合は 0 を設(shè)定します。

2. プレフィックス合計(jì)配列:
   インデックス i の各エントリがそのインデックスまでのパリティ遷移の累積數(shù)を表すプレフィックス合計(jì)配列 prefix_sum を構(gòu)築します。これは、サブ配列內(nèi)のすべてのペアが異なるパリティを持つかどうかをすばやく確認(rèn)するのに役立ちます。

3. クエリ処理:
   各クエリ [from, to] について、範(fàn)囲 [from, to-1] 內(nèi)にパリティが変化しない位置があるかどうかを確認(rèn)します。これは、プレフィックス合計(jì)値の差をチェックすることで実行できます: prefix_sum[to] - prefix_sum[from].

このソリューションを PHP で実裝してみましょう: 3152。特殊配列 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]
?>

説明：

1. パリティ遷移の前処理:
   要素 nums[i] と nums[i 1] のパリティが異なる場合、parity_change[i] = 1 を計(jì)算します。それ以外の場合は、0 に設(shè)定します。

2. プレフィックス合計(jì)配列:
   prefix_sum[i] には、配列の先頭からインデックス i までのパリティ遷移の累積數(shù)が格納されます。これにより、次の式を使用して、一定時(shí)間內(nèi)に任意の部分配列 [from, to] で発生した遷移の數(shù)を計(jì)算できます。
   

   $transition_count = $prefix_sum[$to] - $prefix_sum[$from];

1. クエリ評(píng)価: 各クエリについて、遷移の數(shù)が部分配列の長さから 1 を引いたものに等しい場合、その部分配列は特別であるため、true を返します。それ以外の場合は false を返します。

時(shí)間計(jì)算量:

• パリティ遷移の前処理には O(n) かかります。
• プレフィックス合計(jì)配列の構(gòu)築には O(n) かかります。
• 各クエリは、プレフィックス合計(jì)配列を使用して O(1) で答えることができます。
• したがって、合計(jì)の時(shí)間計(jì)算量は O(n q) です。ここで、n は配列の長さ、q はクエリの數(shù)です。

このソリューションは、最適化されたアプローチで問題の制約を効率的に処理します。

連絡(luò)先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お?dú)荬巳毪辘违僵`シャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お?dú)葺Xにフォローしてください:

• LinkedIn
• GitHub

---

1. サブ配列 サブ配列 は、配列內(nèi)の連続した要素のシーケンスです。??

以上がスペシャルアレイ IIの詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。