範囲 I から選択する整数の最大数-PHPチュートリアル-php.cn

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

Mary-Kate Olsen

リリース： 2024-12-21 02:01:10

オリジナル

749 人が閲覧しました

Maximum Number of Integers to Choose From a Range I

2554。範囲 I

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

難易度: 中

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

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

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

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

例 1:

入力: 禁止 = [1,6,5]、n = 5、maxSum = 6
出力: 2
説明: 整数 2 と 4 を選択できます。

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

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

手順:

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

アプローチ：

禁止された番号を除外する: 高速検索のために、セット (または連想配列) 内の禁止された番号を追跡します。
貪欲な選択: 1 から n までの数値を昇順で選択し始めます。これにより、選択される整数の数を最大化できます。数値を選択するたびに、それを合計に追加し、それが maxSum を超えているかどうかを確認します。そうなった場合は、停止してください。
効率に関する考慮事項: 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
?>

ログイン後にコピー

説明：

禁止された配列を設定に変換します:

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

1 から n までの数値を繰り返し処理します。各番号について:
- 番号が禁止セットにない場合 (isset($bannedSet[$i]) を使用してチェック)、
- そして、合計に数値を加算しても maxSum を超えない場合、
- その数値を含めて合計とカウントを更新します。
カウントを返します:

ループの後、選択された整数の数 ($count) を返します。
$bannedSet = array_flip($banned);: これにより、禁止リストが高速検索用のセット (連想配列) に変換されます。
for ($i = 1; $i : 1 から n までのすべての整数を繰り返します。
if (isset($bannedSet[$i])) { 続行; }: 現在の番号が禁止されたセットに含まれているかどうかをチェックします。そうであれば、スキップします。
if ($sum $i > $maxSum) { ブレーク; }: 現在の数値の加算が maxSum を超える場合、プロセスを停止します。
$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 です。