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

LeetCode-2391. 收集垃圾的最少总时间【数组 字符串 前缀和】

LeetCode-2391. 收集垃圾的最少总时间【数组 字符串 前缀和】

  • 题目描述:
  • 解题思路一:处理垃圾和路程单独计算。
  • 解题思路二:逆向思维,计算多走的路
  • 解题思路三:只记录,当前t需要计算几次

题目描述:

给你一个下标从 0 开始的字符串数组 garbage ,其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 ‘M’ ,‘P’ 和 ‘G’ ,但可能包含多个相同字符,每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。

同时给你一个下标从 0 开始的整数数组 travel ,其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。

城市里总共有三辆垃圾车,分别收拾三种垃圾。每辆垃圾车都从房子 0 出发,按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。

任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候,另外两辆车 不能 做任何事情。

请你返回收拾完所有垃圾需要花费的 最少 总分钟数。

示例 1:

输入:garbage = [“G”,“P”,“GP”,“GG”], travel = [2,4,3]
输出:21
解释:
收拾纸的垃圾车:

  1. 从房子 0 行驶到房子 1
  2. 收拾房子 1 的纸垃圾
  3. 从房子 1 行驶到房子 2
  4. 收拾房子 2 的纸垃圾
    收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
    收拾玻璃的垃圾车:
  5. 收拾房子 0 的玻璃垃圾
  6. 从房子 0 行驶到房子 1
  7. 从房子 1 行驶到房子 2
  8. 收拾房子 2 的玻璃垃圾
  9. 从房子 2 行驶到房子 3
  10. 收拾房子 3 的玻璃垃圾
    收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
    由于没有金属垃圾,收拾金属的垃圾车不需要花费任何时间。
    所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。

示例 2:

输入:garbage = [“MMM”,“PGM”,“GP”], travel = [3,10]
输出:37
解释:
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。

提示:

2 <= garbage.length <= 105
garbage[i] 只包含字母 ‘M’ ,‘P’ 和 ‘G’ 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100

解题思路一:处理垃圾和路程单独计算。

  1. 所有垃圾事一定要处理完的!for g in garbage: ans += len(g)
  2. 反向遍历garbage数组,得到每个垃圾车需要到达的最远距离,即可计算出所需路程时间。
class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:n = len(garbage)ans = 0for g in garbage:ans += len(g)G, M, P = 0, 0, 0for i in range(len(garbage) - 1, 0, -1):if 'G' in garbage[i]:G = ians += sum(travel[:G])breakfor i in range(len(garbage) - 1, 0, -1):if 'M' in garbage[i]:M = ians += sum(travel[:M])breakfor i in range(len(garbage) - 1, 0, -1):if 'P' in garbage[i]:P = ians += sum(travel[: P])breakreturn ans# 简化
class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:n = len(garbage)ans = sum(map(len, garbage))for c in "GMP":for i, g in enumerate(reversed(garbage)):if c in g:ans += sum(travel[:n-i-1])breakreturn ans

时间复杂度:O(n)
空间复杂度:O(1)

解题思路二:逆向思维,计算多走的路

class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:ans = sum(map(len, garbage)) + sum(travel) * 3for c in "MPG":for g, t in zip(reversed(garbage), reversed(travel)):if c in g:breakans -= t  # 没有垃圾 c,多跑了return ans

时间复杂度:O(n)
空间复杂度:O(1)

解题思路三:只记录,当前t需要计算几次

在这里插入图片描述

class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:ans = len(garbage[0])seen = set()for g, t in zip(reversed(garbage), reversed(travel)):seen.update(g)ans += len(g) + t * len(seen)return ans

时间复杂度:O(n)
空间复杂度:O(n)


创作不易,观众老爷们请留步… 动起可爱的小手,点个赞再走呗 (๑◕ܫ←๑)
欢迎大家关注笔者,你的关注是我持续更博的最大动力


原创文章,转载告知,盗版必究



在这里插入图片描述


