格雷編碼的定義

格雷編碼我們在大學(xué)時期已經(jīng)了解過了，在一組數(shù)的編碼中，若任意兩個相鄰的代碼只有一位二進(jìn)制數(shù)不同，則稱這種編碼為格雷碼（Gray Code），另外由于最大數(shù)與最小數(shù)之間也僅一位數(shù)不同，即“首尾相連”，因此又稱循環(huán)碼或反射碼。 [2] 在數(shù)字系統(tǒng)中，常要求代碼按一定順序變化。例如，按自然數(shù)遞增計數(shù)，若采用8421碼，則數(shù)0111變到1000時四位均要變化，而在實(shí)際電路中，4位的變化不可能絕對同時發(fā)生，則計數(shù)中可能出現(xiàn)短暫的其它代碼（1100、1111等）。在特定情況下可能導(dǎo)致電路狀態(tài)錯誤或輸入錯誤。使用格雷碼可以避免這種錯誤。格雷碼有多種編碼形式。
格雷碼（Gray code）曾用過Grey Code、葛萊碼、葛蘭碼、格萊碼、戈萊碼、循環(huán)碼、二進(jìn)制反射碼、最小差錯碼等名字，它們有的是錯誤的，有的易與其它名稱混淆，建議不再使用它們。

格雷編碼的碼表

自然數(shù)	自然數(shù)的二進(jìn)制	一位格雷碼	二位格雷碼	三位格雷碼	四位格雷碼
0	0000	0	00	000	0000
1	0001	1	01	001	0001
2	0010		11	011	0011
3	0011		10	010	0010
4	0100			110	0110
5	0101			111	0111
6	0110			101	0101
7	0111			100	0100
8	1000				1100
9	1001				1101
10	1010				1111
11	1011				1110
12	1100				1010
13	1101				1011
14	1110				1001
15	1111				1000

LeetCode 89. 格雷編碼

LeetCode 89. 格雷編碼
n 位格雷碼序列 是一個由 2n 個整數(shù)組成的序列，其中：
每個整數(shù)都在范圍 [0, 2n - 1] 內(nèi)（含 0 和 2n - 1）
第一個整數(shù)是 0
一個整數(shù)在序列中出現(xiàn) 不超過一次
每對 相鄰 整數(shù)的二進(jìn)制表示 恰好一位不同 ，且
第一個 和 最后一個 整數(shù)的二進(jìn)制表示 恰好一位不同
給你一個整數(shù) n ，返回任一有效的 n 位格雷碼序列 。

實(shí)例

輸入：n = 2
輸出：[0,1,3,2]
解釋：
[0,1,3,2] 的二進(jìn)制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一個有效的格雷碼序列，其二進(jìn)制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

思路與代碼

思路一：找規(guī)律

觀察格雷碼的規(guī)律，具有一定的對稱性，高位是 1 或者 0，并由此就行對稱

代碼一

//耗時 6ms
class Solution {public List<Integer> grayCode(int n) {int count = 1;List<Integer> res = new ArrayList<>();res.add(0);res.add(1);while (n-- > 1) {count <<= 1;for (int i = count - 1; i >= 0; i--) {res.add(res.get(i) + count);}}return res;}
}

因為res.get(i)是循環(huán)方式去取值，當(dāng)n的位數(shù)確定后格雷數(shù)就已經(jīng)知道多少了，故可以這樣寫

代碼二

class Solution {public List<Integer> grayCode(int n) {Integer[] res = new Integer[1 << n];res[0] = 0;res[1] = 1;int count = 1;while (n-- > 1) {count <<= 1;for (int i = 0; i < count; i++) {res[i + count] = count + res[count - i - 1];}}return Arrays.asList(res);}
}

思路二：與自然數(shù)之間的關(guān)系（你必須知道，這個規(guī)律要去百度才知道）

格雷碼→二進(jìn)制碼（解碼）：
從左邊第二位起，將每位與左邊一位解碼后的值異或，作為該位解碼后的值（最左邊一位依然不變）。依次異或，直到最低位。依次異或轉(zhuǎn)換后的值（二進(jìn)制數(shù)）就是格雷碼轉(zhuǎn)換后二進(jìn)制碼的值。

代碼一

class Solution {public List<Integer> grayCode(int n) {List<Integer> res = new ArrayList<>();int sum = 1<<n;for(int i = 0;i < sum;i++){res.add((i >> 1) ^ i);}return res;}
}

LeetCode 1238. 循環(huán)碼排列

LeetCode 1238. 循環(huán)碼排列
給你兩個整數(shù) n 和 start。你的任務(wù)是返回任意 (0,1,2,…,2^n-1) 的排列 p，并且滿足：
p[0] = start
p[i] 和 p[i+1] 的二進(jìn)制表示形式只有一位不同
p[0] 和 p[2^n -1] 的二進(jìn)制表示形式也只有一位不同
實(shí)例：

實(shí)例

輸入：n = 2, start = 3
輸出：[3,2,0,1]
解釋：這個排列的二進(jìn)制表示是 (11,10,00,01)所有的相鄰元素都有一位是不同的，另一個有效的排列是 [3,1,0,2]

思路與代碼

題目與上面的是一樣的，所有解決方法也是兩種

思路一：找規(guī)律

觀察格雷碼的規(guī)律，具有一定的對稱性，高位是 1 或者 0，并由此就行對稱

代碼一

class Solution {public List<Integer> circularPermutation(int n, int start) {List<Integer> ans = new ArrayList<>();Integer[] res = new Integer[1 << n];res[0] = 0;res[1] = 1;int count = 1;int index = start; // 找到位置， 存在start 為 0，1的問題，故直接賦值過去while (n-- > 1) {count <<= 1;for (int i = 0; i < count; i++) {res[i + count] = count + res[count - i - 1];if (res[i + count] == start) {index = i + count;}}}for (int i = 0; i < res.length; i++) {ans.add(res[(index + i) % res.length]);}return ans;}
}

思路二：與自然數(shù)之間的關(guān)系

要通過觀察，格雷數(shù)的 ^ 關(guān)系，格雷是從0開始的，0^任意數(shù)都是本身，然后格雷數(shù)每個與前一個變化相差為一，故一直第一個數(shù) ^ 結(jié)果就是你想要的

代碼一：

class Solution {public List<Integer> circularPermutation(int n, int start) {List<Integer> res = new ArrayList<>();int sum = 1<<n;for(int i = 0;i < sum;i++){res.add((i >> 1) ^ i ^ start);}return res;}
}