3152。スペシャルアレイ II

難易度: 中

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

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

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

nums[fromi_..toi_{] が特別な場(chǎng)合に、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 を作成します。隣接する要素のパリティが異なる場(chǎng)合は各要素が 1、それ以外の場(chǎng)合は 0 になります。例:
   

   • nums[i] と nums[i 1] のパリティが異なる場(chǎng)合は、parity_change[i] = 1 に設(shè)定し、それ以外の場(chǎng)合は 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] のパリティが異なる場(chǎng)合、parity_change[i] = 1 を計(jì)算します。それ以外の場(chǎng)合は、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ù)が部分配列の長(zhǎng)さから 1 を引いたものに等しい場(chǎng)合、その部分配列は特別であるため、true を返します。それ以外の場(chǎng)合は false を返します。

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

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

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

連絡(luò)先リンク

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

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

• LinkedIn
• GitHub

---

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

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