【LeetCode】找到需要补充粉笔的学生编号 Java 题解

关注

发布于: 9 小时前

题目描述

一个班级里有 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 的学生没有足够的粉笔，所以他需要补充粉笔。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的每日一题，题目给出的算法思路比较清晰，可以直接模拟。在模拟的过程中，有很多的重复计算，我们可以先对 chalk 求和，然后 k 进行取余运算，提升算法的执行效率。

通过代码

class Solution {    public int chalkReplacer(int[] chalk, int k) {        int n = chalk.length;        long sum = 0;        for (int num : chalk) {            sum += num;        }        k %= sum;        int ans = -1;        for (int i = 0; i < n; i++) {            if (chalk[i] > k) {                ans = i;                return ans;            }            k -= chalk[i];        }
        return ans;    }}

复制代码

总结

上述算法的时间复杂度是 O(n), 空间复杂度是 O(1)
坚持算法每日一题，加油！

发布于: 9 小时前阅读数: 4

原文链接:【http://xie.infoq.cn/article/fa8903f7accad015572f5de0d】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】找到需要补充粉笔的学生编号 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论