1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题

简介: 1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题

给你一份工作时间表 hours,上面记录着某一位员工每天的工作小时数。


我们认为当员工一天中的工作小时数大于 8 小时的时候,那么这一天就是「劳累的一天」。


所谓「表现良好的时间段」,意味在这段时间内,「劳累的天数」是严格 大于「不劳累的天数」。


请你返回「表现良好时间段」的最大长度。


示例 1:


输入:hours = [9,9,6,0,6,6,9]

输出:3

解释:最长的表现良好时间段是 [9,9,6]。

示例 2:


输入:hours = [6,6,6]

输出:0

提示:

  • 1 <= hours.length <= 104
  • 0 <= hours[i] <= 1

思路:使用前缀和的方法,采用字典记录前缀和

presum:前缀和的值

pre:  前缀数组

index: 索引数组


1.将时间>8的数字改为1,反之改为-1。这样问题就转化成了求大于0的最大的子数组的长度了

                     

如果pre[i]>0时,则说明从下标0开始到i的前缀和都大于0,所求的最大的长度就是i+1(因为下标从0开始,所以要加1)


2.


           


当pre[i]出现 负数或0时,我们需要找到pre[presum-1],所以我们应该标记presum第一次出现的元素(需要求最长),这一点不难理解。比如上图找pre[i]=-1时,我们需要从前往后找pre数组,看看有没有pre[j]=-2,找到第一个-2,然后最大的长度就是index[ 2: 6],长度为5

具体代码如下

以下是添加注释后的代码:
 
```python
class Solution(object):
    def longestWPI(self, hours):
        # 创建一个列表用于存储转换后的 1 或 -1
        nums = []
        for i in hours:
            if i > 8:
                nums.append(1)
            else:
                nums.append(-1)
        # 打印转换后的列表(注释掉了)
        # print(nums)
 
        # 创建一个字典用于存储前缀和及其对应的索引
        pre = {}
        ans = 0
        presum = 0
        for i in range(len(nums)):
            # 计算前缀和
            presum += nums[i]
            # 如果当前前缀和不在字典中,添加进去
            if presum not in pre:
                pre[presum] = i
            # 如果前缀和大于 0,更新最长结果
            if presum > 0:
                ans = max(ans, i + 1)
            else:
                # 如果前缀和减 1 在字典中,计算并更新最长结果
                if presum - 1 in pre:
                    # print(f"i={i} presum={presum},pre[presum-1]={pre[presum-1]}")
                    ans = max(ans, i - pre[presum - 1])
 
        return ans
```

在这个问题中,为什么要使用字典来存储前缀和及其对应的索引?

使用字典来存储前缀和及其对应的索引主要有以下几个原因:

  1. 快速查找:可以在常数时间内快速判断某个前缀和是否已经出现过,以及获取其对应的索引。这对于及时比较和计算很关键。
  2. 记录历史状态:通过存储前缀和与索引的关系,能够有效地记录在遍历过程中已经出现过的前缀和情况,以便后续在计算长度等操作时能准确找到相关信息。
  3. 高效对比和更新:当遇到特定条件(如前缀和的差值等)时,能迅速从字典中获取相关信息进行对比和计算,从而高效地更新最长结果。这样可以避免重复计算和遍历,提高算法效率。


目录
打赏
0
0
0
0
19
分享
相关文章
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
112 31
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
python实战——使用代理IP批量获取手机类电商数据
本文介绍了如何使用代理IP批量获取华为荣耀Magic7 Pro手机在电商网站的商品数据,包括名称、价格、销量和用户评价等。通过Python实现自动化采集,并存储到本地文件中。使用青果网络的代理IP服务,可以提高数据采集的安全性和效率,确保数据的多样性和准确性。文中详细描述了准备工作、API鉴权、代理授权及获取接口的过程,并提供了代码示例,帮助读者快速上手。手机数据来源为京东(item.jd.com),代理IP资源来自青果网络(qg.net)。
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
4月前
|
Python基础---类
【10月更文挑战第10天】Python类的定义
52 2
|
4月前
|
python-类属性操作
【10月更文挑战第11天】 python类属性操作列举
47 1
Python 类中引用其他类的实现详解
Python 类中引用其他类的实现详解
87 1
|
4月前
|
在 Python 中使用公共类处理接口请求的响应结果
在 Python 中使用公共类处理接口请求的响应结果
61 1
【Python篇】Python 类和对象:详细讲解(下篇)
【Python篇】Pyt hon 类和对象:详细讲解(下篇)
51 2

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等