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

马克 扎克伯格大学做的网站百度推广营销页

马克 扎克伯格大学做的网站,百度推广营销页,品牌网图片新闻2003年下一条文章,做微信活动是做网站还是做小程序好LeetCode-2391. 收集垃圾的最少总时间【数组 字符串 前缀和】 题目描述:解题思路一:处理垃圾和路程单独计算。解题思路二:逆向思维,计算多走的路解题思路三:只记录,当前t需要计算几次 题目描述:…

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)


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


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



在这里插入图片描述


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

http://www.yidumall.com/news/53707.html

相关文章:

  • 兰州网站建设公做网站的好处
  • 凡科做的网站百度不到友链外链app
  • 如何做网站seo优化seo优化在哪里学
  • 网站可以做多少个关键词网站开发的步骤
  • 网站颜色表株洲百度seo
  • 泰安企业网站建设博客营销
  • 做视频网站资质aso关键词搜索优化
  • 滨州网站网站建设上海百度推广优化公司
  • java jsp网站开发购买域名的网站
  • 红色为主的网站惠州seo全网营销
  • 安防网站建设优点世界搜索引擎大全
  • 网站300兆是多少钱青岛的seo服务公司
  • 电子商务网站建设与管理期末考试网络营销的目的是什么
  • 电子商务网站开发教程课后习题公司软文代写
  • 成都自由行攻略最详细泰州百度seo公司
  • 动态网站建设课程百度首页广告多少钱
  • 网站制作素材河源今日头条新闻最新
  • 外贸网站和内贸中国新闻网
  • dedecms win8风格网站模板seo排名点击软件
  • 郑州炫彩网站建设在线网站排名工具
  • 动画网站欣赏广州做seo公司
  • 青海企业网站建设开发在线网页制作系统搭建
  • solaris.wordpress太原seo快速排名
  • web开发兼职网站开发如何创建网址
  • 贵州建设工程招标协会网站口碑营销成功案例
  • 网站开发职责个人网站模板建站
  • 图片库站长之家seo查找
  • 网站建设介绍ppt模板下载想要导航推广网页怎么做
  • 北京住房城乡建设网站谷歌推广公司哪家好
  • dw做网站字体 别人 电脑steam交易链接是什么