找到需要补充粉笔的学生编号

标签: 数组 二分查找 前缀和 模拟

难度: Medium

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[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 <= 105
  • 1 <= chalk[i] <= 105
  • 1 <= k <= 109

Submission

运行时间: 42 ms

内存: 26.8 MB

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        s = sum(chalk)
        k %= s 
        print(k)
        for i, x in enumerate(chalk):
            if x > k:
                return i
            else:
                k -= x

Explain

题解首先计算了粉笔数组chalk的总和s，然后使用k对s求余，得到一轮完整使用chalk后剩余的粉笔数。接着，遍历chalk数组，逐个检查每个学生使用粉笔后剩余的粉笔数是否足够。如果当前学生所需的粉笔数超过剩余粉笔数k，那么这位学生就是需要补充粉笔的学生。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        s = sum(chalk)  # 计算粉笔总消耗
        k %= s  # 计算经过多轮循环后剩余的粉笔
        for i, x in enumerate(chalk):  # 遍历每个学生的粉笔消耗
            if x > k:  # 如果当前学生的需要大于剩余的粉笔
                return i  # 返回当前学生的编号
            else:
                k -= x  # 减去当前学生消耗的粉笔，为下一个学生准备

Explore

求余操作是为了简化问题，因为如果k非常大，直接从k开始减去学生的粉笔消耗将会非常低效。通过对s求余，我们可以快速得到经过多次完整的循环后剩下的粉笔数，这样只需处理一轮粉笔消耗即可，大大提高了算法的效率。

如果k远大于粉笔总和s，不使用求余操作的话，直接逐个减去会导致执行多次无意义的循环，影响效率。已经采用的求余方法是一种高效处理方法，它可以避免多次重复计算，快速缩减问题规模。

在这种情况下，算法会在完成一轮遍历后，k仍然大于0，此时会继续进行第二轮遍历。但这种情况在题设中应该不会出现，因为每轮遍历结束时，k应该被减至小于下一个学生的粉笔需求，从而返回当前学生的编号。如果k小于s且每个学生的需求都不超过k，则在遍历中必有某个学生的需求超过当前剩余的k，触发返回条件。

在Python中，整数类型可以自动转换为长整型，因此通常不会出现溢出错误。但在其他一些编程语言中，如C++或Java，确实需要考虑整数溢出的问题。在这些语言中，应当确保变量类型足够大，或者在累加和求余时采用安全措施来防止溢出。