LeetCode刷題題解：495. 提莫攻擊

buildupchao 發布于2021-11-11 16:55 / 3494人閱讀

摘要：正式地講，提莫在發起發起攻擊意味著艾希在時間區間含和處于中毒狀態。示例輸入輸出解釋提莫攻擊對艾希的影響如下第秒，提莫攻擊艾希并使其立即中毒。第秒，提莫再次攻擊艾希，艾希中毒狀態又持續秒，即第秒和第秒。

495. 提莫攻擊

題目：

? ? ??? 在《英雄聯盟》的世界中，有一個叫 “提莫” 的英雄。他的攻擊可以讓敵方英雄艾希（編者注：寒冰射手）進入中毒狀態。當提莫攻擊艾希，艾希的中毒狀態正好持續 duration 秒。

? ? ??? 正式地講，提莫在 t 發起發起攻擊意味著艾希在時間區間 [t, t + duration - 1]（含 t 和 t + 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 。

解題思路：

這道題為簡單題，只需遍歷數組計算相鄰元素間的差值和持續時間的最小值，然后累加求和，也就是統計除了最后一個中毒持續時間的前面的中毒持續時間和，因為最后的中毒持續時間是一定的，所以將求和結果加上duration返回即可。

代碼：

class Solution {    public int findPoisonedDuration(int[] timeSeries, int duration) {    	int t = 0;        int total = 0;        for (int i = 1; i < timeSeries.length; i++) {            t = Math.min(timeSeries[i]-timeSeries[i-1], duration);            total += t;        }        return total+duration;    }}

復雜度分析：

時間復雜度：O(n)，循環遍歷數組，記數組的長度為n，故時間復雜度為O(n)。
空間復雜度：O(1)，有限兩個變量分別記錄前n-1個時段的持續時間和累加和，故空間復雜度為O(1)。

WAF 高防服務器題解 oj題解 LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/123045.html

leetcode每日一題-495:提莫攻擊

摘要：每日一題提莫攻擊鏈接提莫攻擊題目分析從第二位開始枚舉每次判斷和前一次的間隔是多少然后判斷出中毒的描述遍歷結束后因為最后一次施加的中毒狀態一定可以持續完整的中毒事件所以最后再加上代碼作者 ...

kevin 2021-11-11 16:55 評論0 收藏0
【快樂水題】495. 提莫攻擊

摘要：當提莫攻擊艾希，艾希的中毒狀態正好持續秒。正式地講，提莫在發起發起攻擊意味著艾希在時間區間含和處于中毒狀態。如果提莫在中毒影響結束前再次攻擊，中毒狀態計時器將會重置，在新的攻擊之后，中毒影響將會在秒后結束。 ...

k00baa 2021-11-12 10:36 評論0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數組知識點。或者拉到本文最下面，添加的微信等會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 評論0 收藏0
JavaSE與數據結構基礎知識系列——專欄導航

??前面的話?? 大家好！這是Java基礎知識與數據結構博文的導航帖，收藏我！學習Java不迷路！ ?博客主頁：未見花聞的博客主頁 ?歡迎關注?點贊?收藏??留言? ?本文由未見花聞原創，CSDN首發！ ?首發時間：?2021年11月11日? ??堅持和努力一定能換來詩與遠方！ ?參考書籍：?《Java核心技術卷1》，?《Java核心技術卷2》，?《Java編程思想》 ?參考在線編程網站：?牛...

Cc_2011 2021-11-12 10:36 評論0 收藏0