ホームページ >バックエンド開発 >PHPチュートリアル >最も裕福な山からギフトを受け取る
2558。最も裕福な山からギフトを受け取りましょう
難易度: 簡単
トピック: 配列、ヒープ (優先キュー)、シミュレーション
さまざまな山のギフトの数を示す整数配列ギフトが与えられます。毎秒、次のことを行います:
k 秒後に残っているギフトの数を返します。
例 1:
例 2:
制約:
ヒント:
解決策:
最大数のギフトを含む山を繰り返し選択する必要があるため、最大ヒープ (優先キュー) を利用できます。最大ヒープを使用すると、一定時間内に最大の山に効率的にアクセスし、山からギフトを取得した後にヒープを更新できます。
最大ヒープを使用する:
毎秒の処理:
終了:
このソリューションを PHP で実装してみましょう: 2558。最も裕福な山からギフトを受け取りましょう
<?php /** * @param Integer[] $gifts * @param Integer $k * @return Integer */ function pickGifts($gifts, $k) { ... ... ... /** * go to ./solution.php */ } // Example usage: $gifts1 = [25, 64, 9, 4, 100]; $k1 = 4; echo pickGifts($gifts1, $k1) . "\n"; // Output: 29 $gifts2 = [1, 1, 1, 1]; $k2 = 4; echo pickGifts($gifts2, $k2) . "\n"; // Output: 4 ?>
ヒープの初期化:
最大のパイルを処理しています:
残りのギフトを合計しています:
エッジケース:
O(k log n) です。ここで、n はパイルの数、k は秒数です。
チュートリアルの例:
<?php /** * @param Integer[] $gifts * @param Integer $k * @return Integer */ function pickGifts($gifts, $k) { ... ... ... /** * go to ./solution.php */ } // Example usage: $gifts1 = [25, 64, 9, 4, 100]; $k1 = 4; echo pickGifts($gifts1, $k1) . "\n"; // Output: 29 $gifts2 = [1, 1, 1, 1]; $k2 = 4; echo pickGifts($gifts2, $k2) . "\n"; // Output: 4 ?>
残りのギフトの合計は 5 8 9 4 3 = 29 です。
このアプローチは、最大ヒープを使用して問題を効率的に解決し、指定された制約内で適切にパフォーマンスを発揮します。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
以上が最も裕福な山からギフトを受け取るの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。