本文主要是介绍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
```
在这个问题中,为什么要使用字典来存储前缀和及其对应的索引?
使用字典来存储前缀和及其对应的索引主要有以下几个原因:
- 快速查找:可以在常数时间内快速判断某个前缀和是否已经出现过,以及获取其对应的索引。这对于及时比较和计算很关键。
- 记录历史状态:通过存储前缀和与索引的关系,能够有效地记录在遍历过程中已经出现过的前缀和情况,以便后续在计算长度等操作时能准确找到相关信息。
- 高效对比和更新:当遇到特定条件(如前缀和的差值等)时,能迅速从字典中获取相关信息进行对比和计算,从而高效地更新最长结果。这样可以避免重复计算和遍历,提高算法效率。
这篇关于1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!