0089. Gray Code (Medium)

Question

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

1
2
3
4
5
6
7

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

1
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.

1
2
3
4

00 - 0
10 - 2
11 - 3
01 - 1

Example 2

1
2
3
4
5

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].

分析/解題

格雷碼是一個二進位表示的編碼系統，當中每個連續(相鄰)的二個值之間的表示方式只會相差一個位元(bit)。題目給定n個bits，試求出其表達的格雷碼序列。(格雷碼序列一定是從0開始)

在這邊簡單講解一下Bitwise Operation。
(註:本題雖然不會用到太多，
但熟悉這些操作對於一些題目和實際應用上很有幫助，
故在此先行列出給讀者學習。)

先前的文章中已經提到了，電腦對於二進位制的東西操作起來是較為得心應手的，當然我們可以不用像電腦這麼熟悉，但只要會用就可以了XD
二進位之間的一些操作運算，就像是邏輯學上的運算一樣，
有AND/OR/NOT/XOR，以及位移運算(bit shifts)等，這些速度在相同狀況下是由CPU進行支援的，運算速度往往會比一般的四則運算還快。

AND(且):
邏輯上的AND，代表著前後皆為真的狀況結果才為真，否則為假 ，
也就是兩者皆成立才行。在位元運算中，1被視為真，0被視為假。
(所以在如C/C++中你可能會看到使用IF 1或IF 0的開關)
延伸到多個bit的狀況，就是將前後兩者每個bit兩兩相對，
當兩者為1時，運算完的那個新的bit為1，否則為0。
如 110 AND 100的結果會是100(只有最左邊的bit是兩個1)
Java和Python中的AND運算符號均為"&" 。
(請留意，如果判斷兩個運算結果的是否為真 的邏輯運算，
Java是"&&"，Python則是"and" ，
以位元為基準的運算和求真偽的邏輯運算是不同的，記得不要搞混了！)

OR(或):
前後兩者只要其一為真結果即為真，
也就是只有兩者皆不成立時，結果才會是假 。
所以在位元運算中，
兩兩相對，除了兩個bit都是0的運算結果是0外，其餘都會是1 。
如 110 OR 100的結果會是110(只有最右邊的bit是兩個0)
Java和Python中的OR運算符號均為"|" 。
(如果是邏輯運算的話，Java是"||"，Python則是"or" )

NOT(非):
邏輯上的NOT，代表將該真/假狀況轉為原先的相反 ，
真的變假的，假的變真的 。
在位元運算中，對每個bit操作，
只要原先是1的均變為0，為先為0的則變為1 。
如NOT 110的結果會是001。
Java和Python中NOT運算符號均為"~" 。
(如果是邏輯運算的話，Java是"!"，Python則是"not" )

XOR(互斥或，Exclusive OR):
邏輯上的XOR，代表前後兩個狀況剛好有一個成立時為真 ，
即前真後假/前假後真，其餘皆為假。
位元運算的部分，兩兩相對檢查，當發現是一個1一個0的時候，
結果為1，否則均為0。
如1100 XOR 1010的結果會是0110。
Java和Python中的XOR運算符號均為"^" 。

位移運算:
將一個數的所有bit的東西往左或往右移動指定的位元數，
超出儲存空間的部分捨棄，被位移走的原處則補0。
Java和Python中使用"«“和”»“分別代表向左位移及向右位移。
例如:
 2 « 1 的結果會是4，因為2的二進位是"10”，
這個操作代表2向左位移1個bit，空白的部分補零，
所以會得到"100"也就是十進位制的4。

9 » 2的結果會是2，因為9的二進位是"1001"，
這個操作代表向右位移2個bit，所以"01"的部分移出儲存範圍了被捨棄掉，
會得到"10"，也就是十進位的2。

直觀上我們可以將位移N個bit視作乘以或除以2的N次方，
但要注意範圍是否正確，以及是否要處理正負號 的部分。

