チョークの代わりになる生徒を見つける

1894年。チョークの代わりになる生徒を見つけてください

難易度: 中

トピック: 配列、二分探索、シミュレーション、プレフィックス合計

クラスには 0 から n - 1 までの番号が付けられた n 人の生徒がいます。教師は各生徒に生徒番号 0 から始めて問題を出し、次に生徒番号 1 というように生徒番号 n に達するまで問題を出します。 - 1. その後、教師は再び生徒番号 0 から処理を再開します。

0 インデックス付き 整数配列チョークと整数 k が与えられます。最初は k 個のチョークがあります。生徒番号 i に解決すべき問題が与えられると、生徒はチョーク [i] 個のチョークを使ってその問題を解決します。ただし、現在のチョークの数がチョーク[i] より厳密に少ない場合、学生番号 i はチョークを交換するように求められます。

チョーク部分を置き換えする生徒のインデックスを返します。

例 1:

• 入力: チョーク = [5,1,5]、k = 22
• 出力: 0
• 説明: 生徒たちは次のように順番に行動します。
  • 生徒番号 0 はチョークを 5 本使用するため、k = 17 となります。
  • 生徒番号 1 はチョークを 1 本使用するため、k = 16 となります。
  • 生徒番号 2 は 5 つのチョークを使用するため、k = 11。
  • 生徒番号 0 は 5 つのチョークを使用するため、k = 6。
  • 生徒番号 1 はチョークを 1 本使用するため、k = 5 となります。
  • 生徒番号 2 は 5 つのチョークを使用するため、k = 0。
  • 生徒番号 0 はチョークが足りないので、チョークを交換する必要があります。

例 2:

• 入力: チョーク = [3,4,1,2]、k = 25
• 出力: 1
• 説明: 生徒たちは次のように順番に行動します。
  • 生徒番号 0 は 3 つのチョークを使用するため、k = 22。
  • 生徒番号 1 はチョークを 4 本使用するため、k = 18 となります。
  • 生徒番号 2 はチョークを 1 本使用するため、k = 17 となります。
  • 生徒番号 3 はチョークを 2 本使用するため、k = 15。
  • 生徒番号 0 はチョークを 3 本使用するため、k = 12.
  • 生徒番号 1 はチョークを 4 本使用するため、k = 8 となります。
  • 生徒番号 2 はチョークを 1 本使用するため、k = 7 となります。
  • 生徒番号 3 はチョークを 2 本使用するため、k = 5 となります。
  • 生徒番号 0 は 3 つのチョークを使用するため、k = 2.
  • 生徒番号 1 はチョークが足りないので、チョークを交換する必要があります。

制約:

• chalk.length == n
• 1 5
• 1 5
• 1 9

ヒント:

1. k がチョークの合計より小さくなるまで、k からチョークの合計を引きます。
2. 次に、配列を反復処理します。 Chalk[i] が k 未満の場合、これが答えになります。それ以外の場合は、k から chalk[i] を減算して続行します。

解決策:

問題を段階的に分析してみましょう:

アプローチ：

1. チョークの総消費量:
   まず、1 ラウンド (生徒 0 から生徒 n-1 まで) に必要なチョークの総量を計算します。これは、k 個のチョークでカバーできる完全なラウンドの数を考慮して、k の値を減らすのに役立ちます。

2. Modulo で k を減らす:
   k が 1 つの完全なラウンドに必要な合計チョークよりも大きい場合、k % total_chalk を取得することで問題を単純化できます。この操作により、できるだけ多くのラウンドを行った後に残りのチョークが得られ、解決すべき小さな問題が残ります。

3. チョークがなくなった生徒を見つけます:
   各生徒のチョーク消費量を繰り返し、k が現在の生徒のチョーク必要量よりも少なくなるまで、k からそれを減算します。この生徒のインデックスが私たちの答えです。

チュートリアルの例:

チョーク = [3, 4, 1, 2] および k = 25 の例を見てみましょう:

1. チョークの総消費量:

   text{total_chalk} = 3 + 4 + 1 + 2 = 10

1. k を減らす:

   k % 10 = 25 % 10 = 5

できるだけ多くの完全なラウンドを減算すると、k = 5 になります。

1. 生徒を探す:
   • 生徒 0 は 3 つのチョークを使用するため、k = 5 - 3 = 2 となります。
   • 生徒 1 には 4 つのチョークが必要ですが、k = 2 であり、4 未満です。
   • したがって、チョークを交換する必要があるのは生徒 1 になります。

このソリューションを PHP で実装してみましょう: 1894。チョークを交換する生徒を見つけてください

<?php
/**
 * @param Integer[] $chalk
 * @param Integer $k
 * @return Integer
 */
function chalkReplacer($chalk, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

//Example 1
$chalk = [5,1,5];
$k = 22;
echo chalkReplacer($chalk, $k);  // Output: 0

//Example 2
$chalk = [3, 4, 1, 2];
$k = 25;
echo chalkReplacer($chalk, $k);  // Output: 1
?>

Explanation:

1. Total Chalk Sum: We sum up all the chalk requirements to get the total for one complete round.
2. Modulo Operation: Using modulo with k, we get the effective number of chalks to distribute after full rounds.
3. Find the Student: We then iterate through the students, checking if the remaining chalk is sufficient. The first time it's insufficient, that student's index is the answer.

Complexity:

• Time Complexity: O(n) — we sum the array and then iterate through it once.
• Space Complexity: O(1) — only a few variables are used, independent of the input size.

This approach ensures that the problem is solved efficiently even for large inputs.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

以上がチョークの代わりになる生徒を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。