原文链接: https://leetcode-cn.com/problems/gray-code

英文原文

An n-bit gray code sequence is a sequence of 2n integers where:

• Every integer is in the inclusive range [0, 2n - 1],
• The first integer is 0,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

 

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

 

Constraints:

• 1 <= n <= 16

中文题目

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

 

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

 

提示：

• 1 <= n <= 16

通过代码

高赞题解

思路：

• 设 $n$ 阶格雷码集合为 $G(n)$，则 $G(n+1)$ 阶格雷码为：

  • 给 $G(n)$ 阶格雷码每个元素二进制形式前面添加 $0$，得到 $G’(n)$；

  • 设 $G(n)$ 集合倒序（镜像）为 $R(n)$，给 $R(n)$ 每个元素二进制形式前面添加 $1$，得到 $R’(n)$；

  • $G(n+1) = G’(n) ∪ R’(n)$ 拼接两个集合即可得到下一阶格雷码。

• 根据以上规律，可从 $0$ 阶格雷码推导致任何阶格雷码。

• 代码解析：

  • 由于最高位前默认为 $0$，因此 $G’(n) = G(n)$，只需在 res(即 $G(n)$ )后添加 $R’(n)$ 即可；

  • 计算 $R’(n)$：执行 head = 1 << i 计算出对应位数，以给 $R(n)$ 前添加 $1$ 得到对应 $R’(n)$；

  • 倒序遍历 res(即 $G(n)$ )：依次求得 $R’(n)$ 各元素添加至 res 尾端，遍历完成后 res(即 $G(n+1)$)。

图解：

<,,,>

代码：

[]

class Solution:

    def grayCode(self, n: int) -> List[int]:

        res, head = [0], 1

        for i in range(n):

            for j in range(len(res) - 1, -1, -1):

                res.append(head + res[j])

            head <<= 1

        return res

[]

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;

    }

}

统计信息

通过次数	提交次数	AC比率
62899	88306	71.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
1比特与2比特字符	简单