LeetCode Gray Code 格雷碼：遞歸構造與位運算公式兩種解法

Java 實作

import java.util.ArrayList;

public class GrayCode {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> res = new ArrayList<>();
        res.add(0);  // n=0 時序列
        
        for (int i = 1; i <= n; ++i) {
            int prefix = 1 << (i - 1);  // 最高位掩碼
            int size = res.size();
            // 逆序遍歷原序列，加上前綴
            for (int j = size - 1; j >= 0; --j) {
                res.add(res.get(j) + prefix);
            }
        }
        return res;
    }
}

演示過程 (n=3)

i=1: [0] → [0, 1]           (前綴 1)
i=2: [0, 1] → [0, 1, 3, 2]  (前綴 2)
i=3: [0, 1, 3, 2] → [0, 1, 3, 2, 6, 7, 5, 4]  (前綴 4)

解法二：格雷碼編碼公式

數學公式

第 i 個格雷碼：G(i) = i ^ (i >> 1)

• i >> 1：右移一位
• ^：異或運算

Java 實作

public class GrayCode2 {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> res = new ArrayList<>();
        int total = 1 << n;  // 2^n
        for (int i = 0; i < total; ++i) {
            res.add((i >> 1) ^ i);
        }
        return res;
    }
}

公式驗證 (n=3)

兩種解法比較

格雷碼應用場景

1. 卡諾圖簡化：相鄰格僅差一變數
2. 旋轉編碼器：避免多位同時翻轉導致誤讀
3. 漢諾塔最優解：移動步驟對應格雷碼序列
4. 基因演算法：編碼鄰近性保持
5. 誤差校正：最小化狀態轉換錯誤

解碼：格雷碼 → 二進位