二進位操作 格雷碼 Gray Code
_Leetcode #89
題目敘述
題目會給我們一個bit寬度n，要求我們造出所有格雷編碼。
格雷編碼就是一組二進位編碼，每兩個相鄰的編碼的hamming distance都是1。
如果第一次接觸的讀者，可以參考 Wiki 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
演算法
用原本gray code 遮罩演算即可，gray碼的精神是和前一個編碼的hamming distance都是1。
這邊用寬度為3的gray code生成，作示範。
寬度為三的gray code，總共會有2^3 = 8個編碼
格雷碼遮罩 i // 2 等價於 i >> 1 等價於 i右移一個bit
i=0
0的binary form是0，右移一個bit還是0
0 XOR 0 = 0 = 十進制的0
i=1
1的binary form是1，右移一個bit是0 (作為格雷碼遮罩)
1 XOR 0 = 1 = 十進制的1
i=2
2的binary form是10，右移一個bit是1 (作為格雷碼遮罩)
10 XOR 01 = 11 = 十進制的3
i=3
3的binary form是11，右移一個bit是1 (作為格雷碼遮罩)
11 XOR 01 = 10 = 十進制的2
...中間依此類推
i=7
7的binary form是111，右移一個bit是11 (作為格雷碼遮罩)
111 XOR 011 = 100 = 十進制的4
最侯，全部蒐集到的格雷編碼，等價的十進制數字就是[0,1,3,2,6,7,5,4]
程式碼
class Solution:
def grayCode(self, n: int) -> List[int]:
# total 2^n codes for bit length n
code_count = 1 << n
# generate gray code from 0, and toggle 1 bit on each iteration
# toggle mask: ( i >> 1 )
gray_codes =[ i ^ ( i >> 1 ) for i in range(code_count) ]
return gray_codes
複雜度分析
時間複雜度: O(2^n)
一次線性掃描，格雷編碼的總數目有2^n個。
空間複雜度: O(2^n)
過程中，會使用到暫存的buffer array: gray_codes，長度為O(2^n)
關鍵知識點
除了字串的鏡像黏貼法，也可以使用gray code原生的遮罩產生法。
格雷碼遮罩 i // 2 等價於 i >> 1 等價於 i右移一個bit
Reference:
[1] Python/JS/C++/Go O(2^n) by toggle bitmask [w/ Example] - Gray Code - LeetCode
