LintCode領扣 題解丨 微軟面試高頻題：格雷編碼

格雷編碼是一個二進制數字系統，在該系統中，兩個連續的數值僅有一個二進制的差異。

給定一個非負整數 n ，表示該代碼中所有二進制的總數，請找出其格雷編碼順序。一個格雷編碼順序必須以 0 開始，并覆寫所有的 2n 個整數。

對于給定的 n，其格雷編碼順序并不唯一。

當n = 2時，根據上面的定義，[0,1,3,2] 和 [0,2,3,1] 都是有效的格雷編碼順序。

線上評測位址：

https://www.lintcode.com/problem/gray-code/?utm_source=sc-tc-sz0812

​

樣例 1:

輸入: 1

輸出: [0, 1]

樣例 2:

輸入: 2

輸出: [0, 1, 3, 2]

解釋:

0 - 00

1 - 01

3 - 11

2 - 10

最簡單的做法是利用位運算. 在《計算機組成與設計》一書上有介紹.

一個數字對應的格雷編碼的計算方式是:

将其二進制第一位(從高位數)與0異或, 得到的結果為格雷碼的第一位

之後依次将原數的第i位與生成的格雷碼第i-1位做異或運算, 即可得到格雷碼的第i位.

public class Solution {

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

}

////////// 遞歸版本

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if (n <= 1) {
        for (int i = 0; i <= n; i++){
            result.add(i);
        }
        return result;
    }
    result = grayCode(n - 1);
    ArrayList<Integer> r1 = reverse(result);
    int x = 1 << (n-1);
    for (int i = 0; i < r1.size(); i++) {
        r1.set(i, r1.get(i) + x);
    }
    result.addAll(r1);
    return result;
}

public ArrayList<Integer> reverse(ArrayList<Integer> r) {
    ArrayList<Integer> rev = new ArrayList<Integer>();
    for (int i = r.size() - 1; i >= 0; i--) {
        rev.add(r.get(i));
    }
    return rev;
}           

更多題解參見九章算法官網：

https://www.jiuzhang.com/solution/gray-code/?utm_source=sc-tc-sz0812