找到將更換粉筆的學生

1894。找出會替換粉筆的學生

難度：中

主題：陣列、二分查找、模擬、前綴和

一個班級有n個學生，編號從0到n - 1。老師會給每個學生一個問題，從學號0開始，然後是學號1，以此類推，直到老師達到學號n - 1. 之後，老師將重新開始該過程，再次從學號0開始。

給你一個0索引整數陣列chalk和一個整數k。最初有 k 支粉筆。當編號 i 的學生需要解決一個問題時，他們將使用 chalk[i] 塊粉筆來解決這個問題。然而，如果目前粉筆的數量嚴格小於粉筆[i]，那麼學號i將被要求更換粉筆。

回傳將替換粉筆片的學生的索引。

範例1：

• 輸入： chalk = [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：

• 輸入： chalk = [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 減去 chalk 的總和，直到 k 小於 chalk 的總和。
2. 現在迭代數組。如果 chalk[i] 小於 k，這就是答案。否則，從 k 中減去 chalk[i] 並繼續。

解：

讓我們一步步分解問題：

方法：

1. 粉筆總消耗量：
   首先，計算完整一輪（從學生 0 到學生 n-1）所需的粉筆總量。這將幫助我們透過考慮 k 支粉筆可以覆蓋多少完整回合來減少 k 的值。

2. 透過模數減少 k：
   如果 k 大於一整輪所需的粉筆總數，我們可以透過取 k %total_chalk 來簡化問題。此操作將在盡可能多的整輪後為我們提供剩餘的粉筆，從而留下一個較小的問題需要解決。

3. 找到粉筆用完的學生：
   迭代每個學生的粉筆消耗量，從 k 中減去它，直到 k 小於當前學生的粉筆需求。這位同學的索引就是我們的答案。

演練範例：

舉個例子，chalk = [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中文網其他相關文章！