【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 - 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

相关推荐

  1. LeetCode12. 计划

    2024-07-11 02:16:04       5 阅读
  2. leetcode100计划

    2024-07-11 02:16:04       22 阅读
  3. leetcode100计划

    2024-07-11 02:16:04       20 阅读

最近更新

  1. MySQL-显示所有错误信息

    2024-07-11 02:16:04       0 阅读
  2. Python 爬虫技术 第06节 HTTP协议与Web基础知识

    2024-07-11 02:16:04       0 阅读
  3. Oracle19.24发布,打补丁到19.24

    2024-07-11 02:16:04       0 阅读
  4. android audio 相机按键音:(一)资源加载与替换

    2024-07-11 02:16:04       0 阅读

热门阅读

  1. samout 最新版本state 逐层控制加速收敛

    2024-07-11 02:16:04       6 阅读
  2. 【个人笔记】跨域问题

    2024-07-11 02:16:04       5 阅读
  3. webpack 打包配置

    2024-07-11 02:16:04       4 阅读
  4. 人类历史时间轴

    2024-07-11 02:16:04       7 阅读
  5. 使用Python自动化收集和处理视频资源的教程

    2024-07-11 02:16:04       6 阅读
  6. 参数式确定的函数的导数公式及其推导过程

    2024-07-11 02:16:04       5 阅读