495. 提莫攻击 : 简单模拟题

简介: 495. 提莫攻击 : 简单模拟题

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 495. 提莫攻击 ,难度为 简单


Tag : 「模拟」


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


当提莫攻击艾希,艾希的中毒状态正好持续 duration 秒。


正式地讲,提莫在 t 发起发起攻击意味着艾希在时间区间 [t, t + duration - 1](含 tt + duration - 1)处于中毒状态。如果提莫在中毒影响结束 前 再次攻击,中毒状态计时器将会 重置 ,在新的攻击之后,中毒影响将会在 duration 秒后结束。


给你一个 非递减 的整数数组 timeSeries,其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击,以及一个表示中毒持续时间的整数 duration


返回艾希处于中毒状态的 秒数。


示例 1:


输入:timeSeries = [1,4], duration = 2
输出:4
解释:提莫攻击对艾希的影响如下:
- 第 1 秒,提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒,即第 1 秒和第 2 秒。
- 第 4 秒,提莫再次攻击艾希,艾希中毒状态又持续 2 秒,即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态,所以总中毒秒数是 4 。
复制代码


示例 2:


输入:timeSeries = [1,2], duration = 2
输出:3
解释:提莫攻击对艾希的影响如下:
- 第 1 秒,提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒,即第 1 秒和第 2 秒。
- 第 2 秒,提莫再次攻击艾希,并重置中毒计时器,艾希中毒状态需要持续 2 秒,即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态,所以总中毒秒数是 3 。
复制代码


提示:


  • 1 <= timeSeries.length <= 10^41<=timeSeries.length<=104
  • 0 <= timeSeries[i], duration <= 10^70<=timeSeries[i],duration<=107
  • timeSeries 按 非递减 顺序排列


模拟



题目已确保 timeSeriestimeSeries 为非递减排序,按照顺序进行遍历处理即可。


我们使用 ansans 统计答案,使用 lastlast 记录上一次攻击的结束点,对于任意的 timeSeries[i]timeSeries[i] 而言,假设其发起点为 s = timeSeries[i]s=timeSeries[i],结束点为 e = s + duration - 1e=s+duration1,针对 lastlastss 进行分情况讨论即

可:


  • last < slast<s :两次攻击不重合,则有 ans += duration; last = e;ans+=duration;last=e;
  • last >= slast>=s :两次攻击重合,则有 ans += e - last; last = eans+=elast;last=e


注意:lastlast 作为上次的结束点,在处理 timeSeries[i]timeSeries[i] 时,lastlast 是一个「已被统计」的存在,因此我们需要将其初始化为 -11(使用一个比 00 小的数值作为哨兵),以确保当 timeSeries[0] = 0timeSeries[0]=0 时,第 00 秒能够被计数。


代码:


class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ans = 0, last = -1;
        for (int s : timeSeries) {
            int e = s + duration - 1;
            ans += last < s ? duration : e - last;
            last = e;
        }
        return ans;
    }
}
复制代码


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


最后



这是我们「刷穿 LeetCode」系列文章的第 No.495 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
存储 自然语言处理 Oracle
打造全球化企业:ERP系统的国际化与多语言支持
打造全球化企业:ERP系统的国际化与多语言支持
841 2
|
SQL 监控 关系型数据库
【MYSQL高级】Mysql找出执行慢的SQL【慢查询日志使用与分析】
【MYSQL高级】Mysql找出执行慢的SQL【慢查询日志使用与分析】
4730 0
|
存储 Linux 开发工具
成功解决centos7安装docker时 报缺 少container-selinux和fuse-overlayfs包
成功解决centos7安装docker时 报缺 少container-selinux和fuse-overlayfs包
5628 1
成功解决centos7安装docker时 报缺 少container-selinux和fuse-overlayfs包
|
10月前
|
数据采集 人工智能 DataWorks
DataWorks产品最佳实践测评
DataWorks产品最佳实践测评
|
10月前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
639 15
|
11月前
|
人工智能 运维 关系型数据库
云栖大会|数据库与AI全面融合,迈入数据智能新纪元
2024年云栖大会「数据库与AI融合」专场,来自NVIDIA、宇视科技、合思信息、杭州光云科技、MiniMax等企业的代表与阿里云瑶池数据库团队,共同分享了Data+AI全面融合的最新技术进展。阿里云发布了DMS的跨云统一开放元数据OneMeta和智能开发OneOps,推出《云数据库运维》技术图书,并介绍了PolarDB、AnalyticDB、Lindorm和Tair等产品的最新能力,展示了AI在数据库领域的广泛应用和创新。
926 15
|
关系型数据库 MySQL 网络安全
如何在 VPS 上安装和使用 VirtualMin
如何在 VPS 上安装和使用 VirtualMin
212 0
|
存储 搜索推荐 大数据
大数据在医疗领域的应用
大数据在医疗领域有广泛应用,包括电子病历的数字化管理和共享,提升医疗服务效率与协同性;通过数据分析支持医疗决策,制定个性化治疗方案;预测疾病风险并提供预防措施;在精准医疗中深度分析患者基因组信息,实现高效治疗;在药物研发中,加速疗效和副作用发现,提高临床试验效率。此外,在金融领域,大数据的“4V”特性助力业务决策前瞻性,被广泛应用于银行、证券和保险的风险评估、市场分析及个性化服务中,提升运营效率和客户满意度。
1323 6
|
12月前
|
机器学习/深度学习 弹性计算 人工智能
大模型进阶微调篇(三):微调GPT2大模型实战
本文详细介绍了如何在普通个人电脑上微调GPT2大模型,包括环境配置、代码实现和技术要点。通过合理设置训练参数和优化代码,即使在无独显的设备上也能完成微调,耗时约14小时。文章还涵盖了GPT-2的简介、数据集处理、自定义进度条回调等内容,适合初学者参考。
2167 6
|
安全 关系型数据库 MySQL
深入解析MySQL 8中的角色与用户管理
深入解析MySQL 8中的角色与用户管理
730 3