在这里插入图片描述
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠

相关文章:

LeetCode-2391. 收集垃圾的最少总时间【数组 字符串 前缀和】

LeetCode-2391. 收集垃圾的最少总时间【数组 字符串 前缀和】 题目描述&#xff1a;解题思路一&#xff1a;处理垃圾和路程单独计算。解题思路二&#xff1a;逆向思维&#xff0c;计算多走的路解题思路三&#xff1a;只记录&#xff0c;当前t需要计算几次 题目描述&#xff1a;…...

再有人说数字孪生大屏没有用,用这8条怼回去。

数字孪生大屏之所以受到欢迎&#xff0c;主要有以下几个原因&#xff1a; 实时数据可视化 数字孪生大屏可以将实时数据以直观的可视化形式展示出来&#xff0c;让用户能够一目了然地了解数据的状态和趋势。这样可以帮助用户更好地理解和分析数据&#xff0c;及时做出决策和调…...

蓝桥杯练习系统(算法训练)ALGO-946 Q神的足球赛

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 足球赛上&#xff0c;只见Q神如闪电般的速度带球时而左&#xff0c;时而右&#xff0c;时而前&#xff0c;时而后&#xff…...

【Android】Kotlin学习之Kotlin方法的声明和传参

方法声明 普通类的方法 静态类的方法 不需要构建实例对象, 可以通过类名直接访问静态方法 : NumUtil.double(1) companion object 伴生类的方法 使用companion object 在普通类里定义静态方法 参数 括号内传入方法 : 当参数是方法时, 并且是最后一个参数 , 可以使用括号外…...

微信小程序 17:小程序使用 npm 包和组件应用

目前&#xff0c;小程序中已经支持实用 npm 安装第三方包&#xff0c;从而提高小程序的开发效率&#xff0c;但是在小程序中使用 npm 包有三个限制&#xff1a; 不支持 Node.js内置库的包不支持依赖于浏览器内置对象的包不支持依赖于 C插件的包 Vant Weapp Vant Weapp是有赞…...

【mysql篇】执行delete删除大量数据后,磁盘未清空,为什么?

目录 迁移脚本删除数据以及备份数据 解决方法OPTIMIZE TABLE二进制日志按月生成数据 最近某个项目虽说用户量不大&#xff0c;但是&#xff0c;单表的数据量越来越大&#xff0c;mysql一般单表超过千万级别后&#xff0c;性能直线下降&#xff0c;所以利用shardingphere按月做了…...

【Qt 学习笔记】Qt常用控件 | 多元素控件 | Tree Widget的说明及介绍

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt常用控件 | 多元素控件 | Tree Widget的说明及介绍 文章编号&#x…...

在Mars3d实现cesium的ImageryLayer自定义瓦片的层级与原点

需要自定义瓦片层级和原点&#xff0c;所以需要自己写第三方图层&#xff0c;但是之前写的很多方法&#xff0c;图层控制和显隐以及透明度&#xff0c;需要跟之前的交互一直&#xff0c;改动量太大的话不划算&#xff0c;所以直接看Mars3d的layer基类&#xff0c;把重写的image…...

logback日志持久化

1、问题描述 使用logback持久化记录日志。 2、我的代码 logback是Springboot框架里自带的&#xff0c;所以只要引入“spring-boot-starter”就行了。无需额外引入logback依赖。 pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns&…...

函数原型(Function Prototype)、函数定义(Function Definition)和函数声明(Function Declaration)

函数原型&#xff08;Function Prototype&#xff09;、函数定义&#xff08;Function Definition&#xff09;和函数声明&#xff08;Function Declaration&#xff09;在C和C等编程语言中扮演着不同的角色&#xff0c;但它们有时在概念上可能会有些重叠。下面是它们之间的主要…...

Go有无缓冲channel的区别

