89. Gray Code

Problem

An n-bit gray code sequence is a sequence of 2ⁿ integers where:

• Every integer is in the inclusive range [0, 2ⁿ - 1],
• The first integer is 0,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

https://leetcode.com/problems/gray-code/

Example 1:

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

Example 2:

Input: n = 1
Output: [0,1]

Constraints:

• 1 <= n <= 16

Test Cases

1
2

class Solution:
    def grayCode(self, n: int) -> List[int]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import pytest

from solution import Solution


# 191-number-of-1-bits#Another-Way
def hamming_weight(n: int) -> int:
    cnt = 0
    while n > 0:
        cnt += 1
        n &= n - 1

    return cnt


def validate_gray_code(nums: list[int]) -> None:
    n = len(nums)
    assert sorted(nums) == list(range(n))
    assert nums[0] == 0
    for i in range(len(nums)):
        assert hamming_weight(nums[i-1] ^ nums[i]) == 1


@pytest.mark.parametrize('n, expected', [
    (2, [0,1,3,2]),
    (1, [0,1]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, n, expected):
    result = sol.grayCode(n)
    if result != expected:
        assert len(result) == 2 ** n
        validate_gray_code(result)

Thoughts

格雷编码序列，两个连续的数值仅有一个（二进制）位数的差异。

如果已经得到了 n - 1 的格雷编码序列 [g₁, g₂, ..., gₘ]（m = 2ⁿ⁻¹），其中每个数字的第 n 个二进制位都一定是 0。可以把每个数字的第 n 个二进制位都置为 1，得到新的序列 [g'₁, g'₂, ..., g'ₘ]，显然新序列中任意两个连续的数值都仅有一个位数的差异。把第二个序列逆序拼接到第一序列后边，得到 [g₁, g₂, ..., gₘ, g'ₘ, g'ₘ₋₁, ..., g'₂, g'₁]，这就是 n 的格雷编码序列。

初始时 n = 0 的格雷编码序列就是 [0]。

Code

1
2
3
4
5
6
7

class Solution:
    def grayCode(self, n: int) -> list[int]:
        result = [0]
        for i in range(n):
            diff = 1 << i
            result.extend(x + diff for x in reversed(result))
        return result

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章