每日leetcode第0072天 1894. Find the Student that Will Replace the Chalk

今天是教师节,我们做一道找到需要补充粉笔的学生编号的题目。

这道题可以使用模拟算法,但是可能时间会比较久。

所以我们可以考虑加速,将所有的同学一轮所需要的的粉笔数量计算出来,用总粉笔取余。

再进行模拟。

 

但我们也可以不再进行模拟,而是利用二分查找的知识来查找。

有同学可能会问,那二分查找需要建立前缀和数组并且计算,也需要花时间,并且需要空间。

这里其实我们在求和的时候就需要遍历都加一遍了,所以求前缀和和求和是可以算作同一步的,不会花更多时间。

并且我们有了前缀和数组后原数组并没有任何用处,我们可以在原数组上进行修改,不会需要新的空间。

我手写了老半天二分法,算好后上传代码想了一下还是直接利用upper_bound函数算了。

但并不是说手写二分法没有必要练习,练习可以让我们思路更清晰代码更精进。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。