找到将更换粉笔的学生

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中文网其他相关文章！