範囲 I から選択する整数の最大数

2554。範囲 I

から選択する整数の最大数

難易度: 中

トピック: 配列、ハッシュ テーブル、二分探索、貪欲、並べ替え

禁止された整数配列と 2 つの整数 n と maxSum が与えられます。以下のルールに従って、いくつかの整数を選択しています:

• 選択した整数は [1, n] の範囲内である必要があります。
• 各整数は最大 1 回選択できます。
• 選択した整数は、禁止された配列内にあってはなりません。
• 選択した整数の合計が maxSum を超えてはなりません。

前述のルールに従って選択できる整数の 最大数を返します。

例 1:

• 入力: 禁止 = [1,6,5]、n = 5、maxSum = 6
• 出力: 2
• 説明: 整数 2 と 4 を選択できます。
  2 と 4 は [1, 5] の範囲にあり、両方とも禁止されておらず、合計は 6 で、maxSum を超えませんでした。

例 2:

• 入力: 禁止 = [1,2,3,4,5,6,7]、n = 8、maxSum = 1
• 出力: 0
• 説明: 前述の条件に従っている間は、整数を選択できません。

例 3:

• 入力: 禁止 = [11]、n = 7、maxSum = 50
• 出力: 7
• 説明: 整数 1、2、3、4、5、6、7 を選択できます。
  それらは [1, 7] の範囲にあり、すべてが禁止されておらず、合計は 28 であり、maxSum を超えていません。

制約:

1 4 1 4 1 9

ヒント:

n 未満の禁止番号をセットとして保持します。
1 から n までの番号をループし、その番号が禁止されていない場合は、それを使用します。
禁止されていない間は数字を加算し続け、その合計が k 未満になるようにしてください。

解決策:

1 から n までの数値を繰り返し、禁止された数値をスキップし、maxSum に達するまで有効な数値 (禁止された配列に含まれていない数値) を累計に加算し続ける貪欲なアプローチを使用できます。

段階的な解決策は次のとおりです:

手順:

1. 禁止された配列をクイック ルックアップ用のセットに変換する: array_flip() を使用すると、禁止された配列を O(1) 平均計算量ルックアップ用のセットに変換できます。
2. 1 から n まで反復します: 各数値を確認し、禁止されたセットに含まれていない場合、および加算しても maxSum を超えない場合は、合計に加算してカウントを増やします。
3. 次の数値の追加が maxSum を超えたら停止します: 目標は、合計を超えずに選択した整数の数を最大化することであるため、この貪欲なアプローチにより、利用可能な最小の数値が最初に取得されます。

アプローチ：

1. 禁止された番号を除外する: 高速検索のために、セット (または連想配列) 内の禁止された番号を追跡します。
2. 貪欲な選択: 1 から n までの数値を昇順で選択し始めます。これにより、選択される整数の数を最大化できます。数値を選択するたびに、それを合計に追加し、それが maxSum を超えているかどうかを確認します。そうなった場合は、停止してください。
3. 効率に関する考慮事項: 1 から n までの数値を反復処理し、それぞれが禁止されたセット内にあるかどうかをチェックしているため (定数時間で実行可能)、このアプローチは n に対して線形時間で実行され、禁止リストのサイズ

このソリューションを PHP で実装してみましょう: 2554。範囲 I
から選択する整数の最大数

<?php
/**
 * @param Integer[] $banned
 * @param Integer $n
 * @param Integer $maxSum
 * @return Integer
 */
function maxCount($banned, $n, $maxSum) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maxCount([1, 6, 5], 5, 6);  // Output: 2
echo "\n";
echo maxCount([1, 2, 3, 4, 5, 6, 7], 8, 1);  // Output: 0
echo "\n";
echo maxCount([11], 7, 50);  // Output: 7
?>

説明：

1. 禁止された配列を設定に変換します:
   
   array_flip($banned) を使用して、禁止された配列からセットを作成します。これにより、O(1) ルックアップで番号が禁止されているかどうかを確認できます。

2. 1 から n までの反復:
   
   1 から n までの数値を繰り返し処理します。各番号について:

   • 番号が禁止セットにない場合 (isset($bannedSet[$i]) を使用してチェック)、
   • そして、合計に数値を加算しても maxSum を超えない場合、
   • その数値を含めて合計とカウントを更新します。

3. カウントを返します:
   
   ループの後、選択された整数の数 ($count) を返します。

4. $bannedSet = array_flip($banned);: これにより、禁止リストが高速検索用のセット (連想配列) に変換されます。

5. for ($i = 1; $i : 1 から n までのすべての整数を繰り返します。

6. if (isset($bannedSet[$i])) { 続行; }: 現在の番号が禁止されたセットに含まれているかどうかをチェックします。そうであれば、スキップします。

7. if ($sum $i > $maxSum) { ブレーク; }: 現在の数値の加算が maxSum を超える場合、プロセスを停止します。

8. $sum = $i; $count ;: 数値が有効で、その数値を加算しても maxSum を超えない場合は、その数値を合計に含めてカウントを増やします。

時間計算量:

• 禁止されたセット (array_flip) の作成は O(b) です。ここで、b は禁止された配列の長さです。
• ループは n 回 (1 から n までの数値の場合) 繰り返され、禁止されたセットへの各検索には O(1) 時間がかかります。したがって、ループの時間計算量は O(n) です。
• したがって、全体的な時間計算量は O(n b) であり、問​​題の制約を考慮すると効率的です。

チュートリアルの例:

入力用:

• 入力 1: 禁止 = [1, 6, 5]、n = 5、maxSum = 6

  • 禁止されたセット: {1, 5, 6} を作成します。
  • 番号 1 から 5 までを繰り返します。
    • 1 は禁止されています。スキップしてください。
    • 2 は禁止されていません。合計に加算します (sum = 2、count = 1)。
    • 3 は禁止されていません。合計に加算します (合計 = 5、カウント = 2)。
    • 4 は禁止されていませんが、合計に追加すると maxSum (5 4 = 9) を超えるため、スキップしてください。
  • 結果は 2 です。

• 入力 2: 禁止 = [1, 2, 3, 4, 5, 6, 7]、n = 8、maxSum = 1

  • 1 から 7 までのすべての数字は禁止されているため、有効な数字を選択することはできません。
  • 結果は 0 です。

• 入力 3: 禁止 = [11]、n = 7、maxSum = 50

  • 唯一禁止されている数字は 11 であり、1 から 7 の範囲外です。
  • 1 から 7 までのすべての数値を選択でき、それらの合計は 28 となり、maxSum より小さくなります。
  • 結果は 7 です。

このソリューションは、指定された制約内で問題を効率的に処理します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が範囲 I から選択する整数の最大数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。