3152。スペシャルアレイ II
難易度: 中
トピック: 配列、二分探索、接頭辞合計
隣接する要素のすべてのペアに異なるパリティを持つ 2 つの数値が含まれている場合、配列は 特別とみなされます。
整数の配列と 2D 整数行列のクエリが与えられます。クエリ[i] = [fromi, toi] の場合、あなたのタスクはそれをチェックすることです。部分配列1 nums[fromi..toi] は特別かどうか。
nums[fromi..toi] が特別な場合に、answer[i] が true となるようなブール値の配列を返します。
例 1:
例 2:
制約:
ヒント:
解決策:
nums の部分配列が「特別」であるかどうかを判断する必要があります。つまり、部分配列内の隣接する要素のすべてのペアが異なるパリティを持つ必要があります (1 つは奇数で、もう 1 つは偶数である必要があります)。アプローチ:
前処理:
バイナリ配列 parity_change を作成します。隣接する要素のパリティが異なる場合は各要素が 1、それ以外の場合は 0 になります。例:
プレフィックス合計配列:
インデックス i の各エントリがそのインデックスまでのパリティ遷移の累積数を表すプレフィックス合計配列 prefix_sum を構築します。これは、サブ配列内のすべてのペアが異なるパリティを持つかどうかをすばやく確認するのに役立ちます。
クエリ処理:
各クエリ [from, to] について、範囲 [from, to-1] 内にパリティが変化しない位置があるかどうかを確認します。これは、プレフィックス合計値の差をチェックすることで実行できます: 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] ?>
パリティ遷移の前処理:
要素 nums[i] と nums[i 1] のパリティが異なる場合、parity_change[i] = 1 を計算します。それ以外の場合は、0 に設定します。
プレフィックス合計配列:
prefix_sum[i] には、配列の先頭からインデックス i までのパリティ遷移の累積数が格納されます。これにより、次の式を使用して、一定時間内に任意の部分配列 [from, to] で発生した遷移の数を計算できます。
$transition_count = $prefix_sum[$to] - $prefix_sum[$from];
このソリューションは、最適化されたアプローチで問題の制約を効率的に処理します。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
サブ配列 サブ配列 は、配列内の連続した要素のシーケンスです。 ↩
以上がスペシャルアレイ IIの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。