题目描述补充

格雷编码（Gray Code），也称反射二进制码或循环二进制码，是一种二进制数的编码方式，其中两个连续的数值仅有一个位数的差异。格雷码在数字系统错误检测、通信、密码学等领域中有重要应用。

给定一个非负整数 n，代表需要生成的格雷码的位数，请编写一个算法来生成长度为 2^n 的格雷码序列。格雷码序列必须按从小到大的顺序排列（即，从 0 开始，到 2^n - 1 结束）。

示例

对于 n = 2，格雷码序列为 [0, 1, 3, 2]。

对于 n = 3，格雷码序列为 [0, 1, 3, 2, 6, 7, 5, 4]。

PHP 示例代码

function grayCode($n) {
    $result = [0];
    $num = 1;
    
    for ($i = 0; $i < $n; $i++) {
        $num = $num << 1; // 左移一位，相当于乘以2
        for ($j = $num - 1; $j >= 0; $j--) {
            $result[] = $result[$j] | $num; // 或运算，相当于当前元素+2^i
        }
    }
    
    return $result;
}

// 测试
echo implode(', ', grayCode(2)); // 输出: 0, 1, 3, 2
echo "\n";
echo implode(', ', grayCode(3)); // 输出: 0, 1, 3, 2, 6, 7, 5, 4

Python 示例代码

def grayCode(n):
    if n == 0:
        return [0]
    
    prev = grayCode(n - 1)
    curr = [x + (1 << (n - 1)) for x in reversed(prev)]
    return prev + curr

# 测试
print([str(x) for x in grayCode(2)])  # 输出: ['0', '1', '3', '2']
print([str(x) for x in grayCode(3)])  # 输出: ['0', '1', '3', '2', '6', '7', '5', '4']

JavaScript 示例代码

function grayCode(n) {
    if (n === 0) return [0];
    
    const prev = grayCode(n - 1);
    const curr = prev.reverse().map(x => x | (1 << (n - 1)));
    return prev.concat(curr);
}

// 测试
console.log(grayCode(2).toString()); // 输出: "0,1,3,2"
console.log(grayCode(3).toString()); // 输出: "0,1,3,2,6,7,5,4"

码小课网站分享

码小课网站中有更多关于算法和数据结构的详细解析、面试题讲解以及实战案例分享，欢迎大家访问学习，提升编程技能。