您的位置:首页 > 新闻 > 热点要闻 > 【LeetCode】12. 小张刷题计划

【LeetCode】12. 小张刷题计划

2024/10/30 15:23:51 来源:https://blog.csdn.net/liu16659/article/details/140279297  浏览:    关键词:【LeetCode】12. 小张刷题计划

稳住,能赢!没有经验的同学在面试岗位的时候,总是显得手忙脚乱,所以多练习,把技能提升,眼界提升,接着心态放平和,不要慌张,把面试题目读懂读透彻就会大大提升赢的概率。

1. 题目

本题质量不错,是一道很好的二分法面试题。

2. 分析

2.1 贪心

本题是求小张做题时间最多的一天耗时,不是求总共耗时,所以贪心的方法解这题不行。也就是说下面这个方法是无法得到正确答案的。

class Solution:def minTime(self, time: List[int], m: int) -> int:time.sort(reverse=True)res = sum(time[m::])return res

2.2 二分法

本题如果去掉求助这一环节,那么就是一道典型的二分法题,但是加上了“求助” 这么一个操作,二分法依然可解。只不过是带上了一点儿限制条件:这个限制条件就是去除掉每天的做题中耗时最久的那道题。

在得到这个限制条件后,唯一的判断条件就是:在当前这个“每天的最大做题量”情况下,是否能在要求的天数内完成做题?这么来看,就是一道比较典型的二分法求解题了。

3. 代码

class Solution:def minTime(self, time: List[int], m: int) -> int:left, right = 0, sum(time)while(left <= right):mid = (left + right) // 2 print(left, right, mid)if self.check(mid, time, m):right = mid - 1else: left = mid + 1    return left# 每天耗时limit的情况下,是否能在m天内完成def check(self, limit, time, m):        need = 0cur_max = 0 # 某一个窗口内的最大耗时        total = 0for i in range(len(time)):cur_max = max(cur_max, time[i])if total + time[i] - cur_max <= limit:total += time[i]else: # 重置。(又是新的一天)need += 1cur_max = time[i]total = time[i]if total:need += 1return m>=need

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com