Medium

题目描述

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

给你一个下标从 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

提示：

  • chalk.length == n
  • 1 <= n <= 10^5
  • 1 <= chalk[i] <= 10^5
  • 1 <= k <= 10^9

解题思路

这道题的关键在于理解题目模式：学生们循环使用粉笔，我们需要找到第一个粉笔不够的学生。

思路分析：

最直观的想法是模拟整个过程，但由于 k 可能很大（最多10^9），直接模拟会超时。

优化思路：

  1. 首先计算一轮完整循环需要的粉笔总数 sum
  2. 使用取模运算 k % sum 来跳过完整的循环轮次，只关注最后不完整的一轮
  3. 在最后一轮中逐个遍历学生，找到第一个粉笔不够的学生

这样做的好处是避免了大量重复的循环计算，将时间复杂度从 O(k) 降低到 O(n)。

实现步骤：

  1. 计算所有学生一轮需要的粉笔总数
  2. 用 k 对总数取模，得到最后一轮的剩余粉笔数
  3. 遍历学生数组，当某个学生需要的粉笔数大于剩余数量时，返回该学生编号

这种方法既高效又简洁，是处理循环模拟问题的经典优化思路。

代码实现

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        long long sum = 0;
        for (int c : chalk) {
            sum += c;
        }
        
        k %= sum;
        
        for (int i = 0; i < chalk.size(); i++) {
            if (k < chalk[i]) {
                return i;
            }
            k -= chalk[i];
        }
        
        return 0;
    }
};

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        total = sum(chalk)
        k %= total
        
        for i, c in enumerate(chalk):
            if k < c:
                return i
            k -= c
        
        return 0

public class Solution {
    public int ChalkReplacer(int[] chalk, int k) {
        long sum = 0;
        foreach (int c in chalk) {
            sum += c;
        }
        
        k %= (int)sum;
        
        for (int i = 0; i < chalk.Length; i++) {
            if (k < chalk[i]) {
                return i;
            }
            k -= chalk[i];
        }
        
        return 0;
    }
}

var chalkReplacer = function(chalk, k) {
    const sum = chalk.reduce((acc, c) => acc + c, 0);
    k %= sum;
    
    for (let i = 0; i < chalk.length; i++) {
        if (k < chalk[i]) {
            return i;
        }
        k -= chalk[i];
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，需要遍历数组两次：一次计算总和，一次寻找答案
空间复杂度O(1)，只使用常数级别的额外空间

相关题目