回溯 格雷碼

題目

格雷編碼是一個(gè)二進(jìn)制數(shù)字系統(tǒng)，在該系統(tǒng)中，兩個(gè)連續(xù)的數(shù)值僅有一個(gè)位數(shù)的差異。

給定一個(gè)代表編碼總位數(shù)的非負(fù)整數(shù) n，打印其格雷編碼序列。即使有多個(gè)不同答案，你也只需要返回其中一種。

格雷編碼序列必須以 0 開(kāi)頭。

示例 1:

輸入: 2
輸出: [0,1,3,2]
解釋:


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

對(duì)于給定的 n，其格雷編碼序列并不唯一。 例如，[0,2,3,1] 也是一個(gè)有效的格雷編碼序列。

示例 2:

輸入: 0
輸出: [0]

解釋: 我們定義格雷編碼序列必須以 0 開(kāi)頭。 給定編碼總位數(shù)為 n 的格雷編碼序列，其長(zhǎng)度為 2n。當(dāng) n = 0 時(shí)，長(zhǎng)度為 20 = 1。 因此，當(dāng) n = 0 時(shí)，其格雷編碼序列為 [0]。

解題

1.二進(jìn)制碼→格雷碼（編碼）：

此方法從對(duì)應(yīng)的n位二進(jìn)制碼字中直接得到n位格雷碼碼字，步驟如下： 對(duì)n位二進(jìn)制的碼字，從右到左，以0到n-1編號(hào) 如果二進(jìn)制碼字的第i位和i+1位相同，則對(duì)應(yīng)的格雷碼的第i位為0，否則為1（當(dāng)i+1=n時(shí)，二進(jìn)制碼字的第n位被認(rèn)為是0，即第n-1位不變）

2.格雷碼→二進(jìn)制碼（解碼）：

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

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>() {{ add(0); }};
        int head = 1;
        for (int i = 0; i < n; i++) {
            for (int j = res.size() - 1; j >= 0; j--)
                res.add(head + res.get(j));
            head <<= 1;
        }
        return res;
    }
}

方法解析

1.head <<= 1; x<<=1等于x=x<<1，是把x左移1位以后值保存回x里，x發(fā)生變化了。