LeetCode：格雷编码、循环码排列

89. 格雷编码

问题描述

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

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

示例

输入：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 有一位不同

解题思路

镜像反射法求解，思路来源Krahets。

设 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 阶格雷码推导致任何阶格雷码。

代码示例（JAVA）

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);

        for (int i = 0; i < n; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                res.add((1 << i) + res.get(j));
            }
        }
        
        return res;
    }
}

时间复杂度：O(2ⁿ)

---

1238. 循环码排列

问题描述

给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：

• p[0] = start
• p[i] 和 p[i+1] 的二进制表示形式只有一位不同
• p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

示例

输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

输出：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

解题思路

用镜像反射法找到格雷编码，找到编码后重新以start开头排列。
另，用以start开始求每一个格雷编码，求出的结果与start做异或运算可以直接得出结果。

代码示例（JAVA）

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> res = new ArrayList<>();
        res.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 = head << 1;
        }
        // 以start开头
        for (int i = 0; i < res.size(); i++) {
            if (res.get(i) == start) {
                List<Integer> newList = new ArrayList<>();
                newList.addAll(res.subList(i, res.size()));
                newList.addAll(res.subList(0, i));
                res = newList;
            }
        }

        return res;
    }
}

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> res = new ArrayList<>();
        res.add(start);

        for (int i = 0; i < n; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                res.add(((1 << i) + (res.get(j) ^ start)) ^ start);
            }
        }
        
        return res;
    }
}

时间复杂度：O(2ⁿ)