无缓冲的channel channel的默认类型就是无缓冲的。当一个数据被发送到无缓冲的channel中&#xff0c;发送操作会被阻塞&#xff0c;知道有另一个goroutine从这个channel中接收这个数据。同样&#xff0c;当试图从一个无缓冲的channel中接收数据时&#xff0c;如果没有数据可以…...

【全开源】Fastflow工作流系统(源码搭建/上线/运营/售后/维护更新)

一款基于FastAdminThinkPHP开发的可视化工作流程审批插件&#xff0c;帮助用户基于企业业务模式和管理模式自行定义所需的各种流程应用&#xff0c;快速构建企业自身的流程管控体系&#xff0c;快速融合至企业协同OA办公系统。 提供全部无加密服务端源码和前端源代码&#xff0…...

超越传统游戏:生成式人工智能对游戏的变革性影响

人工智能&#xff08;AI&#xff09;在游戏中的应用 游戏产业是一个充满活力、不断发展的领域&#xff0c;人工智能&#xff08;AI&#xff09;的融入对其产生了重大影响。这一技术进步彻底改变了游戏的开发、玩法和体验方式。本文分析的重点是传统人工智能和生成式人工智能在游…...

SpringCloud微服务之Eureka、Ribbon、Nacos详解

SpringCloud微服务之Eureka、Ribbon、Nacos详解 1、认识微服务1.1、单体架构1.2、分布式架构1.3、微服务1.4、SpringCloud 2、服务拆分与远程调用2.1、服务拆分的原则2.2、服务拆分示例2.2、提供者与消费者 3、Eureka注册中心3.1、Eureka的结构和作用3.2、搭建eureka-server3.2…...

五角钱的程序员 | Kafka 是什么?

本文来源公众号“五角钱的程序员”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;Kafka 是什么&#xff1f; 你是一个程序员&#xff0c;假设你维护了两个服务 A 和 B。B 服务每秒只能处理 100 个消息&#xff0c;但 A 服务却每秒…...

C++中合成的默认构造函数的访问权限

问题 我们知道&#xff0c;在C中&#xff0c;如果没有为一个类显式定义构造函数&#xff0c;那么编译器会为我们隐式地定义一个默认构造函数。那么&#xff0c;你有没有想过&#xff0c;这个隐式定义的默认构造函数&#xff08;合成的默认构造函数&#xff09;的访问权限是什么…...

【前端】桌面版docker并部署前端项目

环境 win10专业版 2004 , 需科学 官网下载安装包并安装4.29.0版本 终端输入 wsl --installdocker桌面版和模拟器只能选一个&#xff0c;不然一直转圈圈 镜像配置加速&#xff0c;在settings—>docker engine下 {"builder": {"gc": {"defaultKee…...

发布GPT-5的方式可能会与以往不同;开源vocode使用 AI 自动拨打电话;开源gpt智能对话客服工具;AI自动写提示词

✨ 1: vocode 用AI通过声音与用户进行实时交流 Vocode是一个旨在帮助开发者快速构建基于声音的大型语言模型&#xff08;LLM&#xff09;应用程序的开源库。简单来说&#xff0c;如果你想要开发一个能够通过声音与用户进行实时交流的应用&#xff0c;比如电话机器人、语音助手…...

Linux 作业管理 (bg, fg, jobs, kill)

bg 和 fg 是用来管理作业&#xff08;在 Unix/Linux 命令行下运行的进程&#xff09;的命令。 1. bg 命令 bg 命令用于将作业&#xff08;job&#xff09;放到后台运行。当你在终端中运行一个命令或程序时&#xff0c;它会占用当前终端的控制&#xff0c;如果你想让这个任务在…...

springboot Redis 支持星号(*) 包括注解@Cache

通过自定义CacheManager Bean来实现 bean Autowiredprivate RedisConnectionFactory redisConnectionFactory;/*** 管理缓存** return*///缓存管理器PrimaryBeanOverridepublic CacheManager cacheManager() {// 使用自定义的缓存配置初始化一个cacheManagerreturn new Custom…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...