Сложность: medium
Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.
Пример:
Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2
👨💻 Алгоритм:
1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.
2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.
3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.
😎 Решение:
class Solution {
func flipLights(_ n: Int, _ m: Int) -> Int {
var seen = Set<Int>()
let n = min(n, 6)
let shift = max(0, 6 - n)
for cand in 0..<16 {
let bcount = cand.nonzeroBitCount
if bcount % 2 == m % 2 && bcount <= m {
var lights = 0
if ((cand >> 0) & 1) > 0 { lights ^= 0b111111 >> shift }
if ((cand >> 1) & 1) > 0 { lights ^= 0b010101 >> shift }
if ((cand >> 2) & 1) > 0 { lights ^= 0b101010 >> shift }
if ((cand >> 3) & 1) > 0 { lights ^= 0b100100 >> shift }
seen.insert(lights)
}
}
return seen.count
}
}Ставь 👍 и забирай 📚 Базу знаний