Сложность: 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 минут.
😎 Решение:
class HitCounter {
private var hits: [Int]
init() {
self.hits = [Int]()
}
func hit(_ timestamp: Int) {
self.hits.append(timestamp)
}
func getHits(_ timestamp: Int) -> Int {
while let first = self.hits.first, timestamp - first >= 300 {
self.hits.removeFirst()
}
return self.hits.count
}
}Ставь 👍 и забирай 📚 Базу знаний