Задача: 89. Gray Code
Сложность: medium

Последовательность Грея с n-битами — это последовательность из 2^n целых чисел, где:

1. Каждое число находится в включающем диапазоне от 0 до 2^n - 1,
2. Первое число равно 0,
3. Каждое число встречается в последовательности не более одного раза,
4. Двоичное представление каждой пары соседних чисел отличается ровно на один бит,
5. Двоичное представление первого и последнего чисел отличается ровно на один бит.

Для заданного числа n возвращается любая допустимая последовательность Грея с n-битами.

Пример:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

👨‍💻 Алгоритм:

1⃣Инициализируйте список результатов для хранения последовательности решений. Добавьте 0 в список перед вызовом вспомогательного метода, так как все последовательности Грея начинаются с 0.

2⃣Инициализируйте множество visited. Это позволяет отслеживать числа, присутствующие в текущей последовательности, чтобы избежать повторения.
Начните с числа 0.
В функции grayCodeHelper() используйте цикл for, чтобы найти каждое возможное число (next), которое может быть сгенерировано путем изменения одного бита последнего числа в списке результатов (current). Делайте это, переключая i-ый бит на каждой итерации. Поскольку максимально возможное количество битов в любом числе последовательности равно n, необходимо переключить n битов.

3⃣Если next не присутствует в множестве использованных чисел (isPresent), добавьте его в список результатов и множество isPresent.
Продолжайте поиск с next.
Если grayCodeHelper(next) возвращает true, это означает, что допустимая последовательность найдена. Дальнейший поиск не требуется (ранняя остановка). Это раннее завершение улучшает время выполнения.
Если с next не найдена допустимая последовательность, удаляем его из списка результатов и множества isPresent и продолжаем поиск.
При достижении базового условия, когда длина текущей последовательности равна 2^n, возвращаем true.
Выход из цикла for означает, что с current в качестве последнего числа не найдена допустимая последовательность кода Грея. Поэтому возвращаем false.

😎 Решение:

class Solution {
    public function grayCode($n) {
        $result = [0];
        $isPresent = [0 => true];
        $this->grayCodeHelper($result, $n, $isPresent);
        return $result;
    }

    private function grayCodeHelper(&$result, $n, &$isPresent) {
        if (count($result) === (1 << $n)) {
            return true;
        }
        $current = $result[count($result) - 1];
        for ($i = 0; $i < $n; $i++) {
            $nextNum = $current ^ (1 << $i);
            if (!isset($isPresent[$nextNum])) {
                $isPresent[$nextNum] = true;
                array_push($result, $nextNum);
                if ($this->grayCodeHelper($result, $n, $isPresent)) {
                    return true;
                }
                unset($isPresent[$nextNum]);
                array_pop($result);
            }
        }
        return false;
    }
}

$solution = new Solution();
$n = 2; 
$result = $solution->grayCode($n);
print_r($result);

Ставь 👍 и забирай 📚 Базу знаний