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

链接：1894.找到需要补充粉笔的学生编号
难度：Medium
标签：数组、二分查找、前缀和、模拟
简介：请你返回需要 补充 粉笔的学生 编号 。

题解 1 - typescript

• 编辑时间：2021-09-10
• 执行用时：1052ms
• 内存消耗：49.6MB
• 编程语言：typescript
• 解法介绍：循环相减。

function chalkReplacer(chalk: number[], k: number): number {
  const sum = chalk.reduce((total, cur) => total + cur, 0);
  while (k >= sum) k -= sum;
  let idx = 0;
  while (k >= chalk[idx]) k -= chalk[idx++];
  return idx;
}

题解 2 - typescript

• 编辑时间：2021-09-10
• 执行用时：796ms
• 内存消耗：54.2MB
• 编程语言：typescript
• 解法介绍：二分+前缀和。

function chalkReplacer(chalk: number[], k: number): number {
  let sum = 0;
  const sums: number[] = [0];
  const n = chalk.length;
  for (let i = 0; i < n; i++) sums.push((sum += chalk[i]));
  while (k >= sum) k -= sum;
  return find(k) - 1;
  function find(num: number) {
    let l = 0;
    let r = n;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (sums[mid] > num) r = mid;
      else l = mid + 1;
    }
    return l;
  }
}