找到将更换粉笔的学生

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 <= n <= 10 5 1 <= 粉笔[i] <= 10 5 1 <= k <= 10 9 提示： Git 程序猿必备版本控制工具 下载 从 k 中减去 chalk 的总和，直到 k 小于 chalk 的总和。 现在迭代数组。如果 chalk[i] 小于 k，这就是答案。否则，从 k 中减去 chalk[i] 并继续。 解决方案： 让我们一步步分解问题： 方法： 粉笔总消耗量： 首先，计算完整一轮（从学生 0 到学生 n-1）所需的粉笔总量。这将帮助我们通过考虑 k 支粉笔可以覆盖多少完整回合来减少 k 的值。 通过模数减少 k： 如果 k 大于一整轮所需的粉笔总数，我们可以通过取 k %total_chalk 来简化问题。此操作将在尽可能多的整轮后为我们提供剩余的粉笔，留下一个较小的问题需要解决。 找到粉笔用完的学生： 迭代每个学生的粉笔消耗量，从 k 中减去它，直到 k 小于当前学生的粉笔需求。这位同学的索引就是我们的答案。 演练示例： 举个例子，chalk = [3, 4, 1, 2] 且 k = 25： 粉笔总消耗量： 减少 k： 减去尽可能多的整轮后，现在 k = 5。 找到学生： 学生 0 使用 3 支粉笔，因此 k = 5 - 3 = 2。 学生 1 需要 4 支粉笔，但 k = 2，小于 4。 因此，1号学生将是需要更换粉笔的人。 让我们用 php 实现这个解决方案： 1894。找到将更换粉笔的学生 解释： 粉笔总金额： 我们将所有粉笔要求相加，得到一轮完整的总金额。 取模运算： 使用 k 取模，我们得到整轮后要分配的有效粉笔数量。 找到学生： 然后我们遍历学生，检查剩余的粉笔是否足够。第一次不够，那个学生的索引就是答案。 复杂： 时间复杂度： o(n) — 我们对数组求和，然后迭代它一次。 空间复杂度： o(1) — 仅使用几个变量，与输入大小无关。 这种方法确保即使对于大量输入也能有效解决问题。 联系链接 如果您发现本系列有帮助，请考虑在 git hub 上给 存储库 一个星星，或在您最喜欢的 社交网络 上分享该帖子?。您的支持对我来说意义重大！ 如果您想要更多类似的有用内容，请随时关注我： 领英 github