主題

LeetCode - 89. Gray Code 解題心得

Not In My Back Yard | 2021-10-04 00:00:05 | 巴幣 12 | 人氣 65

題目連結:


題目意譯:
一個 n 位元格雷碼(Gray Code)序列為一序列有著 2 ^ n 個整數,其中:
每個在裡面的整數位於 [0, 2 ^ n - 1] 之範圍(含端點)中 、
第一個整數為 0 、
一個整數出現於序列中不超過一次、
每個相鄰整數對之二進位表達式恰好只差一個位元,且
第一個和最後一個整數的二進位表達式恰好只差一個位元。

給定一整數 n ,回傳任意的合法 n 位元格雷碼序列。

限制:
1 ≦ n ≦ 16



範例測資:
範例 1:
輸入: n = 2
輸出: [0,1,3,2]
解釋:
[0,1,3,2] 的二進位表達式為 [00,01,11,10]。
- 00 和 01 只差一個位元differ by one bit
- 01 和 11 只差一個位元
- 11 和 10 只差一個位元
- 10 和 00 只差一個位元
[0,2,3,1] 同樣也是一個合法的格雷碼序列,其二進位表達式為 [00,10,11,01]。
- 00 和 10 只差一個位元
- 10 和 11 只差一個位元
- 11 和 01 只差一個位元
- 01 和 00 只差一個位元

範例 2:
輸入: n = 1
輸出: [0,1]


解題思維:
雖然 n 位元的格雷碼序列可能很多種,但是有一種相當地經典(以下的數列本身全部以二進位表示):
可以看到 1 位元序列,顯而易見的為
0
1

而 2 位元可以從 1 位元推得,只要將上面的序列多重複一次,但該重複為上面的倒序:
0
1
1
0
然後將前半部開頭補 0 、後半部序列在開頭加上一個 1,即可得
00
01
11
10

而 3 位元也可以仿照 2 位元時的作法——倒序重複一次該序列,前半、後半的開頭依序補 0 和 1,即是
000
001
011
010
110
111
101
100
其他位元數以此類推。而這樣可行是因為每次後半部由前半部而來,所以理所當然地後半部自己內部相鄰數只差一位元。而前半部的結尾與後半部的開頭基本一樣,只差我們新加上去的開頭,所以也符合定義。



而有另一個生成法與上面的方式等價。以 3 位元序列為例:
我們開始於 000,然後我們開始第 1 次的操作。而:
每奇數次操作時,將最右邊的位元翻轉(即 0 變 1 、 1 變 0);
每偶數次操作時,從右邊開始看到第一個 1 ,將其左邊的位元翻轉。

因此一開始為
000,因為是第 1 次,1 為奇數,所以序列下一個數字為
001,因為是第 2 次,2 為偶數,所以序列下一個數字為
011,因為是第 3 次,3 為奇數,所以序列下一個數字為
010,因為是第 4 次,4 為偶數,所以序列下一個數字為
110……以此類推,直到我們執行 2 ^ n - 1 (在此 n = 3)次操作為止。

期間所產生的數字即是 n 位元格雷碼序列。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作