前往
大廳
主題

LeetCode - 495. Teemo Attacking 解題心得

Not In My Back Yard | 2021-08-14 00:00:03 | 巴幣 0 | 人氣 242

題目連結:


題目意譯:
我們的英雄提摩正在用毒攻擊敵人艾希!當提摩攻擊艾希,艾希將中毒恰好 duration 秒。更正式地說,一個 t 秒的攻擊將代表著艾希會在時間區間 [t, t + duration - 1] 之中維持著中毒。如果提摩在毒的效果結束前再次攻擊,則計時器將會重設,而毒的效果將結束於新的攻擊的 duration 秒後。

你被給定一個非遞減整數陣列 timeSeries ,其中 timeSeries[i] 代表提摩於第 timeSeries[i] 時攻擊了艾希,以及給定一個整數 duration。

回傳艾希中毒的總秒數。

限制:
1 ≦ timeSeries.length ≦ 10 ^ 4
0 ≦ timeSeries[i] 、 duration ≦ 10 ^ 7
timeSeries 以非遞減的順序排序。



範例測資:
範例 1:
輸入: timeSeries = [1,4], duration = 2
輸出: 4
解釋: 提摩對於艾希之攻擊如下:
- 在第 1 秒,提摩攻擊,而艾希將中毒於第 1 秒和第 2 秒。
- 在第 4 秒,提摩攻擊,而艾希將中毒於第 4 秒和第 5 秒。
艾希中毒於第 1 、 2 、 4 、 5 秒,因此總共 4 秒。

範例 2:
輸入: timeSeries = [1,2], duration = 2
輸出: 3
解釋: 提摩對於艾希之攻擊如下:
- 在第 1 秒,提摩攻擊,而艾希將中毒於第 1 秒和第 2 秒。
- 不過在第 2 秒,提摩再次攻擊並重設了中毒計時器。而艾希將中毒於第 2 秒和第 3 秒。
艾希中毒於第 1 、 2 、 3 秒,因此總共 3 秒。


解題思維:
單純地模擬出提摩每次攻擊所造成的中毒區間。利用兩個變數 B 、 E,用來儲存中毒時間區間的開頭以及結尾時間點。

對於每次第 t 秒的攻擊,先看前一次的結尾 E(如果有前一次攻擊的話)是否 ≦ t。

如果是就代表著,此次攻擊與先前的攻擊獨立,因此將會有新的中毒區間 [t, t + duration - 1],而先前攻擊的將貢獻 E - B + 1 秒的中毒時間。接著將 B 設為 t 、 E 設為 t + duration - 1 。

反之,就代表本次的攻擊將會重設先前的時間計數器,因此我們需要更新中毒區間的結尾 E 為 t + duration - 1 (注意區間開頭時間點 B 的值沒有更動)。

最後上述過程中的中毒總秒數 + (最後的 E 值 - 最後的 B 值 + 1)(因為光是上面的過程,最後一次攻擊將不會被納入秒數中)即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作