当前位置: 首页 > news >正文

【数据结构-前缀哈希】力扣1124. 表现良好的最长时间段

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

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

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

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

示例 1:
输入:hours = [9,9,6,0,6,6,9]
输出:3
解释:最长的表现良好时间段是 [9,9,6]。

示例 2:
输入:hours = [6,6,6]
输出:0
在这里插入图片描述

前缀+哈希

class Solution {
public:int longestWPI(vector<int>& hours) {int sum = 0, ans = 0;       unordered_map<int, int> group = {{0, -1}};for(int i = 0;i < hours.size();i++){sum += (hours[i] > 8) ? 1 : -1;if(sum > 0){ans = i + 1;}else if(group.find(sum-1) != group.end()){ans = max(ans, i - group[sum - 1]);}if(group.find(sum) == group.end()){group[sum] = i;}}return ans;}
};

这一题前缀+哈希并不是空间最优,最优空间是使用贪心+栈的做法,虽然空间复杂度都是O(n),但是实际的空间使用可能高于 O(n),因为当哈希表需要扩展时,会预留更多的空间以减少哈希冲突。

sum += (hours[i] > 8) ? 1 : -1;

这题的思想就是将大于8小时的天数记+1,小于等于8小时的天数记-1。

 if(sum > 0){ans = i + 1;}else if(group.find(sum-1) != group.end()){ans = max(ans, i - group[sum - 1]);}

“表现良好的时间段”有两种情况,一种是当前的sum能在哈希表中匹配到sum - 1时(如果是匹配sum的话,这个子段是「劳累的天数」等于「不劳累的天数」。)第二种情况是当sum大于0的时候,这时候说明整个数组都是表现良好的时间段。

if(group.find(sum) == group.end()){group[sum] = i;
}

并且,只哈希表中的键只保存第一次出现的位置。

相关文章:

【数据结构-前缀哈希】力扣1124. 表现良好的最长时间段

给你一份工作时间表 hours&#xff0c;上面记录着某一位员工每天的工作小时数。 我们认为当员工一天中的工作小时数大于 8 小时的时候&#xff0c;那么这一天就是「劳累的一天」。 所谓「表现良好的时间段」&#xff0c;意味在这段时间内&#xff0c;「劳累的天数」是严格 大…...

电商平台产品ID|CDN与预渲染|前端边缘计算

技术实现 都是通过ID拿到属性&#xff0c;进行预渲染html&#xff0c;通过 oss 分发出去 详情页这种基本都是通过 ssr 渲染出来&#xff0c;然后上缓存 CDN 分发到边缘节点来处理&#xff0c;具体逻辑可以参考 淘宝——EdgeRoutine边缘计算&#xff08;CDNServerless 边缘计算…...

LATTICE进阶篇DDR2--(4)DDR2 IP核总结

一、IP核的时钟框架 1片DDR2的接口是16位&#xff0c;且DDR2是双边沿读取的&#xff0c; 故当DDR2芯片的时钟为200M时&#xff0c;右侧DDR2芯片上的数据吞吐率为200M*2*16b&#xff0c;左侧数据吞吐率为200M*32b&#xff0c;左右两侧数据吞吐量相等。 根据上规律可知&#xf…...

windows下php安装kafka

下载zookeeper Kafka 依赖 Zookeeper 进行分布式协调&#xff0c;所以需要下载Zookeeper &#xff0c;当然你也可以使用kafka包里自带的一个默认配置的 Zookeeper。这里我们单独下载一个 访问Zookeeper官方下载页面在页面中找到最新的稳定版本&#xff0c;点击相应的下载链接…...

【wiki知识库】09.欢迎页面展示(浏览量统计)SpringBoot部分

&#x1f34a; 编程有易不绕弯&#xff0c;成长之路不孤单&#xff01; 大家好&#xff0c;我是熊哈哈&#xff0c;这个项目从我接手到现在有了两个多月的时间了吧&#xff0c;其实本来我在七月初就做完的吧&#xff0c;但是六月份的时候生病了&#xff0c;在家里休息了一个月的…...

数据分析与应用:微信-情人节红包流向探索分析

