LeetCode Gray Code 格雷碼生成詳解

題目要求

給定非負整數 n，生成 n 位格雷碼序列。格雷碼特性：相鄰兩個數的二進制表示僅有一位不同，且序列必須以 0 開頭。

例：n = 2 時，[0,1,3,2] 是合法序列（二進制：00, 01, 11, 10）。注意序列不唯一，[0,2,3,1] 也正確。

遞歸構造法

格雷碼具有優美的遞歸結構：

1. n = 1 時：[0, 1]
2. n > 1 時：先得到 n-1 位序列 L，則 n 位序列為：
   ['0' + x for x in L] + ['1' + x for x in reversed(L)]

這保證了中間銜接處只差最高位，其餘位保持格雷碼性質。

Java 實現

public class Solution {
    public List grayCode(int n) {
        List strList = generate(n);
        List res = new ArrayList<>();
        for (String s : strList)
            res.add(Integer.parseInt(s, 2));
        return res;
    }

    private List generate(int n) {
        List list = new ArrayList<>();
        if (n == 0) { list.add("0"); return list; }
        if (n == 1) { list.add("0"); list.add("1"); return list; }

        List prev = generate(n - 1);
        List cur = new ArrayList<>();
        for (String s : prev) cur.add("0" + s);
        for (int i = prev.size() - 1; i >= 0; --i) cur.add("1" + prev.get(i));
        return cur;
    }
}

迭代/位運算優化

更高效的做法直接用公式：i-th Gray code = i ^ (i >> 1)。時間 O(2ⁿ)，空間 O(1)（不計輸出）。

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

總結

格雷碼是經典的組合數學結構，遞歸構造直觀易懂，位運算公式則極其高效。面試中掌握兩種寫法並能說明原理為佳。