動機

一個是直接幹，一個是mirror

Problem

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

    t
  • Every integer is in the inclusive range [0, 2n - 1],
    • t
  • The first integer is 0,
    • t
  • An integer appears no more than once in the sequence,
    • t
  • The binary representation of every pair of adjacent integers differs by exactly one bit, and
    • t
  • 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.

 

Example 1:

Input: n = 2Output: [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 = 1Output: [0,1]

 

Constraints:

    t
  • 1 <= n <= 16

Sol

直接幹

i是奇數就只改第一個位元 偶數就lowbit的右邊第一個位元

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ret = [0]
        lowbit = lambda n: n&~(n-1)
        for i in range((1 << n)-1):
            if i % 2 == 0:
                ret.append(ret[-1] ^ 1)
            else:
                ret.append(ret[-1] ^ (lowbit(ret[-1]) << 1))
        return ret

mirror

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 1:
            return [0,1]
        else:
            prev = self.grayCode(n-1)
            return prev+[x+(1 << (n-1)) for x in prev[::-1]]