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 或 -1nums = []for i in hours:if i > 8:nums.append(1)else:nums.append(-1)# 打印转换后的列表(注释掉了)# print(nums)# 创建一个字典用于存储前缀和及其对应的索引pre = {}ans = 0presum = 0for 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. 高效对比和更新:当遇到特定条件(如前缀和的差值等)时,能迅速从字典中获取相关信息进行对比和计算,从而高效地更新最长结果。这样可以避免重复计算和遍历,提高算法效率。

这篇关于1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1045277

相关文章

一文带你搞懂Python中__init__.py到底是什么

《一文带你搞懂Python中__init__.py到底是什么》朋友们,今天我们来聊聊Python里一个低调却至关重要的文件——__init__.py,有些人可能听说过它是“包的标志”,也有人觉得它“没... 目录先搞懂 python 模块(module)Python 包(package)是啥?那么 __in

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

使用Python实现一个优雅的异步定时器

《使用Python实现一个优雅的异步定时器》在Python中实现定时器功能是一个常见需求,尤其是在需要周期性执行任务的场景下,本文给大家介绍了基于asyncio和threading模块,可扩展的异步定... 目录需求背景代码1. 单例事件循环的实现2. 事件循环的运行与关闭3. 定时器核心逻辑4. 启动与停

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python实现word文档内容智能提取以及合成

《Python实现word文档内容智能提取以及合成》这篇文章主要为大家详细介绍了如何使用Python实现从10个左右的docx文档中抽取内容,再调整语言风格后生成新的文档,感兴趣的小伙伴可以了解一下... 目录核心思路技术路径实现步骤阶段一:准备工作阶段二:内容提取 (python 脚本)阶段三:语言风格调

Python结合PyWebView库打造跨平台桌面应用

《Python结合PyWebView库打造跨平台桌面应用》随着Web技术的发展,将HTML/CSS/JavaScript与Python结合构建桌面应用成为可能,本文将系统讲解如何使用PyWebView... 目录一、技术原理与优势分析1.1 架构原理1.2 核心优势二、开发环境搭建2.1 安装依赖2.2 验