☆打卡算法☆LeetCode 89、格雷编码 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

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

题目链接：

来源：力扣（LeetCode）

链接：89. 格雷编码 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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、思路分析

首先说一下格雷码，格雷码是一种典型的二进制编码，最开始是为了通信，用于模拟数字转换和位置数字转换使用，后来应用于机械计数或电路状态输入等。

对于这道题来说，如果我们已经获取到了格雷码序列，只需要对它进行翻转，那么翻转前和翻转后的尾元素应该是相同。

2、代码实现

代码参考：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        ret.add(0);
        for (int i = 1; i <= n; i++) {
            int m = ret.size();
            for (int j = m - 1; j >= 0; j--) {
                ret.add(ret.get(j) | (1 << (i - 1)));
            }
        }
        return ret;
    }
}

3、时间复杂度

时间复杂度 ： O(2ⁿ)

其中n是格雷码序列的位数。

空间复杂度： O(1)

三、总结

将格雷码序列进行翻转，追加到原有序列的尾部，此时新序列的前后两部分均为合法的格雷码。

接下来就是考虑衔接点的合法性：

• 将翻转后的每个数进行尾部加1操作，确保连接点的两个数只有一位二进制位不同
• 追加1后，首尾两个数的二进制只有一位不同

这样就保证了整个序列的合法性。