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 FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Python Websockets库的使用指南

《PythonWebsockets库的使用指南》pythonwebsockets库是一个用于创建WebSocket服务器和客户端的Python库,它提供了一种简单的方式来实现实时通信,支持异步和同步... 目录一、WebSocket 简介二、python 的 websockets 库安装三、完整代码示例1.

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很