Условие задачи (простыми словами)
🎯 Что такое код Грея?
Представьте, что у вас есть переключатели (как в старом лифте: этажи 1, 2, 3...). Каждый переключатель может быть:
- 🔴 Выключен = 0
- 🟢 Включен = 1
Если у вас 2 переключателя, то возможные комбинации:
00 → 0
01 → 1
10 → 2
11 → 3
Главное правило кода Грея:
При перехоре от одного числа к следующему должен меняться только ОДИН переключатель!
✅ Правильно: 00 → 01 → 11 → 10
↑ ↑ ↑
один бит один бит один бит
❌ Неправильно: 00 → 11
↑↑
изменились ДВА бита сразу!
Ваша задача:
Дано число n — количество бит (переключателей).
Верните любую последовательность из 2ⁿ чисел, где:
- Последовательность начинается с 0
- Каждое следующее число отличается от предыдущего ровно одним битом
- Все числа от 0 до 2ⁿ - 1 встречаются ровно один раз
Примеры "на пальцах"
Пример 1: n = 2 (2 бита → 4 числа)
Один из возможных ответов: [0, 1, 3, 2]
В двоичной системе:
0 → 00
1 → 01 (изменился правый бит: 0→1) ✅
3 → 11 (изменился левый бит: 0→1) ✅
2 → 10 (изменился правый бит: 1→0) ✅
Визуализация:
00 → 01 → 11 → 10
↑ ↑ ↑ ↑
Старт 1бит 1бит 1бит
Пример 2: n = 1 (1 бит → 2 числа)
Ответ: [0, 1]
0 → 0
1 → 1 (изменился единственный бит) ✅
Как придумать решение? Три способа!
🔹 Способ 1: "Зеркальный мир" (интуитивный)
Представьте, что вы строите код Грея как конструктор:
Шаг 0 (n=0): [0]
Шаг 1 (n=1):
• Берём [0]
• Добавляем 0 спереди: [00]
• Зеркалим и добавляем 1 спереди: [00, 01]
• Результат: [0, 1]
Шаг 2 (n=2):
• Берём [0, 1] → [00, 01]
• Зеркалим: [01, 00] → добавляем 1 спереди: [11, 10]
• Склеиваем: [00, 01, 11, 10] → [0, 1, 3, 2] ✅
Шаг 3 (n=3):
• [000, 001, 011, 010] + зеркало с единицей [110, 111, 101, 100]
• Результат: [0,1,3,2,6,7,5,4]
Код (рекурсивный):
Способ 2: "Магическая формула" (самый крутой! 🚀)
Оказывается, есть простая формула, которая превращает обычное число в код Грея:
gray(i) = i XOR (i >> 1)
Где:
• XOR (^) — исключающее ИЛИ (0^0=0, 1^1=0, 0^1=1)
• >> 1 — сдвиг вправо на 1 бит (деление на 2)
Почему это работает? (объясняю как школьнику)
Представьте число в двоичной системе:
i = 6 → 110
Сдвигаем вправо: 110 >> 1 = 011
Применяем XOR: 110 ^ 011 = 101 → 5
Проверяем: 6 (110) и 5 (101) отличаются ровно одним битом! ✅
Код решения (одна строка!):
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/tree/main/src/main/java/info/shkryl/task89_grayCcode