Сложность: medium
Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.
Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.
Пример:
Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]
Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1); // hit at timestamp 1.
hitCounter.hit(2); // hit at timestamp 2.
hitCounter.hit(3); // hit at timestamp 3.
hitCounter.getHits(4); // get hits at timestamp 4, return 3.
hitCounter.hit(300); // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.
👨💻 Алгоритм:
1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.
2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.
3⃣Верните размер очереди как количество попаданий за последние 5 минут.
😎 Решение:
from collections import deque
class HitCounter:
def __init__(self):
self.hits = deque()
def hit(self, timestamp: int) -> None:
self.hits.append(timestamp)
def getHits(self, timestamp: int) -> int:
while self.hits and timestamp - self.hits[0] >= 300:
self.hits.popleft()
return len(self.hits)
Ставь 👍 и забирай 📚 Базу знаний