上面介紹了位元運算以後，讓我們回到題目。
在通訊傳輸的過程中，有可能因為受到雜訊干擾等狀況，
使得當中的位元反轉(0變成1，1變成0)。倘若我們按照正常的表達方式，
例如7=0111, 8=1000，對於某些臨界狀況而言，小範圍的變動值會需要大幅度的修改bit，同時當某個高位數的bit出錯的狀況，值就有可能受到大幅度的改變，這顯然是比較糟糕的。

所以格雷碼的設計就是希望能夠讓更動小數值的時候，只更動較少的bit數量即可，且當有其中的bit受到干擾而出錯時，數值的影響範圍也較小。

那怎麼計算呢？
我們從1個bit開始推導看看：
由於要求要從0開始，
故我們應該是拿0代表0，1代表1，這樣就完成了1個bit的格雷碼。
2個bit的話，由於用10來表示會一次更動2個bit(01->10)，
所以我們只能拿11來表示2，而10則表示3。

1
2
3
4

00 - 0
01 - 1
11 - 2
10 - 3

當然，也可以用00, 10, 11, 01來進行表示，但這種方式相對較複雜，
我們直接去考慮前面的方式的邏輯就好。

再來我們可以思考，在不要動到前面的數的狀況下，
下面我們要怎麼表達3個bit的狀況呢？
已經知道：

1
2
3
4

000 - 0
001 - 1
011 - 2
010 - 3

我們想要剛好用3個bit表示07，
那唯有讓47的部分的最左邊的bit均為1才行。
(因為前面的2個bit組合已經被用過了)
同時我們又想要符合相鄰只動一個bit 的原則，
所以4的表示方式就只剩下110了!

1
2
3
4
5
6
7
8

000 - 0
001 - 1
011 - 2
010 - 3
110 - 4
1xx - 5
1xx - 6
1xx - 7

同時，我們也知道前面03符合這個只動一個bit的表達方式，
那麼後面填入57的方式，就可以按照上下鏡向 的狀況填入，
自然會符合格雷碼的要求。也就是除了最左邊是1以外，
4對應到3，5就對應到2，6對應到1，7對應到0即可。

1
2
3
4
5
6
7
8

000 - 0
001 - 1
011 - 2
010 - 3
110 - 4
111 - 5
101 - 6
100 - 7

同樣的道理，變成4個bit時，將後面的8個數的最左邊的bit填入1，
其它的部分鏡向填入即可。

歸納一下這題的解法：

1. 先放入0(最開始的部分，也是n=0時的解答)
2. 定義一個變數adder，用來表示這輪要加上去的bit所代表的值
   (初始值是2的0次方=1)
3. 每次將答案的尾端加上一個新的值，
   這個新的值是鏡向對應到的值加上adder。
   (鏡向對應的方式，可以從尾端開始往回算，或者用adder-1-index來計算)
4. 計算完畢一輪以後，將adder變為2倍，作為下一輪要額外加上去的值。
5. 一路操作直到完成n輪為止，最後將結果回傳。

Java

Python

讀者可以看到兩個解法中一個使用+adder，另一個使用|add，
結果上是一樣的，因為加上去的那個bit一定是跟0相加，
故可以用OR運算會加快一點速度。(讀者可以修改成+來比較看看速度)
*2和«=1的部分，同樣可以等價於位移一個bit，
但速度上應該不會有特別差異才對。

面試實際可能會遇到的問題

「時間複雜度？」
(O(2的n次方)，因為n個bit可以表示2的n次方個數)

「(Python)能不能不要用append來解？」
(可以用extend，
每次將res的部分反轉接上後，再進行add的加總)

「為什麼你要用"_"？」
(因為第一個迴圈事實上只是處理執行n次這件事情，
我們並不需要用到其數值，在習慣上會盡量用底線來命名，
避免去用到有意義的命名方式。)

從LeetCode學演算法，我們下次見囉，掰~