一、题目
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(2n)
其中n是格雷码序列的位数。
空间复杂度： O(1)
三、总结
将格雷码序列进行翻转，追加到原有序列的尾部，此时新序列的前后两部分均为合法的格雷码。
接下来就是考虑衔接点的合法性：
- 将翻转后的每个数进行尾部加1操作，确保连接点的两个数只有一位二进制位不同
- 追加1后，首尾两个数的二进制只有一位不同
这样就保证了整个序列的合法性。
