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从零打造高安全密码管理器

《Python从零打造高安全密码管理器》在数字化时代,每人平均需要管理近百个账号密码,本文将带大家深入剖析一个基于Python的高安全性密码管理器实现方案,感兴趣的小伙伴可以参考一下... 目录一、前言:为什么我们需要专属密码管理器二、系统架构设计2.1 安全加密体系2.2 密码强度策略三、核心功能实现详解

Python Faker库基本用法详解

《PythonFaker库基本用法详解》Faker是一个非常强大的库,适用于生成各种类型的伪随机数据,可以帮助开发者在测试、数据生成、或其他需要随机数据的场景中提高效率,本文给大家介绍PythonF... 目录安装基本用法主要功能示例代码语言和地区生成多条假数据自定义字段小结Faker 是一个 python

Python实现AVIF图片与其他图片格式间的批量转换

《Python实现AVIF图片与其他图片格式间的批量转换》这篇文章主要为大家详细介绍了如何使用Pillow库实现AVIF与其他格式的相互转换,即将AVIF转换为常见的格式,比如JPG或PNG,需要的小... 目录环境配置1.将单个 AVIF 图片转换为 JPG 和 PNG2.批量转换目录下所有 AVIF 图

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

详解如何通过Python批量转换图片为PDF

《详解如何通过Python批量转换图片为PDF》:本文主要介绍如何基于Python+Tkinter开发的图片批量转PDF工具,可以支持批量添加图片,拖拽等操作,感兴趣的小伙伴可以参考一下... 目录1. 概述2. 功能亮点2.1 主要功能2.2 界面设计3. 使用指南3.1 运行环境3.2 使用步骤4. 核

Python 安装和配置flask, flask_cors的图文教程

《Python安装和配置flask,flask_cors的图文教程》:本文主要介绍Python安装和配置flask,flask_cors的图文教程,本文通过图文并茂的形式给大家介绍的非常详细,... 目录一.python安装:二,配置环境变量,三:检查Python安装和环境变量,四:安装flask和flas

使用Python自建轻量级的HTTP调试工具

《使用Python自建轻量级的HTTP调试工具》这篇文章主要为大家详细介绍了如何使用Python自建一个轻量级的HTTP调试工具,文中的示例代码讲解详细,感兴趣的小伙伴可以参考一下... 目录一、为什么需要自建工具二、核心功能设计三、技术选型四、分步实现五、进阶优化技巧六、使用示例七、性能对比八、扩展方向建

基于Python打造一个可视化FTP服务器

《基于Python打造一个可视化FTP服务器》在日常办公和团队协作中,文件共享是一个不可或缺的需求,所以本文将使用Python+Tkinter+pyftpdlib开发一款可视化FTP服务器,有需要的小... 目录1. 概述2. 功能介绍3. 如何使用4. 代码解析5. 运行效果6.相关源码7. 总结与展望1

使用Python实现一键隐藏屏幕并锁定输入

《使用Python实现一键隐藏屏幕并锁定输入》本文主要介绍了使用Python编写一个一键隐藏屏幕并锁定输入的黑科技程序,能够在指定热键触发后立即遮挡屏幕,并禁止一切键盘鼠标输入,这样就再也不用担心自己... 目录1. 概述2. 功能亮点3.代码实现4.使用方法5. 展示效果6. 代码优化与拓展7. 总结1.

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经