【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