すべての要素をマークした後の配列のスコアの検索

2593。すべての要素をマークした後の配列のスコアを検索

難易度: 中

トピック: ヒープ (優先キュー)、ソート、配列、シミュレーション、ハッシュ テーブル、順序付きセット、順序付きマップ、貪欲、単調スタック、スライディング ウィンドウ、2 つのポインター、スタック、キュー、ビット操作、分割統治、動的プログラミング、二重リンクリスト、データストリーム、基数ソート、バックトラッキング、ビットマスク、ツリー、デザイン、ハッシュ関数、文字列、イテレータ、カウンティングソート、リンクリスト

正の整数で構成される配列 nums が与えられます。

スコア = 0 から始めて、次のアルゴリズムを適用します:

• マークされていない配列の最小の整数を選択します。同点の場合は、インデックスが最も小さいものを選択します。
• 選択した整数値をスコアに加算します。
• 選択した要素と、存在する場合はその 2 つの隣接要素を マークします。
• すべての配列要素がマークされるまで繰り返します。

上記のアルゴリズムを適用した後に得られるスコアを返します。

例 1:

• 入力: 数値 = [2,1,3,4,5,2]
• 出力: 7
• 説明: 要素を次のようにマークします。
  • 1 はマークされていない最小の要素なので、これとその 2 つの隣接する要素 [2,1,3,4,5,2] をマークします。
  • 2 はマークされていない最小の要素であるため、これとその左に隣接する要素 [2,1,3,4,5,2] をマークします。
  • 4 はマークされていない要素として残っている唯一のものなので、[2,1,3,4,5,2] とマークします。
  • 私たちのスコアは 1 2 4 = 7 です。

例 2:

• 入力: 数値 = [2,3,5,1,3,2]
• 出力: 5
• 説明: 要素を次のようにマークします。
  • 1 はマークされていない最小の要素なので、これとその 2 つの隣接する要素 [2,3,5,1,3,2] をマークします。
  • 2 はマークされていない最小の要素です。要素が 2 つあるため、一番左の要素を選択し、インデックス 0 の要素とその右隣の要素にマークを付けます: [2,3,5,1,3, 2].
  • 2 は残りのマークされていない唯一の要素なので、[2,3,5,1,3,2] とマークします。
  • 私たちのスコアは 1 2 2 = 5 です。

制約:

• 1 5
• 1 6

ヒント:

1. 要素とその隣接要素をマークするプロセスをシミュレートしてみてください。
2. すでにマークされている要素がある場合は、それをスキップします。

解決策:

ソートされた配列または優先キューを使用して、マークされていない最小の要素を追跡することで、マーキング プロセスを効率的にシミュレートできます。したがって、次のアプローチを使用できます:

プラン：

1. 入力解析: 配列 nums を読み取り、スコアと採点ステータスの変数を初期化します。
2. ヒープ (優先キュー):
   • min-heap を使用して、各ステップでマークされていない最小の要素を効率的に抽出します。
   • 各要素をそのインデックス (値、インデックス) とともにヒープに挿入し、最小のインデックスに基づいて関係を管理します。
3. 要素のマーキング:
   • マークされた配列を維持して、要素とその隣接する要素がマークされているかどうかを追跡します。
   • ヒープから要素を処理するとき、すでにマークされている場合はスキップします。
   • 現在の要素とその 2 つの隣接する要素 (存在する場合) をマークします。
   • 現在の要素の値をスコアに追加します。
4. 繰り返し: すべての要素がマークされるまで続けます。
5. 出力: 蓄積されたスコアを返します。

このソリューションを PHP で実装してみましょう: 2593。すべての要素をマークした後の配列のスコアを検索

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

// Example usage:
$nums1 = [2, 1, 3, 4, 5, 2];
$nums2 = [2, 3, 5, 1, 3, 2];

echo findScore($nums1) . "\n"; // Output: 7
echo findScore($nums2) . "\n"; // Output: 5
?>

説明：

1. ヒープ構築:

   • usort 関数は、値に基づいて配列を並べ替えます。また、値が同じ場合はインデックスによって並べ替えます。
   • これにより、常に最小のインデックスを持つ最小のマークされていない要素が処理されます。

2. マーキングロジック:

   • マークされていない各要素について、マークされた配列を使用してその要素とその隣接する要素をマークします。
   • これにより、以前にマークされた要素を効率的にスキップできます。

3. 時間計算量:

   • ヒープのソート: O(n log n)
   • ヒープの処理: O(n)
   • 全体: O(n log n)。これは、指定された制約に対して効率的です。

4. 空間の複雑さ:

   • マークされた配列: O(n)
   • ヒープ: O(n)
   • 合計: O(n)

このソリューションは制約を満たしており、大規模な入力に対して効率的に機能します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がすべての要素をマークした後の配列のスコアの検索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。