赞
踩
稳住,能赢!没有经验的同学在面试岗位的时候,总是显得手忙脚乱,所以多练习,把技能提升,眼界提升,接着心态放平和,不要慌张,把面试题目读懂读透彻就会大大提升赢的概率。
本题质量不错,是一道很好的二分法面试题。
本题是求小张做题时间最多的一天耗时,不是求总共耗时,所以贪心的方法解这题不行。也就是说下面这个方法是无法得到正确答案的。
class Solution:
def minTime(self, time: List[int], m: int) -> int:
time.sort(reverse=True)
res = sum(time[m::])
return res
本题如果去掉求助这一环节,那么就是一道典型的二分法题,但是加上了“求助” 这么一个操作,二分法依然可解。只不过是带上了一点儿限制条件:这个限制条件就是去除掉每天的做题中耗时最久的那道题。
在得到这个限制条件后,唯一的判断条件就是:在当前这个“每天的最大做题量”情况下,是否能在要求的天数内完成做题?这么来看,就是一道比较典型的二分法求解题了。
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 - 1 else: left = mid + 1 return left # 每天耗时limit的情况下,是否能在m天内完成 def check(self, limit, time, m): need = 0 cur_max = 0 # 某一个窗口内的最大耗时 total = 0 for i in range(len(time)): cur_max = max(cur_max, time[i]) if total + time[i] - cur_max <= limit: total += time[i] else: # 重置。(又是新的一天) need += 1 cur_max = time[i] total = time[i] if total: need += 1 return m>=need
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。