代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
一个班级里有 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
方法一:前缀和 + 二分查找
以下是二分查找的两个通用模板:
模板 1:
boolean check(int x) {}
int search(int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
模板 2:
boolean check(int x) {}
int search(int left, int right) {
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
做二分题目时,可以按照以下步骤:
while (left < right)
,注意是 left < right
,而非 left <= right
;mid = (left + right) >> 1
;check()
函数(有时很简单的逻辑,可以不定义 check
),想一下究竟要用 right = mid
(模板 1) 还是 left = mid
(模板 2);
right = mid
,那么无脑写出 else 语句 left = mid + 1
,并且不需要更改 mid 的计算,即保持 mid = (left + right) >> 1
;left = mid
,那么无脑写出 else 语句 right = mid - 1
,并且在 mid 计算时补充 +1,即 mid = (left + right + 1) >> 1
。注意,这两个模板的优点是始终保持答案位于二分区间内,二分结束条件对应的值恰好在答案所处的位置。 对于可能无解的情况,只要判断二分结束后的 left 或者 right 是否满足题意即可。
class Solution:
def chalkReplacer(self, chalk: List[int], k: int) -> int:
s = list(accumulate(chalk))
k %= s[-1]
return bisect_right(s, k)
class Solution {
public int chalkReplacer(int[] chalk, int k) {
int n = chalk.length;
long[] preSum = new long[n + 1];
for (int i = 0; i < n; ++i) {
preSum[i + 1] = preSum[i] + chalk[i];
}
k %= preSum[n];
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (preSum[mid + 1] > k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
public:
int chalkReplacer(vector<int>& chalk, int k) {
int n = chalk.size();
vector<long long> s(n, chalk[0]);
for (int i = 1; i < n; ++i) s[i] = s[i - 1] + chalk[i];
k %= s[n - 1];
return upper_bound(s.begin(), s.end(), k) - s.begin();
}
};
func chalkReplacer(chalk []int, k int) int {
n := len(chalk)
s := make([]int, n+1)
for i := 0; i < n; i++ {
s[i+1] = s[i] + chalk[i]
}
k %= s[n]
return sort.Search(n, func(i int) bool { return s[i+1] > k })
}
impl Solution {
pub fn chalk_replacer(chalk: Vec<i32>, k: i32) -> i32 {
let pre_sum: Vec<i64> = chalk
.into_iter()
.map(|x| x as i64)
.scan(0, |state, x| {
*state += x;
Some(*state)
})
.collect();
pre_sum
.binary_search(&(k as i64 % pre_sum.last().unwrap()))
.map_or_else(|e| e, |v| v + 1) as i32
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。