前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日算法系列【LeetCode 495】提莫攻击

每日算法系列【LeetCode 495】提莫攻击

作者头像
godweiyang
发布2020-03-24 10:51:34
4140
发布2020-03-24 10:51:34
举报
文章被收录于专栏:算法码上来

题目描述

在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄,他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。

兔宝宝提莫

现在,给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间,你需要输出艾希的中毒状态总时长。

你可以认为提莫在给定的时间点进行攻击,并立即使艾希处于中毒状态。

示例1

代码语言:javascript
复制
输入:
[1,4], 2
输出:
4
解释:
在第 1 秒开始时,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒钟结束。
在第 4 秒开始时,提莫再次攻击艾希,使得艾希获得另外 2 秒的中毒时间。
所以最终输出 4 秒。

示例2

代码语言:javascript
复制
输入:
[1,2], 2
输出:
3
解释:
在第 1 秒开始时,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒钟结束。
但是在第 2 秒开始时,提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加,提莫在第 2 秒开始时的这次攻击会在第 3 秒钟结束。
所以最终输出 3。

题解

因为数组是时间序列,所以是给你排好序的,不需要你自己排序。

那么对于 来说,如果 的话,就说明前一时刻的中毒效果已经过去了,那么当前时刻的中毒效果持续时间都是属于当前时刻的,答案加上 就行了。但是如果 ,那么前一时刻的中毒效果还在,等前一时刻的中毒效果过去了,剩下的中毒时间才能算是当前时刻的,而扣除掉上一时刻剩余的时间为 。所以最后属于当前时刻的中毒时间只要取 和 的最小值就行了。

最终时间复杂度为 ,空间复杂度为 。

代码

c++

代码语言:javascript
复制
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size();
        int res = n ? duration : 0;
        for (int i = 1; i < n; ++i) {
            res += min(timeSeries[i]-timeSeries[i-1], duration);
        }
        return res;
    }
};

python

代码语言:javascript
复制
class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        n = len(timeSeries)
        res = 0 if n==0 else duration
        for i in range(1, n):
            res += min(timeSeries[i]-timeSeries[i-1], duration)
        return res

后记

这题难度其实称不上中等,选取这道题完全是因为有我最爱的小提莫!

如果有同样喜爱英雄联盟的召唤师(小姐姐最棒了),可以加我好友一起开黑呀。本人艾欧尼亚ID:godweiyang)黄金水平,虽然很菜,但是打字速度快!

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-02-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法码上来 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题解
  • 代码
    • c++
      • python
        • 后记
        相关产品与服务
        NLP 服务
        NLP 服务(Natural Language Process,NLP)深度整合了腾讯内部的 NLP 技术,提供多项智能文本处理和文本生成能力,包括词法分析、相似词召回、词相似度、句子相似度、文本润色、句子纠错、文本补全、句子生成等。满足各行业的文本智能需求。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档