找到需要补充粉笔的学生编号
难度:
标签:
题目描述
代码结果
运行时间: 42 ms, 内存: 26.8 MB
/*
* 思路:
* 使用 Java Stream 来简化计算粉笔总数和寻找需要补充粉笔的学生。
* 先计算总粉笔使用量,再用剩余的粉笔量逐个学生判断。
*/
import java.util.stream.IntStream;
public class Solution {
public int chalkReplacer(int[] chalk, int k) {
// 计算总粉笔使用量
long total = IntStream.of(chalk).asLongStream().sum();
// 计算剩余的粉笔量
k %= total;
// 模拟每个学生使用粉笔,找到需要补充粉笔的学生
return IntStream.range(0, chalk.length)
.filter(i -> {
if (k < chalk[i]) {
return true;
}
k -= chalk[i];
return false;
})
.findFirst()
.orElse(-1); // 这个返回值理论上不会被执行
}
}
解释
方法:
题解首先计算了粉笔数组chalk的总和s,然后使用k对s求余,得到一轮完整使用chalk后剩余的粉笔数。接着,遍历chalk数组,逐个检查每个学生使用粉笔后剩余的粉笔数是否足够。如果当前学生所需的粉笔数超过剩余粉笔数k,那么这位学生就是需要补充粉笔的学生。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到了先对粉笔总和进行求余操作,这个操作的目的是什么?为什么不直接从k的初始值开始逐个减去学生的粉笔消耗?
▷🦆
如果k远大于粉笔总和s,会对算法的效率产生什么样的影响?有没有更高效的处理方法?
▷🦆
在题解的算法中,如果所有学生的粉笔需求都小于或等于k且k小于粉笔总和s,算法的返回结果会是什么?
▷🦆
在题解算法中,是否有可能出现由于整数溢出导致的错误,特别是当chalk数组中的值或k特别大时?
▷