二進位操作 格雷碼 Gray Code _Leetcode #89

這題的題目在這裡:Gray Code

題目敘述

題目會給我們一個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