回溯 格雷碼

題目

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

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

格雷編碼序列必須以 0 開頭。

示例 1:

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


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

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

示例 2:

輸入: 0
輸出: [0]

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

解題

1.二進制碼→格雷碼（編碼）：

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

2.格雷碼→二進制碼（解碼）：

從左邊第二位起，將每位與左邊一位解碼后的值異或，作為該位解碼后的值（最左邊一位依然不變）。依次異或，直到最低位。依次異或轉(zhuǎn)換后的值（二進制數(shù)）就是格雷碼轉(zhuǎ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ā)生變化了。