目录 0 需求描述 1 红包发送方用户的基本信息缺失率有多高?(即有多少红包发送方用户无法在用户基本信息表中匹配? 2 哪一组红包金额的拒收率最高? 3、最受二线城市欢迎的红包金额为?(即发出次数最多) 4 北上广深 4 大城市中,哪座城市的男性用户发出的 520 红包比例…...

SQL,获取 ID 的历史状态

sas系统的表tb存储病人的医疗历史记录&#xff0c;当Visit_codeSurgery时表示手术&#xff0c;Visit_codeOffice表示咨询&#xff0c;每个病人有多条Visit_code&#xff0c;有时只有Surgery或只有Office&#xff1a;IdVisit_DateVisit_codeA305/15/2004SurgeryA302/5/2005Offic…...

阅文集团:摇不动的IP摇钱树

把IP当成摇钱树&#xff0c;要做“东方迪士尼” 今天我们聊——阅文集团 《热辣滚烫》《庆余年2》《与凤行》和《玫瑰的故事》很熟悉吧&#xff1f;影视“四连爆”&#xff0c; 阅文集团交出一份亮眼半年报&#xff0c;时隔两年&#xff0c;重启增长。 跟IP相关业务对收入贡献…...

ETL数据集成丨将SQL Server数据同步至Oracle的具体实现

一、背景 在构建企业级数据架构时&#xff0c;将SQL Server数据库的数据同步至数仓数据库&#xff08;如Oracle&#xff09;是一项至关重要的任务。这一过程不仅促进了跨系统数据的一致性与可用性&#xff0c;还为数据分析、商业智能以及决策支持系统提供了坚实的数据基础。 …...

20240814软考架构-------软考51-55答案解析

每日打卡题51-55答案 51、【2017年真题】 难度&#xff1a;一般 系统移植也是系统构建的一种实现方法&#xff0c;在移植工作中&#xff0c; 需要最终确定移植方法。 A.计划阶段 B.准备阶段 C.转换阶段 D.验证阶段 答案&#xff1a;A 解析&#xff1a; 移植工作大体上分为计划…...

JavaEE 的入门

1. 学习JavaEE Java EE(Java Platform Enterprise Edition), Java 平台企业版. 是JavaSE的扩展, ⽤于解决企业级的开 发需求, 所以也可以称之为是⼀组⽤于企业开发的Java技术标准. 所以, 学习JavaEE主要是学习Java在 企业中如何应⽤. 前⾯学习的是Java基础, JavaEE 主要学习Jav…...

vue3+ts 前端word文档下载文件时不预览直接下载方法(支持 doc / excel / ppt / pdf 等)

前端word文档下载文件时不预览直接下载方法支持 doc / excel / ppt / pdf 等 根据需要&#xff0c;要实现一个下载文档的需要 最简单的方法就是使用a标签 如果是相同域可以直接下载&#xff0c;但如果是不同域的&#xff0c;就会先打开一个预览页&#xff0c;在预览页再点下载…...

Java 空值与null 形参与实参学习

Java系列文章目录 文章目录 Java系列文章目录一、前言二、学习内容&#xff1a;三、问题描述四、解决方案&#xff1a;4.1 空值与null的区别4.1.1 空值&#xff08;Empty Value&#xff09;4.1.2 Null 4.2 形参与实参区别 五、总结&#xff1a;5.1 学习总结&#xff1a; 一、前…...

【QT常用技术讲解】QTableView添加QCheckBox、QPushButton

前言 QT展示列表信息的时候通常用到列表&#xff08;比如用户信息、机构信息、设备信息等菜单&#xff09;&#xff0c;当需要对某列进行修改、删除操作时&#xff0c;就需要加入按钮&#xff08;QPushButton&#xff09;&#xff0c;当需要对多列进行右键菜单操作时&#xff0…...

linux监控命令

在 Linux 中&#xff0c;有许多命令可以用于监控系统的性能和状态。以下是一些常用的监控命令及其用途&#xff1a; 1. top​ 和 htop​ top ​top​ 命令显示当前系统中运行的进程列表及其资源使用情况。 top​​ ‍ htop ​htop​ 是 top​ 命令的增强版&#xff0c;提…...

SpringBoot入门笔记

本文是看黑马老师讲课视频学习笔记整理 目录 入门案例 基于IDEA联网 基于Springboot官网创建 基于阿里云创建项目 手工创建 隐藏文件 入门案例解析: parent​编辑 starter 引导类 内嵌tomcat 入门案例 基于IDEA联网 RestController RequestMapping("/books&…...

python 华为od 单词接龙

sd[word,dd,da,dc,dword,d] # 计算出下一个接龙单词 def jl(sd,st):# sd.remove(st)sd list(set(sd))sends list(st)[-1]lg []sd.sort()for i in sd:if i.startswith(sends):lg.append((i, len(i)))if lg[]:return 0,0lg.sort(keylambda x: x[1],reverseTrue)maxlen lg[0][…...

Vue+Echart实现地图省市区三级下钻

采用在线地图数据&#xff0c;整体简约&#xff0c;扩展也方便 参考 <template><div><div ref"mapContainer" style"width: 100%; height: 600px;"></div><button click"goBack">返回上一级</button></…...

Apache Tomcat 信息泄露漏洞排查处理CVE-2024-21733)

一、漏洞描述 Apache Tomcat作为一个流行的开源Web服务器和Java Servlet容器并用于很多中小型项目的开发中。其中,Coyote作为Tomcat的连接器组件,是Tomcat服务器提供的供客户端访问的外部接口,客户端通过Coyote与服务器建立链接、发送请求并且接收响应。 近日发现Apache To…...

51单片机-LED实验

实现了按下独立按键&#xff0c;LED灯亮&#xff0c;松开独立按键&#xff0c;LED灯灭的功能 #include <8051.h>void delayms(unsigned char t){unsigned char i,j;i900;jt;do{jt;while (j--){/* code */}}while(i--); }void main(){// P2_01;while (1){if(P3_00){delay…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...