class Solution {
public:
int chalkReplacer(vector<int>& chalk, int k) {
}
};
1894. 找到需要补充粉笔的学生编号
一个班级里有 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 == n1 <= n <= 1051 <= chalk[i] <= 1051 <= k <= 109原站题解
golang 解法, 执行用时: 112 ms, 内存消耗: 8.3 MB, 提交时间: 2023-09-25 15:54:54
func chalkReplacer(chalk []int, k int) int {
if chalk[0] > k {
return 0
}
n := len(chalk)
for i := 1; i < n; i++ {
chalk[i] += chalk[i-1]
if chalk[i] > k {
return i
}
}
k %= chalk[n-1]
return sort.SearchInts(chalk, k+1)
}
javascript 解法, 执行用时: 84 ms, 内存消耗: 50.6 MB, 提交时间: 2023-09-25 15:54:31
/**
* @param {number[]} chalk
* @param {number} k
* @return {number}
*/
var chalkReplacer = function(chalk, k) {
const n = chalk.length;
if (chalk[0] > k) {
return 0;
}
for (let i = 1; i < n; ++i) {
chalk[i] += chalk[i - 1];
if (chalk[i] > k) {
return i;
}
}
k %= chalk[n - 1];
return binarySearch(chalk, k);
};
const binarySearch = (arr, target) => {
let low = 0, high = arr.length - 1;
while (low < high) {
const mid = Math.floor((high - low) / 2) + low;
if (arr[mid] <= target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
cpp 解法, 执行用时: 112 ms, 内存消耗: 72.9 MB, 提交时间: 2023-09-25 15:53:22
class Solution {
public:
int chalkReplacer(vector<int>& chalk, int k) {
int n = chalk.size();
if (chalk[0] > k) {
return 0;
}
for (int i = 1; i < n; ++i) {
chalk[i] += chalk[i - 1];
if (chalk[i] > k) {
return i;
}
}
k %= chalk.back();
return upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin();
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 56.5 MB, 提交时间: 2023-09-25 15:53:00
class Solution {
// 前缀和 + 二分查找
public int chalkReplacer(int[] chalk, int k) {
int n = chalk.length;
if (chalk[0] > k) {
return 0;
}
for (int i = 1; i < n; ++i) {
chalk[i] += chalk[i - 1];
if (chalk[i] > k) {
return i;
}
}
k %= chalk[n - 1];
return binarySearch(chalk, k);
}
public int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
if (arr[mid] <= target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
java 解法, 执行用时: 1 ms, 内存消耗: 56.5 MB, 提交时间: 2023-09-25 15:52:30
class Solution {
public int chalkReplacer(int[] chalk, int k) {
int n = chalk.length;
long total = 0;
for (int num : chalk) {
total += num;
}
k %= total;
int res = -1;
for (int i = 0; i < n; ++i) {
if (chalk[i] > k) {
res = i;
break;
}
k -= chalk[i];
}
return res;
}
}
golang 解法, 执行用时: 116 ms, 内存消耗: 8.3 MB, 提交时间: 2023-09-25 15:52:18
func chalkReplacer(chalk []int, k int) int {
total := 0
for _, v := range chalk {
total += v
}
k %= total
for i, c := range chalk {
if k < c {
return i
}
k -= c
}
return 0
}
python3 解法, 执行用时: 60 ms, 内存消耗: 26.6 MB, 提交时间: 2023-09-25 15:51:16
class Solution:
def chalkReplacer(self, chalk: List[int], k: int) -> int:
s = sum(chalk)
m = k % s
for i, c in enumerate(chalk):
if m < c:
return i
else:
m -= c