“给定一个整数,返回任一有效的n位格雷码序列。”
题目链接:
来源:力扣(LeetCode)
链接:89. 格雷编码 - 力扣(LeetCode) (leetcode-cn.com)
n 位格雷码序列 是一个由 2n 个整数组成的序列,其中:
示例 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]
首先说一下格雷码,格雷码是一种典型的二进制编码,最开始是为了通信,用于模拟数字转换和位置数字转换使用,后来应用于机械计数或电路状态输入等。
对于这道题来说,如果我们已经获取到了格雷码序列,只需要对它进行翻转,那么翻转前和翻转后的尾元素应该是相同。
代码参考:
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;
}
}
时间复杂度 : O(2n)
其中n是格雷码序列的位数。
空间复杂度: O(1)
将格雷码序列进行翻转,追加到原有序列的尾部,此时新序列的前后两部分均为合法的格雷码。
接下来就是考虑衔接点的合法性:
这样就保证了整个序列的合法性。