0089. Gray Code - chasel2361/leetcode GitHub Wiki

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code.
A gray code sequence must begin with 0.

Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2
For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.
00 - 0
10 - 2
11 - 3
01 - 1

Example 2:
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [0].

這個問題雨蕭大大利用 bitwise operation 來解，這邊先稍微整理一下。

在 bitwise operation 中， 1 被視為真， 0 被視為假，因此出現了下列的邏輯計算：

• AND ( & )：前後皆為真才回傳真
  110 & 100 → 100
  111001 & 100111 → 100001

• OR ( | )：前後其一為真就回傳真
  110 & 100 → 110
  111001 & 100111 → 111111

• NOT ( ~ )：反轉真假
  ~ 110 → 001
  ~ 111001 → 000110

• XOR ( ^ )：前後僅一者為真才回傳真
  110 ^ 100 → 010
  111001 ^ 100111 → 011110

• 位移：將指定值往左或右移一個位元，若超出儲存空間則捨棄，原處補零
  110 >> 2 → 11000
  110 << 2 → 1

這題的目標是要改變最少數字來排列出指定位數的二進位數字，所以會使用到 bitwise operation。觀察上面的範例後可以發現，同樣位數的數字中，前半部分與後半部分不看最高次項的話是對稱排列，而最高次項前半為 0 ，後半為 1 ，所以可以寫成這樣。

[1] 初始值為 0
[2] add 表示最高次方項，要拿來與前半部分做邏輯運算
[3] add - 1 - i 是新值與前半部分的鏡像對應值
[4] 當最高次方項完成操作後，增加最高次方項

class Solution:
    def grayCode(self, n:int) -> List[int]:
        res = [0]  # [1]
        add = 1  # [2]
        for _ in range(n):
            for i in range(add):
                res.append(res[add - 1 - i] | add)  # [3]
            add <<= 1  # [4]
        return res

看了一下發現還有更快的作法，直接拿 i 跟 i 右移一位的結果作 XOR 丟進 res 裡，這關係到底怎麼想到的啊XDDD

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res = []
        for i in range(2**n):
            res.append(i ^ (i >> 1))
        return res

這兩個做法的時間複雜度都是 O(2^N)